選擇排序法

選擇排序法 是對 定位比較交換法（也就是冒泡排序法） 的一種改進。選擇排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。基於此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序。

簡單選擇排序的基本思想：第1趟，在待排序記錄r[1]~r[n]中選出最小的記錄，將它與r[1]交換；第2趟，在待排序記錄r[2]~r[n]中選出最小的記錄，將它與r[2]交換；以此類推，第i趟在待排序記錄r[i]~r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。

基本介紹

• 中文名：選擇排序法
• 外文名：Selection sort
• 類型：編程邏輯
• 分類：簡單選擇排序，樹型選擇排序

基本思想

選擇排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。基於此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序。

簡單選擇排序的基本思想：第1趟，在待排序記錄r[1]~r[n]中選出最小的記錄，將它與r[1]交換；第2趟，在待排序記錄r[2]~r[n]中選出最小的記錄，將它與r[2]交換；以此類推，第i趟在待排序記錄r[i]~r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。

以下為簡單選擇排序的存儲狀態，其中大括弧內為無序區，大括弧外為有序序列：

初始序列：{49 27 65 97 76 12 38}
第1趟：12與49交換：12{27 65 97 76 49 38}
第2趟：27不動　：12 27{65 97 76 49 38}
第3趟：65與38交換：12 27 38{97 76 49 65}
第4趟：97與49交換：12 27 38 49{76 97 65}
第5趟：76與65交換：12 27 38 49 65{97 76}
第6趟：97與76交換：12 27 38 49 65 76 97 完成

簡單選擇排序的算法具體描述如下：

void SelectSort(RecordType r[], int length)　/*對記錄數組r做簡單選擇排序，length為待排序記錄的個數*/{    int temp;    for ( i=0 ; i< length-1 ; i++) //n-1趟排序    {        int index=i；　//假設index處對應的數組元素是最小的        for (int j=i+1 ; j < length ; j++) 　//查找最小記錄的位置            if (r[j].key < r[index].key )                index=j;        if ( index!=i) 　//若無序區第一個元素不是無序區中最小元素，則進行交換        {            temp     = r[i];            r[i]     = r[index];            r[index] = temp;        }    }}

算法

簡單選擇排序算法分析：在簡單選擇排序過程中，所需移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄。最壞情況下，需要移動記錄的次數最多為3（n-1）（此情況中待排序記錄並非完全逆序，給完全逆序記錄排序的移動次數應為(n/2)*3，其中n/2向下取整）。簡單選擇排序過程中需要進行的比較次數與初始狀態下待排序的記錄序列的排列情況無關。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依次類推，共需要進行的比較次數是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即進行比較操作的時間複雜度為O(n2)。

在講選擇排序法之前我們先來了解一下定位比較交換法。為了便於理解，設有10個數分別存在數組元素a[0]～a[9]中。定位比較交換法是由大到小依次定位a[0]～a[9]中恰當的值（和武林大會中的比武差不多），a[9]中放的自然是最小的數。如定位a[0],先假定a[0]中當前值是最大數，a[0]與後面的元素一一比較，如果a[4]更大，則將a[0]、a[4]交換，a[0]已更新再與後面的a[5]～a[9]比較，如果a[8]還要大，則將a[0]、a[8]交換，a[0]又是新數，再與a[9]比較。一輪比完以後，a[0]就是最大的數了，本次比武的武狀元誕生了，接下來從a[1]開始，因為狀元要休息了，再來一輪a[1]就是次大的數，也就是榜眼，然後從a[2]開始，比出探花，真成比武大會了，當比到a[8]以後，排序就完成了。

下面給大家一個例子：

int main(void){    int a[10];    int i,j,t;    for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/    for ( i = 0; i < 9; i ++ )    for ( j = i + 1; j < 10; j ++)    if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /*打不過就要讓出頭把交椅，不過a[ i ]比較愛面子，不好意思見 a[ j ]，讓t幫忙*/    for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/    return 0;}

好啦，囉嗦了半天總算把定位比較排序法講完了，這個方法不錯，容易理解，就是有點麻煩，一把椅子換來換去，哎～

所以就有了下面的選擇排序法，開始的時候椅子誰也不給，放在一邊讓大家看著，找個人k記錄比賽結果，然後發椅子。具體來講呢就是，改進定位比較排序法，但是這個改進只是一部分，比較的次數沒變，該怎么打還是怎么打，就是不用換椅子了。每次外循環先將定位元素的小標i值記錄到K，認為a[k]是最大元素其實k=i還是a[ i ]最大，a[k]與後面的元素一一比較，該交換的也交換，就是把K的值改變一下就完了，最後在把a[k]與a[ i ]交換，這樣a就是最大的元素了。然後進入下一輪的比較。選擇排序法與定位比較排序法相比較，比的次數沒變，交換的次數減少了。

下面也寫個例子：

由大到小時：

int main(void){    int a[10];    int i,j,t,k;    for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/    for ( i = 0;i < 9;i ++ ) /*10個數，所以只需比9次*/    {        k = i; /*裁判AND記者實時追蹤報導比賽情況*/        for ( j = i + 1; j < 10; j ++)            if ( a[ k ] < a[ j ] ) k = j; /*使a[k]始終表示已比較的數中的最大數*/        if （k！=i）        {             t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t;        } /* t 發放獎品* /    }    for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/    return 0;}

由小到大時：

int main(void){    int a[10];    int i,j,t,k;    for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/    for ( i = 0; i < 9; i ++ )    {        k = i; /*裁判AND記者實時追蹤報導比賽情況*/        for ( j = i + 1; j < 10; j ++)            if ( a[ k ] > a[ j ] ) k = j;        if （k！=i）        {            t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t;        }/* t 發放獎品*/    }        for( i = 0; i<= 9; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/return 0;}

有人對上面這兩個算法有一點誤解，原話是這樣說的（“”能看到這裡的都對以上選擇法排序有所疑惑，注意了，以上C語言選擇排序法，都是錯誤的，自己沒有弄清就來誤導別人。而且在網上流傳的選擇排序法大部分都犯的和上面同樣的錯誤。我們來做個邏輯論證，就拿上面這個人說的這個例子，假設第一次比，a[ k ]比a[ j ]比贏了，k變成a[ j ],然後發生第一次交換，第二次比試，a [ k ](這時是a[ j ])又和a[ j +1 ]比，這時沒比贏，不管你怎么比，都要發生第二次交換，因為，第二次的 k 已經變成 j ,再也不等於 i 了。”）這種說法是錯誤的，他很明顯的邏輯錯誤是，假設第一次比贏了，那么進行下一次比較時k的值又再次初始化了，等於此時的i。下面的是一種沒有改進的算法，在內層循環時不管是否改變k的下標，都會進行交換，所以效率會相對低一點。

  ....略   for(i = 0; i <= 8; i++)      {          k = i;          for(j = i + 1; j <= 9; j++)          {              if(a[k] > a[j])              {                  k = j;              }          }         temp = a[i];             //發現區別了嗎？區別就是他們把交換放在第二個for里，不論怎樣       a[i] = a[k];            //只要k的值一變，他們第二個if就滿足條件，會一直交換下去       a[k] = temp;           //而這個才是真正的選擇法    }                         //第二個for內打擂台，打完了才在第一個for內交換  ...略

這個才是真正的選擇排序法，上面那幾個，都是錯誤的。

java選擇排序法代碼

import java.util.Random;public class ArrayDemo {    public static void main(String[] args) {    Random random=new Random();    int[] pData=new int[10];    for(int i=0;i<pData.length;i++){ //隨機生成10個排序數        Integer a =random.nextInt(100);        pData[i]= a;        System.out.print(pData[i]+" ");    }    System.out.println();    pData=Choose(pData);    for(int i=0;i<pData.length;i++){        System.out.print(pData[i]+" ");    }    System.out.println();}public static int[] Choose(int[] pData){    System.out.println();    int k;    for (int i = 0; i < pData.length; i++) {        k = i;        for (int j = i; j < pData.length; j++) {            if(pData[j]<pData[k]){                k = j;            }        }        int a=pData[i];        pData[i]=pData[k];        pData[k]=a;    }    return pData;}}