【原】你對(duì)排序算法了解多少

貪挽懶月 2022-06-20 發(fā)布于廣東

展開全文

說起排序算法，可能大家會(huì)脫口而出：冒泡排序，選擇排序。沒錯(cuò)，這是我們最熟悉的兩種排序算法，其實(shí)，排序算法遠(yuǎn)不止這些。而且，你之前寫的冒泡、選擇排序真的是最優(yōu)的嗎？

一、排序算法的分類

總的來說分為兩大類，內(nèi)部排序 和外部排序。

1、內(nèi)部排序：

就是將需要排序的數(shù)據(jù)都加載到內(nèi)存中，然后進(jìn)行排序。內(nèi)部排序又分為以下幾類：

插入排序：包括直接插入排序和希爾排序；
選擇排序：包括簡單選擇排序和堆排序；
交換排序：包括冒泡排序和快速排序；
歸并排序
基數(shù)排序：桶排序的擴(kuò)展

2、外部排序：

內(nèi)部排序有個(gè)問題，假如現(xiàn)在要排序的數(shù)據(jù)有10億個(gè)，服務(wù)器內(nèi)存加載不了那么多的數(shù)據(jù)，那就得用外部排序了。外部排序就是先加載一部分，排完了再加載另外一部分，然后再合并。

二、常見的時(shí)間復(fù)雜度

時(shí)間復(fù)雜度從低到高依次有：

常數(shù)階：O(1)
對(duì)數(shù)階：O(logn)
線性階：O(n)
線性對(duì)數(shù)階：O(nlogn)
平方階：O(n^2)
立方階：O(n^3)
k次方階：O(n^k)
指數(shù)階：O(2^n)

接下來，就先看看大家最熟悉的冒泡排序和選擇排序。為了避免篇幅過長，其他六種排序中的每一種都會(huì)用一篇單獨(dú)的文章來介紹。

三、冒泡排序

時(shí)間復(fù)雜度為O(n^2)。

1、排序思想：

從前往后遍歷待排序的序列，依次比較相鄰元素的值，如果逆序，就交換位置。

2、案例：

假如現(xiàn)有一個(gè)待排序列：3, 9, -1, 10, 20，現(xiàn)要用冒泡排序算法將其從小到大排列，過程如下：

(1). 第一趟：

比較3和9，發(fā)現(xiàn)3比9小且3在前面，所以不改變位置，結(jié)果是3, 9, -1, 10, 20，同時(shí)兩個(gè)指針都后移一位；
比較9和-1，交換它們的位置，結(jié)果是3, -1, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
比較9和10，不發(fā)生交換，結(jié)果是3, -1, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
比較10和20，不發(fā)生交換，結(jié)果是3, -1, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；

一趟排序結(jié)束后，最大的數(shù)就排到最后去了。

(2). 第二趟：

經(jīng)過第一趟，其實(shí)最后面那個(gè)數(shù)就是最大了，第二趟要做的就是在前面的四個(gè)數(shù)中找到最大的，放在倒數(shù)第二個(gè)的位置。

比較3和-1，交換位置，結(jié)果是-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
比較3和9，不發(fā)生交換，結(jié)果是-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
比較9和10，不發(fā)生交換，結(jié)果是-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；

經(jīng)過第二趟，就將第二大的數(shù)排到了倒數(shù)第二位。

(3). 第三趟：

比較-1和3，不發(fā)生交換，結(jié)果是-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；
比較3和9，不發(fā)生交換，結(jié)果是-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；

經(jīng)過這一趟，就將9排到了倒數(shù)第三位。

(4). 第四趟：

比較-1和3，不發(fā)生交換，結(jié)果是-1, 3, 9, 10, 20，同時(shí)兩個(gè)指針都后移一位；

經(jīng)過這趟，排序就結(jié)束了。

通過這個(gè)案例可以發(fā)現(xiàn)，總共需要進(jìn)行元素個(gè)數(shù)減一次排序，并且每次比較的個(gè)數(shù)都在減少。而且，上面第二趟交換了3和-1的位置后，其實(shí)整個(gè)數(shù)組就已經(jīng)是有序的了，后面的步驟都不用執(zhí)行了。

3、代碼實(shí)現(xiàn)：

public void sort(int[] arr) {
  // 外層控制控制要排序幾趟
  int temp = 0;
  for(int i=0; i<arr.length-1; i++) {
   boolean flag = false; // 如果某一趟中沒有一個(gè)元素發(fā)生交換，說明已經(jīng)有序了，flag用來標(biāo)識(shí)某一趟中是否發(fā)生過交換
   // 比較arr[j]和arr[j+1]的大小，如逆序，則交換。
   for(int j=0; j<arr.length-1-i; j++) {
    if (arr[j] > arr[j+1]) {
     temp = arr[j];
     arr[j] = arr[j+1];
     arr[j+1] = temp;
     flag = true;
    }
   }
   if (!flag) {
    break;
   }
  }
}

四、選擇排序

時(shí)間復(fù)雜度也是O(n^2)，但是經(jīng)測試，選擇排序速度會(huì)比冒泡排序更快。

1、排序思想：

第一趟，用arr[0]依次跟其他元素比較，如果比arr[0]更小，那就認(rèn)為該數(shù)最小，記住其下標(biāo)，讓其他元素跟該數(shù)比較，若又更小，那些又記住新的更小的那個(gè)數(shù)的下標(biāo)……第一趟完成后，就找到了最小的數(shù)，并讓它與arr[0]交換位置；
第二趟，用arr[1]跟其他元素比較，重復(fù)第一趟的步驟……

2、代碼實(shí)現(xiàn)：

public static void sort(int[] arr) {
  // 外層循環(huán)控制第幾趟比較
  for(int i=0; i<arr.length-1; i++) {
   int minNum = arr[i]; // 假定當(dāng)前元素是最小的
   int minNumIndex = i; // 最小值的下標(biāo)
   for(int j=i+1; j<arr.length; j++) {
    if (arr[j] < minNum) {
     // 如果arr[j]比之前認(rèn)為的最小值還小，就把它當(dāng)成新的最小值，并且記住下標(biāo)
     minNum = arr[j];
     minNumIndex = j;
    }
   }
   // 一輪下來，交換arr[i]和最小值的位置
   // 如果最小值索引minIndex就等于i，那就不用交換
   if (minNumIndex != i) {
    arr[minNumIndex] = arr[i];
    arr[i] = minNum;
   }
  }
}