- 相關推薦
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 < days.length; i++) {
min = i;
for (int j = min + 1; j < days.length; j++) {
if (days[min].compare(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 > date.year ? 1 : year < date.year ? -1
: month > date.month ? 1 : month < date.month ? -1
: day > date.day ? 1 : day < date.day ? -1 : 0;
}
public void print() {
System.out.println(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 || data.length <= 1）
return;
int i, j, value, minPos, len = data.length;
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++） {
// System.out.print（data[k] + " , "）；
// }
// System.out.println（）；
}
}
public static void main（String[] args） {
int[] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
selectionSort（coll）；
for （int i = 0; i < coll.length; i++） {
System.out.print（coll[i] + " , "）；
}
}
樹選擇排序（Tree Selection Sort）
樹選擇排序算法相對于簡單選擇排序來說是典型的以空間換時間的算法。其思想是對待排序的 N 個元素 , 構造出相對較小的 （n+1）/2個數，然后再構造出相對較小的[n+1]/4個數，直到只有一個元素為止。構造成一個完全二叉樹。
排序的時候，那個元素就是最小的，取出該最小元素，將該元素替換為"最大值",再調整完全二叉樹。
下面是樹形選擇排序的一個Java實現版：
復制代碼 代碼如下:
public static void treeSelectionSort（int[] data） {
if （data == null || data.length <= 1）
return;
int len = data.length , low = 0 , i , j;
// add Auxiliary Space
int[] tmp = new int[2*len -1];
int tSize = tmp.length;
//construct a tree
for（i =len-1 , j=tmp.length-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] = Integer.MAX_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;
}
}
則實現遞歸的構造新集合中的最小值。
【JAVA簡單選擇排序算法及實現】相關文章：
Java排序算法06-17
冒泡排序算法原理及JAVA實現代碼方法10-16
java常見的排序算法的代碼09-20
常用Java排序算法詳解09-17
JAVA語言的常見排序算法07-16
權重隨機算法的java實現08-13
java堆排序的算法思想的分析09-14
簡單選擇排序（C語言實現）08-09
C++選擇排序算法實例09-26