【2】資料結構與算法 —— 選擇排序算法

選擇排序分為簡單選擇排序和堆排序，下面看看兩個算法直接的對比。

1、簡單選擇排序

簡單選擇排序法就是通過n-i此關鍵字間的比較，從n-i-1個記錄中選出關鍵字最小的記錄，并且和第i個記錄交換。實作如下：

package com.sort.exe;

public class SelectSort {

  public  void selectSort(int[] arrs){
    int i,j,min=0;
    for( i=0;i<arrs.length;i++){
      //将第一個下标設為最小值；
      min=i;
      for( j=i+1;j<arrs.length;j++){
        //若第j個下标表示的值比 min表示的值小，就将下标j指派給min;如此操作直到數組尾部
        if(arrs[min] > arrs[j])
          min=j;
      }
      //如果min改變了，說明找到了最小值
      if(min != i){
        int temp=arrs[i];
        arrs[i]=arrs[min];
        arrs[min]=temp;
      }
    }
  }
  
  public static void main(String[] args){
     int[] a={1,12,3,9,5,6,8}; 
     new SelectSort().selectSort(a);
     for(int i=0;i<a.length;i++){ 
       System.out.print(a[i]+" "); 
    } 
  }
}      

時間複雜度O（n^2）

2、堆排序