冒泡排序
要點(diǎn)
冒泡排序是一種交換排序。
什么是交換排序呢？
交換排序：兩兩比較待排序的關(guān)鍵字，并交換不滿足次序要求的那對(duì)數(shù)，直到整個(gè)表都滿足次序要求為止。
算法思想
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。
假設(shè)有一個(gè)大小為 N 的無序序列。冒泡排序就是要每趟排序過程中通過兩兩比較，找到第 i 個(gè)小（大）的元素，將其往上排。
以上圖為例，演示一下冒泡排序的實(shí)際流程：
假設(shè)有一個(gè)無序序列 { 4. 3. 1. 2, 5 }
- 第一趟排序：通過兩兩比較，找到第一小的數(shù)值 1 ，將其放在序列的第一位。
- 第二趟排序：通過兩兩比較，找到第二小的數(shù)值 2 ，將其放在序列的第二位。
- 第三趟排序：通過兩兩比較，找到第三小的數(shù)值 3 ，將其放在序列的第三位。
至此，所有元素已經(jīng)有序，排序結(jié)束。
要將以上流程轉(zhuǎn)化為代碼，我們需要像機(jī)器一樣去思考，不然編譯器可看不懂。
- 假設(shè)要對(duì)一個(gè)大小為 N 的無序序列進(jìn)行升序排序（即從小到大）。
- 每趟排序過程中需要通過比較找到第 i 個(gè)小的元素。
- 所以，我們需要一個(gè)外部循環(huán)，從數(shù)組首端(下標(biāo) 0) 開始，一直掃描到倒數(shù)第二個(gè)元素（即下標(biāo) N - 2) ，剩下最后一個(gè)元素，必然為最大。
- 假設(shè)是第 i 趟排序，可知，前 i-1 個(gè)元素已經(jīng)有序。現(xiàn)在要找第 i 個(gè)元素，只需從數(shù)組末端開始，掃描到第 i 個(gè)元素，將它們兩兩比較即可。
- 所以，需要一個(gè)內(nèi)部循環(huán)，從數(shù)組末端開始（下標(biāo) N - 1），掃描到 (下標(biāo) i + 1)。
核心代碼
public void bubbleSort(int[] list) {
int temp = 0; // 用來交換的臨時(shí)數(shù)
// 要遍歷的次數(shù)
for (int i = 0; i < list.length - 1; i++) {
// 從后向前依次的比較相鄰兩個(gè)數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個(gè)位置上
for (int j = list.length - 1; j > i; j--) {
// 比較相鄰的元素，如果前面的數(shù)大于后面的數(shù)，則交換
if (list[j - 1] > list[j]) {
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
}
}
System.out.format("第 %d 趟：t", i);
printAll(list);
}
}
復(fù)制代碼
算法分析
冒泡排序算法的性能
參數(shù) 結(jié)果 排序類別 交換排序 排序方法 冒泡排序 時(shí)間復(fù)雜度平均情況 O(N2) 時(shí)間復(fù)雜度最壞情況 O(N3) 時(shí)間復(fù)雜度最好情況 O(N) 空間復(fù)雜度 O(1) 穩(wěn)定性 穩(wěn)定 復(fù)雜性 簡單 時(shí)間復(fù)雜度
若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù) C 和記錄移動(dòng)次數(shù) M 均達(dá)到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好時(shí)間復(fù)雜度為 O(N)。
若初始文件是反序的，需要進(jìn)行 N -1 趟排序。每趟排序要進(jìn)行 N - i 次關(guān)鍵字的比較(1 ≤ i ≤ N - 1)，且每次比較都必須移動(dòng)記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值：
Cmax = N(N-1)/2 = O(N2)
Mmax = 3N(N-1)/2 = O(N2)
冒泡排序的最壞時(shí)間復(fù)雜度為 O(N2)。
因此，冒泡排序的平均時(shí)間復(fù)雜度為 O(N2)。
總結(jié)起來，其實(shí)就是一句話：當(dāng)數(shù)據(jù)越接近正序時(shí)，冒泡排序性能越好。
算法穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。
所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。
優(yōu)化
對(duì)冒泡排序常見的改進(jìn)方法是加入標(biāo)志性變量 exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換。
如果進(jìn)行某一趟排序時(shí)并沒有進(jìn)行數(shù)據(jù)交換，則說明所有數(shù)據(jù)已經(jīng)有序，可立即結(jié)束排序，避免不必要的比較過程。
核心代碼
// 對(duì) bubbleSort 的優(yōu)化算法
public void bubbleSort_2(int[] list) {
int temp = 0; // 用來交換的臨時(shí)數(shù)
boolean bChange = false; // 交換標(biāo)志
// 要遍歷的次數(shù)
for (int i = 0; i < list.length - 1; i++) {
bChange = false;
// 從后向前依次的比較相鄰兩個(gè)數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個(gè)位置上
for (int j = list.length - 1; j > i; j--) {
// 比較相鄰的元素，如果前面的數(shù)大于后面的數(shù)，則交換
if (list[j - 1] > list[j]) {
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
bChange = true;
}
}
// 如果標(biāo)志為false，說明本輪遍歷沒有交換，已經(jīng)是有序數(shù)列，可以結(jié)束排序
if (false == bChange)
break;
System.out.format("第 %d 趟：t", i);
printAll(list);
}
}
復(fù)制代碼
示例代碼
我的 Github 測試?yán)?/p>
樣本包含：數(shù)組個(gè)數(shù)為奇數(shù)、偶數(shù)的情況；元素重復(fù)或不重復(fù)的情況。且樣本均為隨機(jī)樣本，實(shí)測有效。
快速排序
要點(diǎn)
快速排序是一種交換排序。
快速排序由 C. A. R. Hoare 在 1962 年提出。
算法思想
它的基本思想是：
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分：分割點(diǎn)左邊都是比它小的數(shù)，右邊都是比它大的數(shù)。
然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
詳細(xì)的圖解往往比大堆的文字更有說明力，所以直接上圖：
上圖中，演示了快速排序的處理過程：
- 初始狀態(tài)為一組無序的數(shù)組：2、4、5、1、3。
- 經(jīng)過以上操作步驟后，完成了第一次的排序，得到新的數(shù)組：1、2、5、4、3。
- 新的數(shù)組中，以 2 為分割點(diǎn)，左邊都是比 2 小的數(shù)，右邊都是比 2 大的數(shù)。
- 因?yàn)?2 已經(jīng)在數(shù)組中找到了合適的位置，所以不用再動(dòng)。
- 2 左邊的數(shù)組只有一個(gè)元素 1，所以顯然不用再排序，位置也被確定。（注：這種情況時(shí)，left 指針和 right 指針顯然是重合的。因此在代碼中，我們可以通過設(shè)置判定條件 left 必須小于 right，如果不滿足，則不用排序了）。
- 而對(duì)于 2 右邊的數(shù)組 5、4、3，設(shè)置 left 指向 5，right 指向 3，開始繼續(xù)重復(fù)圖中的一、二、三、四步驟，對(duì)新的數(shù)組進(jìn)行排序。
核心代碼
public int division(int[] list, int left, int right) {
// 以最左邊的數(shù)(left)為基準(zhǔn)
int base = list[left];
while (left < right) {
// 從序列右端開始，向左遍歷，直到找到小于base的數(shù)
while (left < right && list[right] >= base)
right--;
// 找到了比base小的元素，將這個(gè)元素放到最左邊的位置
list[left] = list[right];
// 從序列左端開始，向右遍歷，直到找到大于base的數(shù)
while (left < right && list[left] <= base)
left++;
// 找到了比base大的元素，將這個(gè)元素放到最右邊的位置
list[right] = list[left];
}
// 最后將base放到left位置。此時(shí)，left位置的左側(cè)數(shù)值應(yīng)該都比left小；
// 而left位置的右側(cè)數(shù)值應(yīng)該都比left大。
list[left] = base;
return left;
}
private void quickSort(int[] list, int left, int right) {
// 左下標(biāo)一定小于右下標(biāo)，否則就越界了
if (left < right) {
// 對(duì)數(shù)組進(jìn)行分割，取出下次分割的基準(zhǔn)標(biāo)號(hào)
int base = division(list, left, right);
System.out.format("base = %d:t", list[base]);
printPart(list, left, right);
// 對(duì)“基準(zhǔn)標(biāo)號(hào)“左側(cè)的一組數(shù)值進(jìn)行遞歸的切割，以至于將這些數(shù)值完整的排序
quickSort(list, left, base - 1);
// 對(duì)“基準(zhǔn)標(biāo)號(hào)“右側(cè)的一組數(shù)值進(jìn)行遞歸的切割，以至于將這些數(shù)值完整的排序
quickSort(list, base + 1, right);
}
}
復(fù)制代碼
算法分析
快速排序算法的性能
參數(shù) 結(jié)果 排序類別 交換排序 排序方法 快速排序 時(shí)間復(fù)雜度平均情況 O(Nlog2N) 時(shí)間復(fù)雜度最壞情況 O(N2) 時(shí)間復(fù)雜度最好情況 O(Nlog2N) 空間復(fù)雜度 O(Nlog2N) 穩(wěn)定性 不穩(wěn)定 復(fù)雜性 較復(fù)雜 時(shí)間復(fù)雜度
當(dāng)數(shù)據(jù)有序時(shí)，以第一個(gè)關(guān)鍵字為基準(zhǔn)分為兩個(gè)子序列，前一個(gè)子序列為空，此時(shí)執(zhí)行效率最差。
而當(dāng)數(shù)據(jù)隨機(jī)分布時(shí)，以第一個(gè)關(guān)鍵字為基準(zhǔn)分為兩個(gè)子序列，兩個(gè)子序列的元素個(gè)數(shù)接近相等，此時(shí)執(zhí)行效率最好。
所以，數(shù)據(jù)越隨機(jī)分布時(shí)，快速排序性能越好；數(shù)據(jù)越接近有序，快速排序性能越差。
空間復(fù)雜度
快速排序在每次分割的過程中，需要 1 個(gè)空間存儲(chǔ)基準(zhǔn)值。而快速排序的大概需要 Nlog2N 次的分割處理，所以占用空間也是 Nlog2N 個(gè)。
算法穩(wěn)定性
在快速排序中，相等元素可能會(huì)因?yàn)榉謪^(qū)而交換順序，所以它是不穩(wěn)定的算法。
