|
0. 前言 大家好，我是多選參數(shù)的程序鍋，一個正在 neng 操作系統(tǒng)、學(xué)數(shù)據(jù)結(jié)構(gòu)和算法以及 Java 的硬核菜雞。數(shù)據(jù)結(jié)構(gòu)和算法是我準(zhǔn)備新開的坑，主要是因為自己在這塊確實很弱，需要大補（殘廢了一般）。這個坑以排序為開端，介紹了 7 種最經(jīng)典、最常用的排序算法，分別是：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、桶排序、計數(shù)排序、基數(shù)排序。對應(yīng)的時間復(fù)雜度如下所示：
整篇文章的主要知識提綱如圖所示：  接下去所用到的圖都來自于極客時間王爭的專欄《數(shù)據(jù)結(jié)構(gòu)與算法之美》，因為圖太好看了。 1. 排序算法分析學(xué)習(xí)排序算法除了學(xué)習(xí)它的算法原理、代碼實現(xiàn)之外，最重要的是學(xué)會如何評價、分析一個排序算法。分析一個排序算法通常從以下幾點出發(fā)。 1.1. 執(zhí)行效率而對執(zhí)行效率的分析，一般從這幾個方面來衡量：
1.2. 內(nèi)存消耗內(nèi)存消耗其實就是空間復(fù)雜度。針對排序算法來說，如果該排序算法的空間復(fù)雜度為 O(1)，那么這個排序算法又稱為原地排序。 1.3. 穩(wěn)定性是什么 穩(wěn)定性是指待排序的序列中存在值相等的元素。在排序之后，相等元素的前后順序跟排序之前的是一樣的。 為什么 我們將排序的原理和實現(xiàn)排序時用的大部分都是整數(shù)，但是實際開發(fā)過程中要排序的往往是一組對象，而我們只是按照對象中的某個 key 來進行排序。 比如一個對象有兩個屬性，下單時間和訂單金額。在存入到數(shù)據(jù)庫的時候，這些對象已經(jīng)按照時間先后的順序存入了。但是我們現(xiàn)在要以訂單金額為主要 key，在訂單金額相同的時候，以下單時間為 key。那么在采用穩(wěn)定的算法之后，只需要按照訂單金額進行一次排序即可。比如有這么三個數(shù)據(jù)，第一個數(shù)據(jù)是下單時間、第二數(shù)據(jù)是訂單金額：（20200515、20）、（20200516、10）、（20200517、30）、（20200518、20）。在采用穩(wěn)定的算法之后，排序的情況如下：（20200516、10）、(20200515、20)、（20200518、20）、（20200517、30）可以發(fā)現(xiàn)在訂單金額相同的情況下是按訂單時間進行排序的。 2. 經(jīng)典的常用排序算法2.1. 冒泡排序冒泡排序就是依次對兩個相鄰的元素進行比較，然后在不滿足大小條件的情況下進行元素交換。一趟冒泡排序下來至少會讓一個元素排好序（元素排序好的區(qū)域相當(dāng)于有序區(qū)，因此冒泡排序中相當(dāng)于待排序數(shù)組分成了兩個已排序區(qū)間和未排序區(qū)間）。因此為了將 n 個元素排好序，需要 n-1 趟冒泡排序（第 n 趟的時候就不需要）。 下面用冒泡排序?qū)@么一組數(shù)據(jù)4、5、6、3、2、1，從小到大進行排序。第一次排序情況如下：  img 可以看出，經(jīng)過一次冒泡操作之后，6 這個元素已經(jīng)存儲在正確的位置上了，要想完成有所有數(shù)據(jù)的排序，我們其實只需要 5 次這樣的冒泡排序就行了。圖中給出的是帶第 6 次了的，但是第 6 次其實沒必要。 
2.1.1. 優(yōu)化使用冒泡排序的過程中，如果有一趟冒泡過程中元素之間沒有發(fā)生交換，那么就說明已經(jīng)排序好了，可以直接退出不再繼續(xù)執(zhí)行后續(xù)的冒泡操作了。 2.1.2. 實現(xiàn)下面的冒泡排序?qū)崿F(xiàn)是優(yōu)化之后的： /** * 冒泡排序： * 以升序為例，就是比較相鄰兩個數(shù)，如果逆序就交換，類似于冒泡； * 一次冒泡確定一個數(shù)的位置，因為要確定 n-1 個數(shù)，因此需要 n-1 * 次冒泡； * 冒泡排序時，其實相當(dāng)于把整個待排序序列分為未排序區(qū)和已排序區(qū) */ public void bubbleSort(int[] arr, int len) { // len-1 趟
for (int j = 0; j < len-1; j++) { int sortedFlag = 0; // 一趟冒泡
for (int i = 0; i < len-1-j; i++) { if (arr[i] > arr[i+1]) { int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
sortedFlag = 1;
}
} // 該趟排序中沒有發(fā)生，表示已經(jīng)有序
if (0 == sortedFlag) { break;
}
}
}
2.1.3. 算法分析
2.2. 插入排序**插入排序中將數(shù)組中的元素分成兩個區(qū)間：已排序區(qū)間和未排序區(qū)間（最開始的時候已排序區(qū)間的元素只有數(shù)組的第一個元素），插入排序就是將未排序區(qū)間的元素依次插入到已排序區(qū)間（需要保持已排序區(qū)間的有序）。最終整個數(shù)組都是已排序區(qū)間，即排序好了。**假設(shè)要對 n 個元素進行排序，那么未排序區(qū)間的元素個數(shù)為 n-1，因此需要 n-1 次插入。插入位置的查找可以從尾到頭遍歷已排序區(qū)間也可以從頭到尾遍歷已排序區(qū)間。 如圖所示，假設(shè)要對 4、5、6、1、3、2進行排序。左側(cè)橙紅色表示的是已排序區(qū)間，右側(cè)黃色的表示未排序區(qū)間。整個插入排序過程如下所示  img 2.2.1. 優(yōu)化
2.2.2. 實現(xiàn)這邊查找插入位置的方式采用從尾到頭遍歷已排序區(qū)間，也沒有使用哨兵。 /** * 插入排序： * 插入排序也相當(dāng)于把待排序序列分成已排序區(qū)和未排序區(qū)； * 每趟排序都將從未排序區(qū)選擇一個元素插入到已排序合適的位置； * 假設(shè)第一個元素屬于已排序區(qū)，那么還需要插入 len-1 趟； */ public void insertSort(int[] arr, int len) { // len-1 趟
for (int i = 1; i < len; i++) { // 一趟排序
int temp = arr[i]; int j; for (j = i-1; j >= 0; j--) { if (arr[j] > temp) {
arr[j+1] = arr[j];
} else { break;
}
}
arr[j+1] = temp;
}
}
2.2.3. 算法分析
2.2.4. VS 冒泡排序冒泡排序和插入排序的時間復(fù)雜度都是 O(n^2)，都是原地穩(wěn)定排序。而且冒泡排序不管怎么優(yōu)化，元素交換的次數(shù)是一個固定值，是原始數(shù)據(jù)的逆序度。插入排序是同樣的，不管怎么優(yōu)化，元素移動的次數(shù)也等于原始數(shù)據(jù)的逆序度。但是，從代碼的實現(xiàn)上來看，冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動要復(fù)雜，冒泡排序需要 3 個賦值操作，而插入排序只需要一個賦值操作。所以，雖然冒泡排序和插入排序在時間復(fù)雜度上都是 O(n^2)，但是如果希望把性能做到極致，首選插入排序。其實該點分析的主要出發(fā)點就是在同階復(fù)雜度下，需要考慮系數(shù)、常數(shù)、低階等。 2.3. 選擇排序選擇排序也分為已排序區(qū)間和未排序區(qū)間（剛開始的已排序區(qū)間沒有數(shù)據(jù)），選擇排序每趟都會從未排序區(qū)間中找到最小的值（從小到大排序的話）放到已排序區(qū)間的末尾。 
2.3.1. 實現(xiàn)/** * 選擇排序： * 選擇排序?qū)⒋判蛐蛄蟹殖晌磁判騾^(qū)和已排序區(qū)； * 第一趟排序的時候整個待排序序列是未排序區(qū)； * 每一趟排序其實就是從未排序區(qū)選擇一個最值，放到已排序區(qū)； * 跑 len-1 趟就好 */ public void switchSort(int[] arr, int len) { // len-1 趟，0-i 為已排序區(qū)
for (int i = 0; i < len-1; i++) { int minIndex = i; for (int j = i+1; j < len; j++) { if (arr[j] < arr[minIndex]) {
minIndex = j;
}
} if (minIndex != i) { int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
2.3.2. 算法分析
2.4. 歸并排序（Merge Sort）**歸并排序的核心思想就是我要對一個數(shù)組進行排序：首先將數(shù)組分成前后兩部分，然后對兩部分分別進行排序，排序好之后再將兩部分合在一起，那整個數(shù)組就是有序的了。對于分出的兩部分可以采用相同的方式進行排序。**這個思想就是分治的思想，就是先將大問題分解成小的子問題來解決，子問題解決之后，大問題也就解決了。而對于子問題的求解也是一樣的套路。這個套路有點類似于遞歸的方式，所以分治算法一般使用遞歸來實現(xiàn)。分治是一種解決問題的處理思想，而遞歸是一種實現(xiàn)它的編程方法。 2.4.1. 實現(xiàn)下面使用遞歸的方式來實現(xiàn)歸并排序。遞歸的遞推公式是：merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))，終止條件是 p>=r，不再遞歸下去了。整個實現(xiàn)過程是先調(diào)用 /**
* 歸并排序 */public void mergeSort(int[] arr, int len) {
__mergerSort(arr, 0, len-1);
}private void __mergerSort(int[] arr, int begin, int end) { if (begin == end){ return;
}
__mergerSort(arr, begin, (begin+end)/2);
__mergerSort(arr, (begin+end)/2 + 1, end);
merge(arr, begin, end); return;
}private void merge(int[] arr, int begin, int end) { int[] copyArr = new int[end-begin+1];
System.arraycopy(arr, begin, copyArr, 0, end-begin+1); int mid = (end - begin + 1)/2; int i = 0; // begin - mid 的指針
int j = mid; // mid - end 的指針
int count = begin; // 合并之后數(shù)組的指針
while (i <= mid-1 && j <= end - begin) {
arr[count++] = copyArr[i] < copyArr[j] ? copyArr[i++] : copyArr[j++];
} while (i <= mid-1) {
arr[count++] = copyArr[i++];
} while (j <= end - begin) {
arr[count++] = copyArr[j++];
}
}
2.4.2. 算法分析
T(n)=Cn+nlonn2 ，使用大 O 時間復(fù)雜表示 T(n)=O(nlogn)。 歸并排序中，無論待排數(shù)列是有序還是倒序，最終遞歸的層次都是到只有一個數(shù)組為主，所以歸并排序跟待排序列沒有什么關(guān)系，最好、最壞、平均的時間復(fù)雜度都是 O(nlogn)。
2.5. 快速排序（Quick Sort）快速排序利用的也是分治思想，核心思想是從待排數(shù)組中選擇一個元素，然后將待排數(shù)組劃分成兩個部分：左邊部分的元素都小于該元素的值，右邊部分的元素都大于該元素的值，中間是該元素的值。然后對左右兩個部分套用相同的處理方法，也就是將左邊部分的元素再劃分成左右兩部分，右邊部分的元素也再劃分成左右兩部分。以此類推，當(dāng)遞歸到只有一個元素的時候，就說明此時數(shù)組是有序了的。 2.5.1. 實現(xiàn)首先要對下標(biāo)從 begin 到 end 之間的數(shù)據(jù)進行分區(qū)，可以選擇 begin 到 end 之間的任意一個數(shù)據(jù)作為 pivot（分區(qū)點），一般是最后一個數(shù)據(jù)作為分區(qū)點。之后遍歷 begin 到 end 之間的數(shù)據(jù)，將小于 pivot 的放在左邊，大于的 pivot 的放在右邊，將pivot 放在中間（位置 p）。經(jīng)過這一操作之后，數(shù)組 begin 到 end 之間的數(shù)據(jù)就被分成了三個部分：begin 到 p-1、p、p+1 到 end。最后，返回 pivot 的下標(biāo)。那么這個過程一般有三種方式：
在返回 pivot 的下標(biāo) q 之后，再根據(jù)分治的思想，將 begin 到 q-1 之間的數(shù)據(jù)和下標(biāo) q+1 到 end 之間的數(shù)據(jù)進行遞歸。這邊一定要 q-1 和 q+1 而不能是 q 和 q+1 是因為：考慮數(shù)據(jù)已經(jīng)有序的極端情況，一開始是對 begin 到 end；當(dāng)分區(qū)之后 q 的位置還是 end 的位置，那么相當(dāng)于死循環(huán)了。最終，當(dāng)區(qū)間縮小至 1 時，說明所有的數(shù)據(jù)都有序了。 如果用遞推公式來描述上述的過程的話，遞推公式：quick_sort(begin...end) = quick_sort(begin...q-1) + quick_sort(q+1...end)，終止條件是：begin >= end。將這兩個公式轉(zhuǎn)化為代碼之后，如下所示： /**
* 快速排序 */public void quickSort(int[] arr, int len) {
__quickSort(arr, 0, len-1);
}// 注意邊界條件private void __quickSort(int[] arr, int begin, int end) { if (begin >= end) { return;
} // 一定要是 p-1！
int p = partition(arr, begin, end); // 先進行大致排序，并獲取區(qū)分點
__quickSort(arr, begin, p-1);
__quickSort(arr, p+1, end);
}private int partition(int[] arr, int begin, int end) { int pValue = arr[end]; // 整兩個指針，兩個指針都從頭開始 // begin --- i-1（含 i-1）：小于 pValue 的區(qū) // i --- j-1（含 j-1）：大于 pValue 的區(qū) // j --- end：未排序區(qū)
int i = begin; int j = begin; while (j <= end) { if (arr[j] <= pValue) { int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
j++;
} else {
j++;
}
} return i-1;
}
2.5.2. 優(yōu)化
2.5.3. 算法分析
2.5.4. VS 歸并排序首先從思想上來看：歸并排序的處理過程是由下到上的，先處理子問題，然后對子問題的解再合并；而快排正好相反，處理過程是由上到下的，先分區(qū)，再處理子問題。 從性能上來看：歸并是一個穩(wěn)定的、時間復(fù)雜度為 O(nlogn) 的排序算法，但是歸并并不是一個原地排序算法（所以歸并沒有快排應(yīng)用廣泛）。而快速排序算法時間復(fù)雜度不一定是 O(nlogn)，最壞情況下是 O(n^2)，而且不是一個穩(wěn)定的算法，但是通過設(shè)計可以讓快速排序成為一個原地排序算法。 2.6. 桶排序**桶排序的核心思想就是將要排序的數(shù)據(jù)分到幾個有序的桶里，每個桶里的數(shù)據(jù)再單獨進行排序。**桶內(nèi)排序完成之后，再把每個桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。一般步驟是：
2.6.1. 實現(xiàn)public void buckerSort(int[] arr, int len, int bucketCount) { // 確定數(shù)據(jù)的范圍
int minVal = arr[0]; int maxVal = arr[0]; for (int i = 1; i < len; ++i) { if (arr[i] < minVal) {
minVal = arr[i];
} else if (arr[i] > maxVal){
maxVal = arr[i];
}
} // 確認(rèn)每個桶的所表示的范圍
bucketCount = (maxVal - minVal + 1) < bucketCount ? (maxVal - minVal + 1) : bucketCount; int bucketSize = (maxVal - minVal + 1) / bucketCount;
bucketCount = (maxVal - minVal + 1) % bucketCount == 0 ? bucketCount : bucketCount + 1; int[][] buckets = new int[bucketCount][bucketSize]; int[] indexArr = new int[bucketCount]; // 數(shù)組位置記錄 // 將數(shù)據(jù)依次放入桶中
for (int i = 0; i < len; i++) { int bucketIndex = (arr[i] - minVal) / bucketSize; if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
expandCapacity(buckets, bucketIndex);
}
buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
} // 桶內(nèi)排序
for (int i = 0; i < bucketCount; ++i) { if (indexArr[i] != 0) {
quickSort(buckets[i], 0, indexArr[i] - 1);
}
} // 桶內(nèi)數(shù)據(jù)依次取出
int index = 0; for (int i = 0; i < bucketCount; ++i) { for (int j = 0; j < indexArr[i]; ++j) {
arr[index++] = buckets[i][j];
}
} // 打印
for (int i = 0; i < len; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}// 對數(shù)組進行擴容public void expandCapacity(int[][] buckets, int bucketIndex) { int[] newArr = new int[buckets[bucketIndex].length * 2];
System.arraycopy(buckets[bucketIndex], 0, newArr, 0, buckets[bucketIndex].length);
buckets[bucketIndex] = newArr;
}
2.6.2. 算法分析
2.6.3. 總結(jié)
2.7. 計數(shù)排序計數(shù)排序跟桶排序類似，可以說計數(shù)排序其實是桶排序的一種特殊情況。**當(dāng)要排序的 n 個數(shù)據(jù)，所處的范圍并不大的時候，比如最大值是 K，那么就可以把數(shù)據(jù)劃分到 K 個桶，每個桶內(nèi)的數(shù)據(jù)值都是相同的，**從而省掉了桶內(nèi)排序的時間?？梢哉f計數(shù)排序和桶排序的區(qū)別其實也就在于桶的大小粒度不一樣。 下面通過舉例子的方式來看一下計數(shù)排序的過程。假設(shè)數(shù)組 A 中有 8 個數(shù)據(jù)，值在 0 到 5 之間，分別是：2、5、3、0、2、3、0、3。
2.7.1. 實現(xiàn)/**
* 計數(shù)排序，暫時只能處理整數(shù)（包括整數(shù)和負(fù)數(shù)）
* @param arr
* @param len */public void countingSort(int[] arr, int len) { // 確定范圍
int minVal = arr[0]; int maxVal = arr[0]; for (int i = 1; i < len; ++i) { if (maxVal < arr[i]) {
maxVal = arr[i];
} else if (arr[i] < minVal) {
minVal = arr[i];
}
} // 對數(shù)據(jù)進行處理
for (int i = 0; i < len; ++i) {
arr[i] = arr[i] - minVal;
}
maxVal = maxVal - minVal; // 遍歷數(shù)據(jù)數(shù)組，求得計數(shù)數(shù)組的個數(shù)
int[] count = new int[maxVal + 1]; for (int i = 0; i < len; ++i) {
count[arr[i]] ++;
}
printAll(count, maxVal + 1); // 對計數(shù)數(shù)組進行優(yōu)化
for (int i = 1; i < maxVal + 1; ++i) {
count[i] = count[i - 1] + count[i];
}
printAll(count, maxVal + 1); // 進行排序，從后往前遍歷（為了穩(wěn)定）
int[] sort = new int[len]; for (int i = len - 1; i >= 0; --i) {
sort[count[arr[i]] - 1] = arr[i] + minVal;
count[arr[i]]--;
}
printAll(sort, len);
}
2.7.2. 算法分析
2.7.3. 總結(jié)
2.8. 基數(shù)排序桶排序和計數(shù)排序都適合范圍不是特別大的情況（請注意是范圍），但是桶排序的范圍可以比計數(shù)排序的范圍稍微大一點。假如數(shù)據(jù)的范圍很大很大，比如對手機號這種的，桶排序和技術(shù)排序顯然不適合，因為需要的桶的數(shù)量也是十分巨大的。此時，可以使用基數(shù)排序。**基數(shù)排序的思想就是將要排序的數(shù)據(jù)拆分成位，然后逐位按照先后順序進行比較。**比如手機號中就可以從后往前，先按照手機號最后一位來進行排序，之后再按照倒數(shù)第二位來進行排序，以此類推。當(dāng)按照第一位重新排序之后，整個排序就算完成了。 需要注意的是**，按照每位排序的過程需要穩(wěn)定的**，因為假如后一次的排序不穩(wěn)定，前一次的排序結(jié)果將功虧一簣。比如，第一次對個位進行排序結(jié)果為 21、11、42、22、62，此時 21 在 22 前面；第二次對十位的排序假如是不穩(wěn)定的話，22 可能跑到 21 前面去了。那么整個排序就錯了，對個位的排序也就相當(dāng)于白費了。 下面舉個字符串的例子，整個基數(shù)排序的過程如下圖所示： 
2.8.1. 實現(xiàn)/**
* 基數(shù)排序
* @param arr
* @param len */public void radixSort(int[] arr, int len, int bitCount) { int exp = 1; for (int i = 0; i < bitCount; ++i) {
countingSort(arr, len, exp);
exp = exp * 10;
}
}public int getBit(int value, int exp) { return (value / exp) % 10;
}/**
* 計數(shù)排序，暫時只能處理整數(shù)（包括整數(shù)和負(fù)數(shù)）
* @param arr
* @param len */public void countingSort(int[] arr, int len, int exp) { // 確定范圍
int maxVal = getBit(arr[0], exp); for (int i = 1; i < len; ++i) { if (maxVal < getBit(arr[i], exp)) {
maxVal = getBit(arr[i], exp);
}
} // 遍歷數(shù)據(jù)數(shù)組，求得計數(shù)數(shù)組的個數(shù)
int[] count = new int[maxVal + 1]; for (int i = 0; i < len; ++i) {
count[getBit(arr[i], exp)] ++;
} // 對計數(shù)數(shù)組進行優(yōu)化
for (int i = 1; i < maxVal + 1; ++i) {
count[i] = count[i - 1] + count[i];
} // 進行排序，從后往前遍歷（為了穩(wěn)定）
int[] sort = new int[len]; for (int i = len - 1; i >= 0; --i) {
sort[count[getBit(arr[i], exp)] - 1] = arr[i];
count[getBit(arr[i], exp)]--;
}
System.arraycopy(sort, 0, arr, 0, len);
printAll(sort, len);
}
2.8.2. 算法分析
2.8.3. 總結(jié)
3. 排序函數(shù)幾乎所有編程語言都會提供排序函數(shù)，比如 C 語言中 qsort()、C++ STL 中的 sort()/stable_sort()、Java 中的 Collections.sort()。這些排序函數(shù)，并不會只采用一種排序算法，而是多種排序算法的結(jié)合。當(dāng)然主要使用的排序算法都是 O(nlogn) 的。
4. 附加知識4.1. 有序度、逆序度在以從小到大為有序的情況中，有序度是數(shù)組中有序關(guān)系的元素對的個數(shù)，用數(shù)學(xué)公式表示如下所示。 如果 i < j，那么 a[i] < a[j]
比如 2、4、3、1、5、6 這組數(shù)據(jù)的有序度是 11；倒序排列的數(shù)組，有序度是 0；一個完全有序的數(shù)組，有序度為滿有序度，為 n*(n-1)/2，比如1、2、3、4、5、6，有序度就是 15。 逆序度的定義正好跟有序度的定義相反 如果 i < j，那么 a[i] > a[j]
關(guān)于逆序度、有序度、滿有序度滿足如下公式 逆序度 = 滿有序度 - 有序度
排序的過程其實就是減少逆序度，增加有序度的過程，如果待排序序列達(dá)到滿有序度了，那么此時的序列就是有序了。 5. 總結(jié)
有完整的Java初級，高級對應(yīng)的學(xué)習(xí)路線和資料！專注于java開發(fā)。分享java基礎(chǔ)、原理性知識、JavaWeb實戰(zhàn)、spring全家桶、設(shè)計模式、分布式及面試資料、開源項目，助力開發(fā)者成長！
轉(zhuǎn)載于：作者：syy 鏈接：https://cloud.tencent.com/developer/article/1650030?from=information.detail.%E5%AD%A6java%E9%9C%80%E8%A6%81%E5%AD%A6%E7%AE%97%E6%B3%95%E5%90%97 來源：騰訊云/侵刪 |
|
|
