a)原理：每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最后，直到全部記錄排序完畢。也就是：每一趟在n-i+1(i=1，2，…n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。基于此思想的算法主要有簡(jiǎn)單選擇排序、樹(shù)型選擇排序和堆排序。（這里只介紹常用的簡(jiǎn)單選擇排序）

b)簡(jiǎn)單選擇排序的基本思想：給定數(shù)組：int[]arr={里面n個(gè)數(shù)據(jù)}；第1趟排序，在待排序數(shù)據(jù)arr[1]~arr[n]中選出最小的數(shù)據(jù)，將它與arrr[1]交換；第2趟，在待排序數(shù)據(jù)arr[2]~arr[n]中選出最小的數(shù)據(jù)，將它與r[2]交換；以此類(lèi)推，第i趟在待排序數(shù)據(jù)arr[i]~arr[n]中選出最小的數(shù)據(jù)，將它與r[i]交換，直到全部排序完成。

c)舉例：數(shù)組int[]arr={5,2,8,4,9,1};

-------------------------------------------------------

第一趟排序： 原始數(shù)據(jù)：528491

最小數(shù)據(jù)1，把1放在首位，也就是1和5互換位置，

排序結(jié)果：128495

-------------------------------------------------------

第二趟排序：

第1以外的數(shù)據(jù){28495}進(jìn)行比較，2最小，

排序結(jié)果：128495

-------------------------------------------------------

第三趟排序：

除1、2以外的數(shù)據(jù){8495}進(jìn)行比較，4最小，8和4交換

排序結(jié)果：124895

-------------------------------------------------------

第四趟排序：

除第1、2、4以外的其他數(shù)據(jù){895}進(jìn)行比較，5最小，8和5交換

排序結(jié)果：124598

-------------------------------------------------------

第五趟排序：

除第1、2、4、5以外的其他數(shù)據(jù){98}進(jìn)行比較，8最小，8和9交換

排序結(jié)果：124589

-------------------------------------------------------

注：每一趟排序獲得最小數(shù)的方法：for循環(huán)進(jìn)行比較，定義一個(gè)第三個(gè)變量temp，首先前兩個(gè)數(shù)比較，把較小的數(shù)放在temp中，然后用temp再去跟剩下的數(shù)據(jù)比較，如果出現(xiàn)比temp小的數(shù)據(jù)，就用它代替temp中原有的數(shù)據(jù)。具體參照后面的代碼示例，相信你在學(xué)排序之前已經(jīng)學(xué)過(guò)for循環(huán)語(yǔ)句了，這樣的話(huà)，這里理解起來(lái)就特別容易了。

代碼示例：

//選擇排序
public class SelectionSort {
  public static void main(String[] args) {
    int[] arr={1,3,2,45,65,33,12};
    System.out.println("交換之前：");
    for(int num:arr){
      System.out.print(num+" ");
    }    
    //選擇排序的優(yōu)化
    for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
      int k = i;
      for(int j = k + 1; j < arr.length; j++){// 選最小的記錄
        if(arr[j] < arr[k]){ 
          k = j; //記下目前找到的最小值所在的位置
        }
      }
      //在內(nèi)層循環(huán)結(jié)束，也就是找到本輪循環(huán)的最小的數(shù)以后，再進(jìn)行交換
      if(i != k){ //交換a[i]和a[k]
        int temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
      }  
    }
    System.out.println();
    System.out.println("交換后：");
    for(int num:arr){
      System.out.print(num+" ");
    }
  }

}

運(yùn)行結(jié)果截圖：

選擇排序的時(shí)間復(fù)雜度：簡(jiǎn)單選擇排序的比較次數(shù)與序列的初始排序無(wú)關(guān)。假設(shè)待排序的序列有N個(gè)元素，則比較次數(shù)永遠(yuǎn)都是N(N-1)/2。而移動(dòng)次數(shù)與序列的初始排序有關(guān)。當(dāng)序列正序時(shí)，移動(dòng)次數(shù)最少，為0。當(dāng)序列反序時(shí)，移動(dòng)次數(shù)最多，為3N(N-1)/2。

所以，綜上，簡(jiǎn)單排序的時(shí)間復(fù)雜度為O(N2)。

最新評(píng)論