java資料結構排序演算法（3）簡單選擇排序

這篇文章主要介紹了java資料結構與演算法之簡單選擇排序,結合實例形式分析了選擇排序的原理、實作方法與相關操作技巧,需要的朋友可以參考下

本文實例講述了java資料結構與演算法之簡單選擇排序。分享給大家供大家參考，具體如下：

在前面的文章中已經講述了交換類別的排序演算法，這節中開始說說選擇類別的排序演算法了，首先來看一下選擇排序的演算法思想；

選擇排序的基本演算法想法：

#每一趟在n-i+1 (i=1,2, 3,……,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。

簡單選擇排序：

設所排序序列的記錄個數為n。 i取1,2,…,n-1,從所有n-i+1個記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，與第i個記錄交換。執行n-1趟 後就完成了記錄序列的排序。

演算法實作程式碼如下：

package exp_sort;
public class SimpleSelectSort {
  static int i;
  static int temp;
  public static void selectSort(int array[]) {
    for (i = 0; i < array.length; i++) {
      int k = i;  //记录当前位置
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[k]) {   //找出最小的数，并用k指向最小数的位置
          k = j;
        }
      }
            //交换最小数array[k]与第i位上的数
      if (k != i) {
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
      }
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    selectSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}

演算法分析：

在此排序過程中，需要移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄；最壞情況下，即待排序記錄初始狀態是按照逆序排列的，則需要移動次數最多是：3( n-1)。排序過程中需要進行的比較次數與初始狀態下待排序的記錄序列的排列情況無關。當i=1時，需要進行n-1次比較；當i=n時，共需要進行的比較次數是：n(n-1)/2，即比較操作的時間複雜度是：O(n^ 2)，進行移動操作的時間複雜度為O(n)；此排序為不穩定排序#。

【相關推薦】

1. java資料結構排序演算法（1）樹狀選擇排序

2. java資料結構排序演算法（2）歸併排序

3. 詳解Java中選擇排序（Selection Sort_java）的實例教學

4. #java資料結構排序演算法（4）選擇排序

以上是java資料結構排序演算法（3）簡單選擇排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！