排序算法分為內(nèi)部排序和外部排序，而我們經(jīng)常說的基礎(chǔ)排序算法，都是內(nèi)部排序算法。包括冒泡排序，選擇排序，插入排序，快速排序，并歸排序，希爾排序，堆排序等。
這里總結(jié)一下這幾種排序算法，以備不時之需。
冒泡排序
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
--- 冒泡排序-維基百科
上面是摘自維基百科上冒泡排序的說明，之所以起名冒泡排序，是因為整個過程非常形象，每次經(jīng)過比較交換后，較大的值都會“浮”到最后面（或者較小的值“浮”到最前面）。
動畫示意圖：
它的過程如下：
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
| 最壞時間復(fù)雜度 | О(n2) |
| 最優(yōu)時間復(fù)雜度 | O(n) |
| 平均時間復(fù)雜度 | О(n2) |
| 最壞空間復(fù)雜度 | 總共O(n) |
| 需要輔助空間 | O(1) |
代碼實現(xiàn)
#include <stdio.h>
#define LEN 5
void sort(int a[], int length) {
for (int i = length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (a[i] < a[j]) {
swapArray(a, i, j); // 交換數(shù)組的i，j元素
}
}
}
}
int main(int argc, char const *argv[]) {
int a[LEN] = {10, 5, 2, 4, 7};
sort(a, LEN);
printf("最終結(jié)果：%d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4]);
return 0;
}
選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序-維基百科
動畫示意圖：
| 最壞時間復(fù)雜度 | О(n2) |
| 最優(yōu)時間復(fù)雜度 | О(n2) |
| 平均時間復(fù)雜度 | О(n2) |
| 最壞空間復(fù)雜度 | О(n) total, O(1) auxiliary |
代碼實現(xiàn)
#include <stdio.h>
#define LEN 5
void sort(int a[], int length) {
for (int i = 0; i < length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < length; j++) {
if (a[j] < a[minIdx]) {
minIdx = j;
}
}
swapArray(a, minIdx, i);
}
}
int main(int argc, char const *argv[]) {
int a[LEN] = {10, 5, 2, 4, 7};
sort(a, LEN);
return 0;
}
插入排序
它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
插入排序--維基百科
動畫示意圖：
| 最壞時間復(fù)雜度 | О(n2) |
| 最優(yōu)時間復(fù)雜度 | O(n) |
| 平均時間復(fù)雜度 | О(n2) |
| 最壞空間復(fù)雜度 | 總共 O(n) ，需要輔助空間 O(1) |
代碼實現(xiàn)
#include <stdio.h>
#include "../common/utils.h"
#define LENGTH 5
void sort(int array[], int length) {
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
if (array[i] < array[j]) {
swapArray(array, i, j);
}
}
}
}
int main(int argc, char const* argv[]) {
int array[LENGTH] = {10, 5, 2, 4, 7};
sort(array, LENGTH);
printf("最終結(jié)果：");
printArray(array, LENGTH);
return 0;
}
快速排序
快速排序采用分而治之的策略，找一個基準值，將所有小于基準值的元素放到該基準值前面，所有大于基準值的元素放到基準值的后面。
然后遞歸的將基準值的左右兩部分子序列進行快速排序。
步驟：
- 從數(shù)列中挑出一個元素，稱為“基準”（pivot），
- 重新排序數(shù)列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（相同的數(shù)可以到任何一邊）。在這個分割結(jié)束之后，該基準就處于數(shù)列的中間位置。這個稱為分割（partition）操作。
- 遞歸地（recursively）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
從上面可以看出，該算法采用遞歸思想。
動畫示意圖：
| 最壞時間復(fù)雜度 | О(n2) |
| 最優(yōu)時間復(fù)雜度 | O(nlogn) |
| 平均時間復(fù)雜度 | O(nlogn) |
代碼實現(xiàn)
#include <stdio.h>
#define LEN 5
/*
* 快速排序
* 先選定一個元素，將所有小于該元素的元素放到該元素的左邊，所有大于該元素的元素放到該元素的右邊
* 分別對左右兩部分進行快速排序
* 直到每次排序的元素只有一個元素為止
*/
void sort(int a[], int length, int start, int end) {
printf("排序區(qū)間：a[%d]-a[%d]\n", start, end);
if (start >= end) {
return;
}
int idx = start;
for (int i = start + 1; i <= end; i++) {
// 將所有小于基準的值放到該基準值的前面
if (a[idx] > a[i]) {
int tmp = a[i];
int sidx = i;
while (sidx > idx) {
a[sidx] = a[sidx - 1];
sidx -= 1;
}
a[idx] = tmp;
idx += 1;
}
}
for (int i = 0; i < length; i++) {
printf("%d ", a[i]);
}
printf("\n-----------------------\n");
if (idx > 0) {
sort(a, length, start, idx - 1);
}
if (idx < length - 1) {
sort(a, length, idx + 1, end);
}
}
int main(int argc, char const *argv[]) {
int a[LEN] = {10, 5, 2, 4, 7};
sort(a, LEN, 0, LEN - 1);
printf("最終結(jié)果：%d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4]);
return 0;
}
歸并排序
歸并排序和上面的快速排序相似，也是采用分而治之的策略，同樣也是用遞歸的思想。
不同點在于，歸并排序依賴于歸并操作，即將兩個已經(jīng)排好序的子序列合并成一個大的有序序列。
步驟：
- 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
- 重復(fù)步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
動畫示意圖：
| 最壞時間復(fù)雜度 | O(nlogn) |
| 最優(yōu)時間復(fù)雜度 | O(nlogn) |
| 平均時間復(fù)雜度 | O(nlogn) |
| 最壞空間復(fù)雜度 | O(n) |
代碼實現(xiàn)
#include <stdio.h>
#include "../common/utils.h"
#define LEN 12
/**
* 對兩個已經(jīng)拍好序的子序列進行合并操作
*
*/
void merge(int a[], int start, int mid, int end) {
// 左側(cè)序列的范圍是 [start, mid]
int leftLenght = mid - start + 1;
// 右側(cè)序列的范圍是 [mid+1, end]
int rightLenght = end - mid;
int left[leftLenght], right[rightLenght];
// 將左右兩側(cè)數(shù)據(jù)分別放到兩個臨時數(shù)組中
for (int i = 0; i < leftLenght; i++) {
left[i] = a[start + i];
}
for (int i = 0; i < rightLenght; i++) {
right[i] = a[mid + 1 + i];
}
printf("left:");
printArray(left, leftLenght);
printf("right:");
printArray(right, rightLenght);
// 左右兩部分進行合并
int start1 = 0, start2 = 0;
int i = start;
while (start1 < leftLenght && start2 < rightLenght) {
if (left[start1] < right[start2]) {
a[i] = left[start1];
start1 += 1;
} else {
a[i] = right[start2];
start2 += 1;
}
i += 1;
}
while (start1 < leftLenght) {
a[i++] = left[start1++];
}
while (start2 < rightLenght) {
a[i++] = right[start2++];
}
printf("merge: ");
printArray(a, leftLenght + rightLenght);
printf("----------\n");
}
void sort(int a[], int start, int end) {
int mid = (start + end) / 2;
if (start != mid) {
sort(a, start, mid);
}
if (mid + 1 != end) {
sort(a, mid + 1, end);
}
merge(a, start, mid, end);
}
int main(int argc, char const *argv[]) {
int a[LEN] = {3, 5, 6, 4, 7, 9, 8, 0, 1, 2, 19, 15};
sort(a, 0, LEN - 1);
printf("排序后：");
printArray(a, LEN);
return 0;
}
希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）。
例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應(yīng)該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數(shù)字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經(jīng)移至正確位置了，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)椋?/p>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）。
代碼實現(xiàn)
#include <stdio.h>
#define LEN 10
void sort(int a[], int length) {
for (int gap = length / 2; gap > 0; gap /= 2) {
printf("gap: %d\n", gap);
for (int g = 0; g < gap; g++) {
int tmplength = length / gap;
// 針對每個子間隔序列進行插入排序
for (int i = g + gap; i < tmplength * gap + g; i += gap) {
for (int j = g; j < i; j += gap) {
if (a[i] < a[j]) {
swapArray(a, i, j);
}
}
}
printArray(a, LEN);
}
}
}
int main(int argc, char const *argv[]) {
int a[LEN] = {10, 5, 2, 4, 7, 3, 1, 9, 8, 6};
sort(a, LEN);
printArray(a, LEN);
return 0;
}
堆排序
堆排序（英語：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。
1 11
/ \ / \
2 3 9 10
/ \ / \ / \ / \
4 5 6 7 5 6 7 8
/ \ / \ /\ /\
8 9 10 11 1 2 3 4
小頂堆 大頂堆
如上圖所示，就是小頂堆和大頂堆的示意圖。
堆一般用數(shù)組來表示，有如下特點：
- 索引為i的左孩子的索引是
2*i - 索引為i的右孩子的索引是
2*i+1 - 索引為i的父節(jié)點的索引是
floor(i/2)
堆排序即是用堆的這種特性，先將數(shù)組構(gòu)造成小頂堆（或大頂堆），堆的根元素即為最小值（或最大值）。
然后再一次將剩下的元素再構(gòu)造成小頂堆（或大頂堆），直至最后的堆只有一個元素為止。
步驟：
- 數(shù)組調(diào)整為小頂堆
- 取小頂堆的根節(jié)點，放到第一個元素
- 遞歸調(diào)整剩下的元素為小頂堆，并取堆的根節(jié)點
| 最壞時間復(fù)雜度 | O(nlogn) |
| 最優(yōu)時間復(fù)雜度 | O(nlogn) |
| 平均時間復(fù)雜度 | O(nlogn) |
代碼實現(xiàn)
#include <stdio.h>
#define LEN 15
/**
* arr: 傳入的數(shù)組
* start: 開始位置
* end: 結(jié)束位置
* offset: 偏移量，即從哪個位置開始做最小堆
*/
void swapMin(int arr[], int start, int end, int offset) {
int dad = start;
int son = dad * 2 + 1 - offset;
if (son >= end) {
return;
}
// 先比較兩個子節(jié)點，選擇最小的
if (son + 1 < end && arr[son] > arr[son + 1]) {
son += 1;
}
// 如果父節(jié)點小于子節(jié)點，交換父子節(jié)點
if (arr[dad] >= arr[son]) {
swapArray(arr, dad, son);
}
}
/**
* 構(gòu)建最小堆
* arr: 數(shù)組
* start: 起始元素。從start元素往后的所有元素構(gòu)建最小堆。start之前的表示已排好序
* length: 數(shù)組的長度
*
*/
void minHeapify(int arr[], int start, int length) {
for (int i = length / 2 - 1 + start; i >= start; i--) {
swapMin(arr, i, length, start);
}
}
/**
* 排序方法
* arr: 數(shù)組
* length: 數(shù)組長度
*
*/
void sort(int arr[], int length) {
for (int i = 0; i < length; i++) {
minHeapify(arr, i, length);
}
}
int main(int argc, char const *argv[]) {
int a[LEN] = {10, 5, 3, 4, 7, 3, 2, 9, 7, 6, 12, 8, 3, 15, 20 };
sort(a, LEN);
printArray(a, LEN);
return 0;
}
