java數(shù)據(jù)結(jié)構(gòu)與算法之簡(jiǎn)單選擇排序詳解

更新時(shí)間：2017年05月03日 11:08:45 作者：android小豬

這篇文章主要介紹了java數(shù)據(jù)結(jié)構(gòu)與算法之簡(jiǎn)單選擇排序,結(jié)合實(shí)例形式分析了選擇排序的原理、實(shí)現(xiàn)方法與相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了java數(shù)據(jù)結(jié)構(gòu)與算法之簡(jiǎn)單選擇排序。分享給大家供大家參考，具體如下：

在前面的文章中已經(jīng)講述了交換類的排序算法，這節(jié)中開始說(shuō)說(shuō)選擇類的排序算法了，首先來(lái)看一下選擇排序的算法思想；

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

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

簡(jiǎn)單選擇排序：

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

算法實(shí)現(xiàn)代碼如下：

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;  //記錄當(dāng)前位置
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[k]) {   //找出最小的數(shù)，并用k指向最小數(shù)的位置
          k = j;
        }
      }
            //交換最小數(shù)array[k]與第i位上的數(shù)
      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");
  }
}

算法分析：

在此排序過(guò)程中，需要移動(dòng)記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄；最壞情況下，即待排序記錄初始狀態(tài)是按照逆序排列的，則需要移動(dòng)次數(shù)最多是：3(n-1)。排序過(guò)程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無(wú)關(guān)。當(dāng)i=1時(shí)，需要進(jìn)行n-1次比較；當(dāng)i=n時(shí)，共需要進(jìn)行的比較次數(shù)是：n(n-1)/2，即比較操作的時(shí)間復(fù)雜度是：O(n^2)，進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為O(n)；該排序是不穩(wěn)定排序。

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: