JAVA簡單選擇排序算法及實現
簡單選擇排序:
(選出最小值,放在第一位,然後第一位向後推移,如此循環)第一位與後面每一個逐個比較,每次都使最小的置頂,第一位向後推進(即剛選定的第一位是最小值,不再參與比較,比較次數減1)
複雜度: 所需進行記錄移動的操作次數較少 0--3(n-1) ,無論記錄的初始排列如何,所需的關鍵字間的比較次數相同,均為n(n-1)/2,總的時間複雜度為O(n2);
空間複雜度 O(1)
算法改進:每次對比,都是為了將最小的值放到第一位,所以可以一比到底,找出最小值,直接放到第一位,省去無意義的調換移動操作。也可以換一個方向,最後一位與前面每一個比較,每次使最大值沉底,最後一位向前推進。
複製代碼 代碼如下:
public static void selectSort(Date[] days) {
int min;
Date temp;
for (int i = 0; i < th; i++) {
min = i;
for (int j = min + 1; j < th; j++) {
if (days[min]are(days[j]) > 0) {
min = j;
}
}
if (min != i) {
temp = days[i];
days[i] = days[min];
days[min] = temp;
}
}
}
class Date {
int year, month, day;
Date(int y, int m, int d) {
year = y;
month = m;
day = d;
}
public int compare(Date date) {
return year > ? 1 : year < ? -1
: month > h ? 1 : month < h ? -1
: day > ? 1 : day < ? -1 : 0;
}
public void print() {
tln(year + " " + month + " " + day);
}
}
簡單選擇排序(Simple Selection Sort):
簡單選擇排序類似於冒泡排序(Bubble Sort) ,每次都會在剩下的元素集合中選擇出一個最值出來填充到當前位置。唯一的區別是,冒泡排序在每次發現比當前值小於(或大於)時,都會交換元素的位置, 而 簡單選擇排序是選擇剩餘元素中的最值和當前位置交換數據。
比如對於元素集合R={37, 40, 38, 42, 461, 5, 7, 9, 12}
在第一趟排序中:37直接和5交換, 形成新的序列 R1={5,40,38,42,461,37,7,9,12}
在第二趟排序中:40直接和7交換, 形成新的序列 R2={5,7,38,42,461,37,40,9,12}
以此類推,直到最後一個元素(注意:在第二趟排序中,38比42小,但是他們並沒有交換數據)。
以下是簡單選擇排序的一個Java實現版本:
複製代碼 代碼如下:
public static void selectionSort(int[] data) {
if (data == null || th <= 1)
return;
int i, j, vALue, minPos, len = th;
int outer = len - 1, tmp;
for (i = 0; i < outer; i++) {
value = data[i];
minPos = -1;
for (j = i + 1; j < len; j++) {
if (data[j] < value) {
minPos = j;
value = data[j];
}
}
if (minPos != -1) {
tmp = data[i];
data[i] = value;
data[minPos] = tmp;
}
// for (int k = 0; k < len; k++) {
// t(data[k] + " , ");
// }
// tln();
}
}
public static void main(String[] args) {
int[] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
selectionSort(coll);
for (int i = 0; i < th; i++) {
t(coll[i] + " , ");
}
}
樹選擇排序(Tree Selection Sort)
樹選擇排序算法相對於簡單選擇排序來説是典型的以空間換時間的算法。其思想是對待排序的 N 個元素 , 構造出相對較小的 (n+1)/2個數,然後再構造出相對較小的'[n+1]/4個數,直到只有一個元素為止。構造成一個完全二叉樹。
排序的時候,那個元素就是最小的,取出該最小元素,將該元素替換為"最大值",再調整完全二叉樹。
下面是樹形選擇排序的一個Java實現版:
複製代碼 代碼如下:
public static void treeSelectionSort(int[] data) {
if (data == null || th <= 1)
return;
int len = th , low = 0 , i , j;
// add Auxiliary Space
int[] tmp = new int[2*len -1];
int tSize = th;
//construct a tree
for(i =len-1 , j=th-1;i >=0 ;i--,j--){
tmp[j]=data[i];
}
for(i = tSize -1 ; i > 0 ; i-=2){
tmp[(i-1)/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
}
//end
//remove the minimum node.
while(low < len){
data[low++] = tmp[0];
for(j=tSize-1;tmp[j]!=tmp[0];j--);
tmp[j] = _VALUE;
while(j > 0){
if(j%2 == 0){ //如果是右節點
tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = (j-1)/2;
}else{ //如果是左節點
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}
}
}
在構造完全二叉樹的時候對 N 個元素的集合, 需要 2*N -1 個輔助空間。
複製代碼 代碼如下:
while(j > 0){
if(j%2 == 0){ //如果是右節點
tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = (j-1)/2;
}else{ //如果是左節點
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}
則實現遞歸的構造新集合中的最小值。