選擇排序是常用內部排序的一種,常見的實現算法有直接選擇排序算法和堆排序算法,選擇排序的基本思想是每次從待排數據中選擇第n小的數據放到排序列表的第n個位置,假如共有N個數據待排,那麼經過N-1次排序後,待排數據就已經按照從小到大的順序排列了。
直接選擇排序算法的思想比較簡單:(假設數據放在一個數組a中,且數組的長度是N)
1:從a[0]-a[N-1]中選出最小的數據,然後與a[0]交換位置
2:從a[1]-a[N-1]中選出最小的數據,然後與a[1]交換位置(第1步結束後a[0]就是N個數的最小值)
3:從a[2]-a[N-1]中選出最小的數據,然後與a[2]交換位置(第2步結束後a[1]就是N-1個數的最小值)
以此類推,N-1次排序後,待排數據就已經按照從小到大的順序排列了。
直接選擇排序的java實現如下:
package datasort;
//選擇排序O(n*n)
public class SelectSort {
public static void SelectSort(int[] array){
for(int i=0;i<array.length;i++){
int k=i;
for(int j=i;j<array.length;j++){
if(array[k]>array[j]){
k=j;
}
}
if(k!=i){
int temp=array[k];
array[k]=array[i];
array[i]=temp;
}
}
}
public static void main(String[] args) {
int[] a={28,4,36,2,65,14,55,17};
SelectSort(a);
System.out.println();
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}