冒泡排序

要點

冒泡排序是一種交換排序。

什麼是交換排序呢？

交換排序：兩兩比較待排序的關鍵字，並交換不滿足次序要求的那對數，直到整個表都滿足次序要求為止。

算法思想

它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，故名。

假設有一個大小為 N 的無序序列。冒泡排序就是要每趟排序過程中通過兩兩比較，找到第 i 個小（大）的元素，將其往上排。

以上圖為例，演示一下冒泡排序的實際流程：

假設有一個無序序列 { 4. 3. 1. 2, 5 }

• 第一趟排序：通過兩兩比較，找到第一小的數值 1 ，將其放在序列的第一位。
• 第二趟排序：通過兩兩比較，找到第二小的數值 2 ，將其放在序列的第二位。
• 第三趟排序：通過兩兩比較，找到第三小的數值 3 ，將其放在序列的第三位。

至此，所有元素已經有序，排序結束。

要將以上流程轉化為代碼，我們需要像機器一樣去思考，不然編譯器可看不懂。

• 假設要對一個大小為 N 的無序序列進行升序排序（即從小到大）。
• 每趟排序過程中需要通過比較找到第 i 個小的元素。
• 所以，我們需要一個外部循環，從數組首端(下標 0) 開始，一直掃描到倒數第二個元素（即下標 N - 2) ，剩下最後一個元素，必然為最大。
• 假設是第 i 趟排序，可知，前 i-1 個元素已經有序。現在要找第 i 個元素，只需從數組末端開始，掃描到第 i 個元素，將它們兩兩比較即可。
• 所以，需要一個內部循環，從數組末端開始（下標 N - 1），掃描到 (下標 i + 1)。

核心代碼

public void bubbleSort(int[] list) {

int temp = 0; // 用來交換的臨時數

// 要遍歷的次數

for (int i = 0; i < list.length - 1; i++) {

// 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把數組中第i小的數放在第i個位置上

for (int j = list.length - 1; j > i; j--) {

// 比較相鄰的元素，如果前面的數大於後面的數，則交換

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);

}

}

複製代碼

算法分析

冒泡排序算法的性能

參數 結果 排序類別 交換排序 排序方法 冒泡排序 時間複雜度平均情況 O(N2) 時間複雜度最壞情況 O(N3) 時間複雜度最好情況 O(N) 空間複雜度 O(1) 穩定性 穩定 複雜性 簡單 時間複雜度

若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數 C 和記錄移動次數 M 均達到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好時間複雜度為 O(N)。

若初始文件是反序的，需要進行 N -1 趟排序。每趟排序要進行 N - i 次關鍵字的比較(1 ≤ i ≤ N - 1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：

Cmax = N(N-1)/2 = O(N2)

Mmax = 3N(N-1)/2 = O(N2)

冒泡排序的最壞時間複雜度為 O(N2)。

因此，冒泡排序的平均時間複雜度為 O(N2)。

總結起來，其實就是一句話：當數據越接近正序時，冒泡排序性能越好。

算法穩定性

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。

所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序算法。

優化

對冒泡排序常見的改進方法是加入標誌性變量 exchange，用於標誌某一趟排序過程中是否有數據交換。

如果進行某一趟排序時並沒有進行數據交換，則說明所有數據已經有序，可立即結束排序，避免不必要的比較過程。

核心代碼

// 對 bubbleSort 的優化算法

public void bubbleSort_2(int[] list) {

int temp = 0; // 用來交換的臨時數

boolean bChange = false; // 交換標誌

// 要遍歷的次數

for (int i = 0; i < list.length - 1; i++) {

bChange = false;

// 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把數組中第i小的數放在第i個位置上

for (int j = list.length - 1; j > i; j--) {

// 比較相鄰的元素，如果前面的數大於後面的數，則交換

if (list[j - 1] > list[j]) {

temp = list[j - 1];

list[j - 1] = list[j];

list[j] = temp;

bChange = true;

}

}

// 如果標誌為false，說明本輪遍歷沒有交換，已經是有序數列，可以結束排序

if (false == bChange)

break;

System.out.format("第 %d 趟：\\t", i);

printAll(list);

}

}

複製代碼

示例代碼

我的 Github 測試例

樣本包含：數組個數為奇數、偶數的情況；元素重複或不重複的情況。且樣本均為隨機樣本，實測有效。

快速排序

要點

快速排序是一種交換排序。

快速排序由 C. A. R. Hoare 在 1962 年提出。

算法思想

它的基本思想是：

通過一趟排序將要排序的數據分割成獨立的兩部分：分割點左邊都是比它小的數，右邊都是比它大的數。

然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

詳細的圖解往往比大堆的文字更有說明力，所以直接上圖：

上圖中，演示了快速排序的處理過程：

1. 初始狀態為一組無序的數組：2、4、5、1、3。
2. 經過以上操作步驟後，完成了第一次的排序，得到新的數組：1、2、5、4、3。
3. 新的數組中，以 2 為分割點，左邊都是比 2 小的數，右邊都是比 2 大的數。
4. 因為 2 已經在數組中找到了合適的位置，所以不用再動。
5. 2 左邊的數組只有一個元素 1，所以顯然不用再排序，位置也被確定。（注：這種情況時，left 指針和 right 指針顯然是重合的。因此在代碼中，我們可以通過設置判定條件 left 必須小於 right，如果不滿足，則不用排序了）。
6. 而對於 2 右邊的數組 5、4、3，設置 left 指向 5，right 指向 3，開始繼續重複圖中的一、二、三、四步驟，對新的數組進行排序。

核心代碼

public int division(int[] list, int left, int right) {

// 以最左邊的數(left)為基準

int base = list[left];

while (left < right) {

// 從序列右端開始，向左遍歷，直到找到小於base的數

while (left < right && list[right] >= base)

right--;

// 找到了比base小的元素，將這個元素放到最左邊的位置

list[left] = list[right];

// 從序列左端開始，向右遍歷，直到找到大於base的數

while (left < right && list[left] <= base)

left++;

// 找到了比base大的元素，將這個元素放到最右邊的位置

list[right] = list[left];

}

// 最後將base放到left位置。此時，left位置的左側數值應該都比left小；

// 而left位置的右側數值應該都比left大。

list[left] = base;

return left;

}

private void quickSort(int[] list, int left, int right) {

// 左下標一定小於右下標，否則就越界了

if (left < right) {

// 對數組進行分割，取出下次分割的基準標號

int base = division(list, left, right);

System.out.format("base = %d:\\t", list[base]);

printPart(list, left, right);

// 對“基準標號“左側的一組數值進行遞歸的切割，以至於將這些數值完整的排序

quickSort(list, left, base - 1);

// 對“基準標號“右側的一組數值進行遞歸的切割，以至於將這些數值完整的排序

quickSort(list, base + 1, right);

}

}

複製代碼

算法分析

快速排序算法的性能

參數 結果 排序類別 交換排序 排序方法 快速排序 時間複雜度平均情況 O(Nlog2N) 時間複雜度最壞情況 O(N2) 時間複雜度最好情況 O(Nlog2N) 空間複雜度 O(Nlog2N) 穩定性 不穩定 複雜性 較複雜 時間複雜度

當數據有序時，以第一個關鍵字為基準分為兩個子序列，前一個子序列為空，此時執行效率最差。

而當數據隨機分佈時，以第一個關鍵字為基準分為兩個子序列，兩個子序列的元素個數接近相等，此時執行效率最好。

所以，數據越隨機分佈時，快速排序性能越好；數據越接近有序，快速排序性能越差。

空間複雜度

快速排序在每次分割的過程中，需要 1 個空間存儲基準值。而快速排序的大概需要 Nlog2N 次的分割處理，所以佔用空間也是 Nlog2N 個。

算法穩定性

在快速排序中，相等元素可能會因為分區而交換順序，所以它是不穩定的算法。

最後，想學習大數據或者需要面試題的小夥伴們！

請關注+私信回覆：“學習”就可以拿到一份我為大家準備的學習資料！

"

冒泡排序

要點

冒泡排序是一種交換排序。

什麼是交換排序呢？

交換排序：兩兩比較待排序的關鍵字，並交換不滿足次序要求的那對數，直到整個表都滿足次序要求為止。

算法思想

它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，故名。

假設有一個大小為 N 的無序序列。冒泡排序就是要每趟排序過程中通過兩兩比較，找到第 i 個小（大）的元素，將其往上排。

以上圖為例，演示一下冒泡排序的實際流程：

假設有一個無序序列 { 4. 3. 1. 2, 5 }

• 第一趟排序：通過兩兩比較，找到第一小的數值 1 ，將其放在序列的第一位。
• 第二趟排序：通過兩兩比較，找到第二小的數值 2 ，將其放在序列的第二位。
• 第三趟排序：通過兩兩比較，找到第三小的數值 3 ，將其放在序列的第三位。

至此，所有元素已經有序，排序結束。

要將以上流程轉化為代碼，我們需要像機器一樣去思考，不然編譯器可看不懂。

• 假設要對一個大小為 N 的無序序列進行升序排序（即從小到大）。
• 每趟排序過程中需要通過比較找到第 i 個小的元素。
• 所以，我們需要一個外部循環，從數組首端(下標 0) 開始，一直掃描到倒數第二個元素（即下標 N - 2) ，剩下最後一個元素，必然為最大。
• 假設是第 i 趟排序，可知，前 i-1 個元素已經有序。現在要找第 i 個元素，只需從數組末端開始，掃描到第 i 個元素，將它們兩兩比較即可。
• 所以，需要一個內部循環，從數組末端開始（下標 N - 1），掃描到 (下標 i + 1)。

核心代碼

public void bubbleSort(int[] list) {

int temp = 0; // 用來交換的臨時數

// 要遍歷的次數

for (int i = 0; i < list.length - 1; i++) {

// 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把數組中第i小的數放在第i個位置上

for (int j = list.length - 1; j > i; j--) {

// 比較相鄰的元素，如果前面的數大於後面的數，則交換

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);

}

}

複製代碼

算法分析

冒泡排序算法的性能

參數 結果 排序類別 交換排序 排序方法 冒泡排序 時間複雜度平均情況 O(N2) 時間複雜度最壞情況 O(N3) 時間複雜度最好情況 O(N) 空間複雜度 O(1) 穩定性 穩定 複雜性 簡單 時間複雜度

若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數 C 和記錄移動次數 M 均達到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好時間複雜度為 O(N)。

若初始文件是反序的，需要進行 N -1 趟排序。每趟排序要進行 N - i 次關鍵字的比較(1 ≤ i ≤ N - 1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：

Cmax = N(N-1)/2 = O(N2)

Mmax = 3N(N-1)/2 = O(N2)

冒泡排序的最壞時間複雜度為 O(N2)。

因此，冒泡排序的平均時間複雜度為 O(N2)。

總結起來，其實就是一句話：當數據越接近正序時，冒泡排序性能越好。

算法穩定性

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。

所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序算法。

優化

對冒泡排序常見的改進方法是加入標誌性變量 exchange，用於標誌某一趟排序過程中是否有數據交換。

如果進行某一趟排序時並沒有進行數據交換，則說明所有數據已經有序，可立即結束排序，避免不必要的比較過程。

核心代碼

// 對 bubbleSort 的優化算法

public void bubbleSort_2(int[] list) {

int temp = 0; // 用來交換的臨時數

boolean bChange = false; // 交換標誌

// 要遍歷的次數

for (int i = 0; i < list.length - 1; i++) {

bChange = false;

// 從後向前依次的比較相鄰兩個數的大小，遍歷一次後，把數組中第i小的數放在第i個位置上

for (int j = list.length - 1; j > i; j--) {

// 比較相鄰的元素，如果前面的數大於後面的數，則交換

if (list[j - 1] > list[j]) {

temp = list[j - 1];

list[j - 1] = list[j];

list[j] = temp;

bChange = true;

}

}

// 如果標誌為false，說明本輪遍歷沒有交換，已經是有序數列，可以結束排序

if (false == bChange)

break;

System.out.format("第 %d 趟：\\t", i);

printAll(list);

}

}

複製代碼

示例代碼

我的 Github 測試例

樣本包含：數組個數為奇數、偶數的情況；元素重複或不重複的情況。且樣本均為隨機樣本，實測有效。

快速排序

要點

快速排序是一種交換排序。

快速排序由 C. A. R. Hoare 在 1962 年提出。

算法思想

它的基本思想是：

通過一趟排序將要排序的數據分割成獨立的兩部分：分割點左邊都是比它小的數，右邊都是比它大的數。

然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

詳細的圖解往往比大堆的文字更有說明力，所以直接上圖：

上圖中，演示了快速排序的處理過程：

1. 初始狀態為一組無序的數組：2、4、5、1、3。
2. 經過以上操作步驟後，完成了第一次的排序，得到新的數組：1、2、5、4、3。
3. 新的數組中，以 2 為分割點，左邊都是比 2 小的數，右邊都是比 2 大的數。
4. 因為 2 已經在數組中找到了合適的位置，所以不用再動。
5. 2 左邊的數組只有一個元素 1，所以顯然不用再排序，位置也被確定。（注：這種情況時，left 指針和 right 指針顯然是重合的。因此在代碼中，我們可以通過設置判定條件 left 必須小於 right，如果不滿足，則不用排序了）。
6. 而對於 2 右邊的數組 5、4、3，設置 left 指向 5，right 指向 3，開始繼續重複圖中的一、二、三、四步驟，對新的數組進行排序。

核心代碼

public int division(int[] list, int left, int right) {

// 以最左邊的數(left)為基準

int base = list[left];

while (left < right) {

// 從序列右端開始，向左遍歷，直到找到小於base的數

while (left < right && list[right] >= base)

right--;

// 找到了比base小的元素，將這個元素放到最左邊的位置

list[left] = list[right];

// 從序列左端開始，向右遍歷，直到找到大於base的數

while (left < right && list[left] <= base)

left++;

// 找到了比base大的元素，將這個元素放到最右邊的位置

list[right] = list[left];

}

// 最後將base放到left位置。此時，left位置的左側數值應該都比left小；

// 而left位置的右側數值應該都比left大。

list[left] = base;

return left;

}

private void quickSort(int[] list, int left, int right) {

// 左下標一定小於右下標，否則就越界了

if (left < right) {

// 對數組進行分割，取出下次分割的基準標號

int base = division(list, left, right);

System.out.format("base = %d:\\t", list[base]);

printPart(list, left, right);

// 對“基準標號“左側的一組數值進行遞歸的切割，以至於將這些數值完整的排序

quickSort(list, left, base - 1);

// 對“基準標號“右側的一組數值進行遞歸的切割，以至於將這些數值完整的排序

quickSort(list, base + 1, right);

}

}

複製代碼

算法分析

快速排序算法的性能

參數 結果 排序類別 交換排序 排序方法 快速排序 時間複雜度平均情況 O(Nlog2N) 時間複雜度最壞情況 O(N2) 時間複雜度最好情況 O(Nlog2N) 空間複雜度 O(Nlog2N) 穩定性 不穩定 複雜性 較複雜 時間複雜度

當數據有序時，以第一個關鍵字為基準分為兩個子序列，前一個子序列為空，此時執行效率最差。

而當數據隨機分佈時，以第一個關鍵字為基準分為兩個子序列，兩個子序列的元素個數接近相等，此時執行效率最好。

所以，數據越隨機分佈時，快速排序性能越好；數據越接近有序，快速排序性能越差。

空間複雜度

快速排序在每次分割的過程中，需要 1 個空間存儲基準值。而快速排序的大概需要 Nlog2N 次的分割處理，所以佔用空間也是 Nlog2N 個。

算法穩定性

在快速排序中，相等元素可能會因為分區而交換順序，所以它是不穩定的算法。

最後，想學習大數據或者需要面試題的小夥伴們！

請關注+私信回覆：“學習”就可以拿到一份我為大家準備的學習資料！

"