JAVA簡略選擇排序算法道理及完成

簡略選擇排序：（選出最小值，放在第一名，然後第一名向後推移，如斯輪回）第一名與前面每個逐一比擬，每次都使最小的置頂，第一名向後推動（即剛選定的第一名是最小值，不再介入比擬，比擬次數減1）

龐雜度： 所需停止記載挪動的操作次數較少 0--3(n-1) ，不管記載的初始分列若何，所需的症結字間的比擬次數雷同，均為n(n-1)/2，總的時光龐雜度為O(n2)；
空間龐雜度 O(1)

算法改良：每次比較，都是為了將最小的值放到第一名，所以可以一比究竟，找出最小值，直接放到第一名，省去有意義的更換挪動操作。也能夠換一個偏向，最初一名與後面每個比擬，每次使最年夜值沉底，最初一名向前推動。

JAVA源代碼：

 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;
　　}
　　}

　　則完成遞歸的結構新聚集中的最小值。