Java排序算法_選擇排序

選擇排序的基本操作就是每一趟從待排序的資料元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。算法不穩定，O(1)的額外的空間，比較的時間複雜度為O(n^2)，交換的時間複雜度為O(n)，并不是自适應的。在大多數情況下都不推薦使用。隻有在希望減少交換次數的情況下可以用。

基本思想

n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

①初始狀态：無序區為R[1..n]，有序區為空。

②第1趟排序

在無序區R[1..n]中選出關鍵字最小的記錄R[k]，将它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

……

③第i趟排序

第i趟排序開始時，目前有序區和無序區分别為R[1..i-1]和R(1≤i≤n-1)。該趟排序從目前無序區中選出關鍵字最小的記錄

R[k]，将它與無序區的第1個記錄R交換，使R[1..i]和R分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

這樣，n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

代碼實作

public class chooseSort {

public static void main(String[] args) {

 int[] a = {25,89,42,16,12,36};

 int min = 0;

 int tmp = 0;

 for(int

i=0;i<a.length;i++){

  min = i;//

 System.out.println("第一組設定下标min為："+min);

  for(int

j=i+1;j<a.length;j++){

 if(a[min]>a[j]) {

System.out.print(a[min]+"比"+a[j]+"要大  

  ");

    min =

j;//記下較大數位置，再次比較，直到最大

   }

 System.out.println("現在較小數為"+a[min]+"，下标為min:"+min+"

    ");

  }

  if(i!=min){

   tmp = a[i];

   a[i] = a[min];

   a[min] = tmp;

 System.out.print(a[i]+"與"+a[min]+"進行了交換，現在較大值為：a[min]:"+a[min]+"

要換的值的下标為："+min+"     ");

  System.out.println(Arrays.toString(a));

 }

 for(int i=0;i<a.length;i++)

  System.out.print(a[i]+" ");

}

代碼二：按順序排序

public static void main(String args[]) {

 int[] array = { 14, 5, 86, 4, 12, 3, 51, 13,

11, 2, 32, 6 };  // 建立一個初始化的一維數組array

 int keyValue;  

   // 表示最小的元素值

 int index;  

    // 表示最小的元素值的下标

 int temp;  

    // 中間變量

 System.out.println("未排序的數組:");

 for (int i = 0; i <

array.length; i++) {  // 周遊array數組中的元素

  System.out.print(" " + array[i]);

 // 輸出數組元素

  if ((i + 1) % 5 == 0)  

 // 每5個元素一行

 System.out.println();

array.length; i++) {  // 使用選擇排序法的核心

  index = i;

  keyValue = array[i];

  for (int j = i; j <

array.length; j++)

   if (array[j]

< keyValue) {

    index = j;

    keyValue =

array[j];

  temp = array[i];

  array[i] = array[index];

  array[index] = temp;

 System.out.println("\n使用選擇排序法後的數組:");

array.length; i++) {   // 周遊排好序的array數組中的元素

  // 輸出數組元素

  if ((i + 1) % 5 == 0)

   System.out.println();

   // 每5個元素一行

選擇排序法與冒泡排序法一樣，最外層循環仍然要執行n-1次，其效率仍然較差