快捷導(dǎo)航

JAVA簡(jiǎn)單選擇排序算法原理及實(shí)現(xiàn)

更新時(shí)間：2014年01月19日 13:27:41 作者：

選擇排序（Selection Sort ）分為兩種簡(jiǎn)單選擇排序（Simple Selection Sort）和樹形選擇排序

簡(jiǎn)單選擇排序：（選出最小值，放在第一位，然后第一位向后推移，如此循環(huán)）第一位與后面每一個(gè)逐個(gè)比較，每次都使最小的置頂，第一位向后推進(jìn)（即剛選定的第一位是最小值，不再參與比較，比較次數(shù)減1）

復(fù)雜度：所需進(jìn)行記錄移動(dòng)的操作次數(shù)較少 0--3(n-1) ，無論記錄的初始排列如何，所需的關(guān)鍵字間的比較次數(shù)相同，均為n(n-1)/2，總的時(shí)間復(fù)雜度為O(n2)；
空間復(fù)雜度 O(1)

算法改進(jìn)：每次對(duì)比，都是為了將最小的值放到第一位，所以可以一比到底，找出最小值，直接放到第一位，省去無意義的調(diào)換移動(dòng)操作。也可以換一個(gè)方向，最后一位與前面每一個(gè)比較，每次使最大值沉底，最后一位向前推進(jìn)。

JAVA源代碼：

復(fù)制代碼代碼如下:

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

　　簡(jiǎn)單選擇排序（Simple Selection Sort）：

　　簡(jiǎn)單選擇排序類似于冒泡排序（Bubble Sort） ,每次都會(huì)在剩下的元素集合中選擇出一個(gè)最值出來填充到當(dāng)前位置。唯一的區(qū)別是，冒泡排序在每次發(fā)現(xiàn)比當(dāng)前值小于（或大于）時(shí)，都會(huì)交換元素的位置，而簡(jiǎn)單選擇排序是選擇剩余元素中的最值和當(dāng)前位置交換數(shù)據(jù)。

　　比如對(duì)于元素集合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}

　　以此類推，直到最后一個(gè)元素（注意：在第二趟排序中，38比42小，但是他們并沒有交換數(shù)據(jù)）。

　　以下是簡(jiǎn)單選擇排序的一個(gè)Java實(shí)現(xiàn)版本：

復(fù)制代碼代碼如下:

　　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）
　　樹選擇排序算法相對(duì)于簡(jiǎn)單選擇排序來說是典型的以空間換時(shí)間的算法。其思想是對(duì)待排序的 N 個(gè)元素 , 構(gòu)造出相對(duì)較小的（n+1）/2個(gè)數(shù)，然后再構(gòu)造出相對(duì)較小的[n+1]/4個(gè)數(shù)，直到只有一個(gè)元素為止。構(gòu)造成一個(gè)完全二叉樹。
　　排序的時(shí)候，那個(gè)元素就是最小的，取出該最小元素，將該元素替換為"最大值",再調(diào)整完全二叉樹。
下面是樹形選擇排序的一個(gè)Java實(shí)現(xiàn)版：

復(fù)制代碼代碼如下:

　　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）{  //如果是右節(jié)點(diǎn)
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  //如果是左節(jié)點(diǎn)
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}
　　}
　　}

　　在構(gòu)造完全二叉樹的時(shí)候?qū)?N 個(gè)元素的集合，需要 2*N -1 個(gè)輔助空間。
　　代碼：

復(fù)制代碼代碼如下:

　　while（j > 0）{
　　if（j%2 == 0）{  //如果是右節(jié)點(diǎn)
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  //如果是左節(jié)點(diǎn)
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}

　　則實(shí)現(xiàn)遞歸的構(gòu)造新集合中的最小值。

您可能感興趣的文章: