文章目錄
1.?概念
2.?十大排序算法
3.?冒泡排序
4. 冒泡代碼實現
5. 快速排序
6. 快速代碼實現
7. 選擇排序
8.?選擇代碼實現
9. 插入排序
10.?插入代碼實現
1.?概念
排序(Sort)是將無序的記錄序列(或稱文件)調整成有序的序列。排序算法在計算機科學中非常重要,因為它們可以提高數據檢索效率、簡化后續算法的復雜性和優化存儲結構等。
穩定排序和非穩定排序
- 穩定排序:如果在排序前,兩個相等的元素在原序列中的先后順序在排序后依然保持不變,那么這種排序算法就是穩定的。插入排序,歸并排序,冒泡排序。
- 非穩定排序:如果排序后,兩個相等的元素的先后順序可能改變,那么這種排序算法就是非穩定的。選擇排序,快速排序,堆排序。
例如:
- 原序列:R1,R2,...,Ri,...,Rj,...,Rn
- 其中,Ki=Kj 且 i<j(即 Ri 在 Rj 之前)。
在穩定排序中,排序后 Ri 仍在 Rj? 之前。而在非穩定排序中,Ri? 和 Rj 的相對位置可能會改變。
內排序和外排序
- 內排序:如果待排序文件的所有記錄都能放入內存中進行排序,那么這種排序稱為內排序。內排序速度快,但受限于內存容量,適用于較小的數據集。插入排序、冒泡排序、選擇排序、快速排序、歸并排序等。
- 外排序:如果待排序文件的大小超過了內存容量,需要借助外存(如磁盤)進行排序,那么這種排序稱為外排序。外排序速度較慢,但適用于大型數據集。通常通過將數據分塊讀取到內存中排序,然后再將排序后的塊合并來實現。比如:歸并排序。
排序算法是計算機科學中的基本算法,廣泛應用于各種場景。穩定性和適用場景是選擇排序算法時的重要考慮因素。內排序適用于小數據集,外排序則適用于大數據集。理解這些概念和性質有助于選擇合適的排序算法,從而提高程序的效率和性能。
2.?十大排序算法
排序方法 | 時間復雜度(平均) | 時間復雜度(最壞) | 時間復雜度(最好) | 空間復雜度 | 穩定性 |
---|---|---|---|---|---|
插入排序 | O(n2) | O(n2) | O(n) | O(1) | 穩定 |
希爾排序 | O(n log2 n) | O(n2) | O(n) | O(1) | 不穩定 |
選擇排序 | O(n2) | O(n2) | O(n2) | O(1) | 不穩定 |
堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不穩定 |
冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 穩定 |
快速排序 | O(n log n) | O(n2) | O(n log n) | O(log n) | 不穩定 |
歸并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 穩定 |
計數排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 穩定 |
桶排序 | O(n + k) | O(n2) | O(n) | O(n) | 穩定 |
基數排序 | O(n * k) | O(n * k) | O(n * k) | O(n * k) | 穩定 |
3.?冒泡排序
冒泡排序是一種簡單的排序算法,它通過多次遍歷要排序的序列,依次比較相鄰元素的大小,并根據需要交換它們的位置,以此將序列中的最大或最小元素逐步移動到序列的一端。其思路如下:
-
比較相鄰元素:
- 從數組的第一個元素開始,依次比較相鄰的兩個元素。
-
交換位置:
- 如果當前面的元素比后面的元素大(或小,根據升序或降序排序的要求),則交換這兩個元素的位置。
-
一趟遍歷完成:
- 最大(或最小)元素已移至末尾:經過一趟遍歷,最大(或最小)的元素會被交換到數組的最后一個位置。
-
重復進行遍歷和交換:
- 除了最后一個元素,對數組中的所有元素重復執行上述兩步。
每次遍歷都會將當前未排序部分的最大(或最小)元素放置到合適的位置。
循環遍歷:重復執行步驟3和步驟4,直到整個數組都被排序。
示例:
以序列 [3, 1, 5, 4, 2]
為例,進行冒泡排序的過程如下:
-
第一趟比較:
- 比較
3
和1
,3
大于1
,交換位置,序列變為[1, 3, 5, 4, 2]
。 - 比較
3
和5
,3
小于5
,不交換位置,序列不變。 - 比較
5
和4
,5
大于4
,交換位置,序列變為[1, 3, 4, 5, 2]
。 - 比較
5
和2
,5
大于2
,交換位置,序列變為[1, 3, 4, 2, 5]
。 - 第一趟比較結束,最大元素
5
已經移到序列末尾。
- 比較
-
第二趟比較:
- 比較
1
和3
,1
小于3
,不交換位置,序列不變。 - 比較
3
和4
,3
小于4
,不交換位置,序列不變。 - 比較
4
和2
,4
大于2
,交換位置,序列變為[1, 3, 2, 4, 5]
。 - 第二趟比較結束,次大元素
4
已經移到序列倒數第二位。
- 比較
-
第三趟比較:
- 比較
1
和3
,1
小于3
,不交換位置,序列不變。 - 比較
3
和2
,3
大于2
,交換位置,序列變為[1, 2, 3, 4, 5]
。 - 第三趟比較結束,次小元素
3
已經移到正確位置。
- 比較
-
第四趟比較:
- 比較
1
和2
,1
小于2
,不交換位置,序列不變。 - 第四趟比較結束,次次小元素
2
已經移到正確位置。
- 比較
通過上述步驟,整個序列變為 [1, 2, 3, 4, 5]
,排序完成。
優化:
在實際實現中,可以通過添加一個標志來檢測在某一趟遍歷中是否發生了交換。如果沒有發生交換,則說明數組已經是有序的,可以提前終止排序過程,進一步提升算法效率。
這種算法適用于數據量較小的情況,雖然其時間復雜度為O(n2),但其實現簡單,且在某些情況下(如數據量較小或數據已基本有序)依然具有一定的實用性。
4. 冒泡代碼實現
#include <stdio.h>// 冒泡排序函數定義
void bubbleSort(int arr[], int n) {int i, j;// 外層循環:控制比較輪數,每次減少一個元素的比較for (i = 0; i < n - 1; i++) {// 內層循環:進行元素比較和交換for (j = 0; j < n - i - 1; j++) {// 如果前一個元素大于后一個元素,則交換它們if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}// 打印數組的函數
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}// 主函數
int main() {// 定義一個數組int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的數組: \n");printArray(arr, n);// 調用冒泡排序函數bubbleSort(arr, n);printf("排序后的數組: \n");printArray(arr, n);return 0;
}
5. 快速排序
快速排序(Quick Sort)是一種高效的排序算法,由圖靈獎獲得者Tony Hoare發明,被列為20世紀十大算法之一。其主要特點是通過分治法(Divide and Conquer)來實現對數據的快速排序。下面詳細解釋快速排序的算法原理和執行過程。
基本思想
快速排序通過以下步驟進行排序:
- 選擇基準(pivot):從數列中挑選一個元素,稱為“基準”。
- 分區(partition):重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺放在基準后面。經過分區后,基準值的位置就是它在排序后數組中的最終位置。
- 遞歸排序:遞歸地對基準值左邊的子數組和右邊的子數組進行快速排序。
執行步驟
-
選擇基準:
- 基準可以是數組中的任意一個元素,常見的選擇方法有:選擇第一個元素、最后一個元素、中間的元素,或者隨機選擇一個元素作為基準。
-
分區操作:
- 將數組中的元素重新排列,所有小于基準的元素放在基準的左邊,所有大于基準的元素放在基準的右邊。
- 分區過程中,基準值最終會被放到它的正確位置上,即使得基準左邊的所有元素都小于基準,右邊的所有元素都大于基準。
-
遞歸排序:
- 對基準左邊和右邊的子數組分別進行快速排序。
- 遞歸的基準情況是子數組的大小為零或一,此時數組已經被排序好了。
優點與缺點
-
優點:
- 平均時間復雜度為O(n log n),在大多數情況下表現非常好。
- 空間復雜度為O(log n),需要遞歸調用棧空間。
- 屬于原地排序算法,空間利用率高。
- 排序速度非常快,尤其適用于大數據集。
-
缺點:
- 最壞情況下時間復雜度為O(n^2),如數組已經有序或逆序時。
- 不穩定排序,可能打亂相同元素的相對順序。
示例1:
個示例展示了如何使用快速排序算法對數組進行排序。假設有以下數組:
[49, 38, 65, 97, 76, 13, 27, 49]
第一步:選擇基準并進行第一次分區
- 選擇基準
49
。 - 進行分區,將數組分為三部分:小于
49
、等于49
和大于49
的部分。
[27, 38, 13], 49, [76, 97, 65, 49]
第二步:遞歸排序
對每一部分繼續遞歸地進行快速排序:
- 對左側
[27, 38, 13]
部分:- 選擇
27
作為基準。 - 分區為
[13] 27 [38]
。
- 選擇
[13] 27 [38]
對右側 [76, 97, 65, 49]
部分:
- 選擇
76
作為基準。 - 分區為
[65] 76 [97]
。
[65] 76 [97]
組合結果
將所有部分組合起來,得到排序后的數組:
[13, 27, 38, 49, 49, 65, 76, 97]
示例2:
初始狀態:
[9, -16, 30, 23, -30, -49, 25, 21, 30]
-
第一趟交換:
- 基準值:9
- 低位指針和高位指針開始交換:
- 第一次交換后: [-16, 9, 30, 23, -30, -49, 25, 21, 30]
- 第二次交換后: [-16, -49, 30, 23, -30, 9, 25, 21, 30]
- 第三次交換后: [-16, -49, -30, 23, 9, 30, 25, 21, 30]
-
第二趟交換:
- 基準值:-30
- 低位指針和高位指針開始交換:
- 第一次交換后: [-49, -30, -16, 23, 9, 30, 25, 21, 30]
- 第二次交換后: [-49, -30, -16, 23, 9, 30, 25, 21, 30]
-
分割完成:
- 將數組分為左側和右側分別繼續遞歸排序,最終達到有序。
6. 快速代碼實現
#include <stdio.h>// 快速排序入口函數
void quickSort(int arr[], int size) {subSort(arr, 0, size - 1);
}// 輔助排序函數,遞歸實現
void subSort(int arr[], int start, int end) {if (start < end) {int base = arr[start]; // 選擇基準值為第一個元素int low = start; // 初始化低位索引int high = end + 1; // 初始化高位索引while (1) {while (low < end && arr[++low] <= base); // 從左向右掃描,找到第一個大于基準值的元素while (high > start && arr[--high] >= base); // 從右向左掃描,找到第一個小于基準值的元素if (low < high) {int temp = arr[low]; // 交換找到的兩個元素arr[low] = arr[high];arr[high] = temp;} else {break; // 如果low和high相遇,則退出循環}}int temp1 = arr[start]; // 將基準值交換到正確的位置arr[start] = arr[high];arr[high] = temp1;subSort(arr, start, high - 1); // 遞歸排序基準值左邊的子數組subSort(arr, high + 1, end); // 遞歸排序基準值右邊的子數組}
}// 打印數組函數
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函數
int main() {int arr[] = {9, -16, 40, 23, -30, -49, 25, 21, 30};int length = sizeof(arr) / sizeof(int);// 排序前遍歷數組printArray(arr, length);// 調用快速排序quickSort(arr, length);// 排序后遍歷數組printArray(arr, length);return 0;
}
7. 選擇排序
選擇排序(Selection Sort)是一種簡單直觀的排序算法。它的基本思想是不斷地從未排序的部分中選擇最小(或最大)的元素,放到已排序部分的末尾,從而不斷擴大已排序的部分,直到整個數組有序。選擇排序的時間復雜度為O(n^2),空間復雜度為O(1),是一種不穩定的排序算法。
算法原理
- 初始狀態:整個數組為未排序部分。
- 找到最小值:從未排序部分中找到最小(或最大)的元素。
- 交換位置:將找到的最小(或最大)元素與未排序部分的第一個元素交換位置。
- 已排序部分增加:將已排序部分擴大一個元素,未排序部分減小一個元素。
- 重復步驟2-4:對未排序部分重復上述步驟,直到未排序部分為空,排序完成。
優點
-
簡單易懂:選擇排序的算法原理非常直觀,容易理解和實現,特別適合教學和初學者學習。
-
不需要額外空間:選擇排序是就地排序(in-place sorting)算法,只需要常數級別的額外空間,空間復雜度為O(1)。
-
適合小規模數據:對于小規模數據集,選擇排序的實現簡單且運行時間可以接受。
缺點
-
時間復雜度高:選擇排序的時間復雜度為O(n^2),不適合大規模數據集,隨著數據量的增加,性能會顯著下降。
-
不穩定:選擇排序是不穩定的排序算法,即相同元素的相對順序在排序過程中可能會被改變。
-
數據交換多:在選擇排序過程中,每次找到最小值后都會進行數據交換,如果數組元素較多且數據量較大,頻繁的數據交換會影響性能。
過程示例:
初始數組:
[29, 10, 14, 37, 14]
?第一輪:找到最小值10,交換29和10。
[10, 29, 14, 37, 14]
第二輪:找到最小值14,交換29和14。
[10, 14, 29, 37, 14]
第三輪:找到最小值14,交換29和14。
[10, 14, 14, 37, 29]
第四輪(最終結果):找到最小值29,交換37和29。
[10, 14, 14, 29, 37]
選擇排序通過不斷選擇未排序部分的最小值,將其移動到已排序部分的末尾,逐步完成整個排序過程。雖然選擇排序的時間復雜度較高,但其實現簡單,適用于數據量較小或對穩定性要求不高的場景。
8.?選擇代碼實現
#include <stdio.h>// 選擇排序函數
void selectionSort(int arr[], int size) {// 外層循環,逐步擴大已排序部分for (int i = 0; i < size - 1; i++) {// 假設當前位置i為最小值索引int minIndex = i;// 內層循環,從i+1位置開始尋找未排序部分的最小值for (int j = i + 1; j < size; j++) {if (arr[j] < arr[minIndex]) {// 更新最小值索引minIndex = j;}}// 交換當前位置i和找到的最小值位置minIndex的元素if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}// 打印數組函數
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函數
int main() {// 定義并初始化一個待排序的數組int arr[] = {29, 10, 14, 37, 14};int length = sizeof(arr) / sizeof(arr[0]);// 排序前遍歷數組并打印printf("排序前的數組: ");printArray(arr, length);// 調用選擇排序函數對數組進行排序selectionSort(arr, length);// 排序后遍歷數組并打印printf("排序后的數組: ");printArray(arr, length);return 0;
}
9. 插入排序
插入排序(Insertion Sort)是一種簡單直觀的排序算法。它的工作原理類似于我們整理撲克牌的過程,從左到右逐步擴大已排序的部分,將當前元素插入到已排序部分的適當位置,直到整個序列有序。
算法原理
- 初始狀態:已排序部分只有第一個元素。
- 從第二個元素開始:逐一取出元素,將其插入到已排序部分的適當位置。
- 重復步驟2:直到所有元素均插入到已排序部分。
插入排序的優缺點
優點:
- 算法簡單,易于理解和實現。
- 對于少量元素的數組或幾乎已經排好序的數組,插入排序非常高效。
- 是穩定排序算法,保證相等元素的相對位置不變。
缺點:
- 對于大規模數組,插入排序的效率較低,時間復雜度為O(n^2)。
插入排序的步驟示例
初始狀態:
[5, 2, 9, 1, 5, 6]
- 已排序部分:
[5]
-
第二個元素2:
- 將2插入到已排序部分
[5]
之前。
- 將2插入到已排序部分
[2, 5, 9, 1, 5, 6]
-
已排序部分:
[2, 5]
-
第三個元素9:
- 將9插入到已排序部分
[2, 5]
之后。
- 將9插入到已排序部分
[2, 5, 9, 1, 5, 6]
-
已排序部分:
[2, 5, 9]
-
第四個元素1:
- 將1插入到已排序部分
[2, 5, 9]
之前。
- 將1插入到已排序部分
[1, 2, 5, 9, 5, 6]
-
已排序部分:
[1, 2, 5, 9]
-
第五個元素5:
- 將5插入到已排序部分
[1, 2, 5, 9]
的適當位置。
- 將5插入到已排序部分
[1, 2, 5, 5, 9, 6]
-
已排序部分:
[1, 2, 5, 5, 9]
-
第六個元素6:
- 將6插入到已排序部分
[1, 2, 5, 5, 9]
的適當位置。
- 將6插入到已排序部分
[1, 2, 5, 5, 6, 9]
10.?插入代碼實現
#include <stdio.h>// 插入排序函數
void insertionSort(int arr[], int size) {// 從數組的第二個元素開始,逐個插入到已排序部分for (int i = 1; i < size; i++) {int key = arr[i]; // 當前待插入的元素int j = i - 1;// 將已排序部分中大于key的元素向后移動while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key; // 將key插入到正確的位置}
}// 打印數組函數
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函數
int main() {// 定義并初始化一個待排序的數組int arr[] = {5, 2, 9, 1, 5, 6};int length = sizeof(arr) / sizeof(arr[0]);// 排序前遍歷數組并打印printf("排序前的數組: ");printArray(arr, length);// 調用插入排序函數對數組進行排序insertionSort(arr, length);// 排序后遍歷數組并打印printf("排序后的數組: ");printArray(arr, length);return 0;
}