定期推送信息學(xué)新聞，競賽自主招生，信息學(xué)專業(yè)知識(shí)，信息學(xué)疑難解答，融科教育信息學(xué)培訓(xùn)等諸多優(yōu)質(zhì)內(nèi)容的微信平臺(tái)，歡迎分享文章給你的朋友或者朋友圈！
排序(Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。
1、選擇排序
選擇排序是一種直觀簡單的排序算法，它每次從待排序的數(shù)據(jù)元素中選出最小(或者最大)元素存放到序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。注意，選擇排序并不是穩(wěn)定的排序。
1 /*
2 * @brief select sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void SelectSort(int arr[], int length)
8 {
9 for (int i = 0; i ) {
10 int min = i;
11 for (int j = i + 1; j ) {
12 if (arr[min] arr[j]) {
13 min = j;
14 }
15 }
16 if (min != i) {
17 swap(arr[min], arr[i]);
18 }
19 }
20 }
2、冒泡排序
冒泡排序也是一種直觀簡單的排序算法，它重復(fù)地走訪要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。冒泡排序是一種穩(wěn)定的排序。
1 /*
2 * @brief bubble sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void BubbleSort(int arr[], int length)
8 {
9 for (int i = 0; i ) {
10 for (int j = 0; j 1; j++) {
11 if (arr[j] > arr[j + 1]) {
12 swap(arr[j], arr[j + 1]);
13 }
14 }
15 }
16 }
3、插入排序
插入排序基本思想是：每步將一個(gè)待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的元素序列中適當(dāng)位置上，直到全部插入完為止。插入排序是穩(wěn)定的排序算法。
1 /*
2 * @brief insert sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void InsertSort(int arr[], int length)
8 {
9 for (int i = 0; i ) {
10 for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
11 swap(arr[j], arr[j - 1]);
12 }
13 }
14 }
15 /* 這是插入排序的第二種寫法 */
16 void InsertSort2(int arr[], int length)
17 {
18 for (int i = 0; i )
19 {
20 int x = arr[i], j;
21 for (j = i; j > 0 && arr[j - 1] > x; j--)
22 arr[j] = arr[j - 1];
23 arr[j] = x;
24 }
25 }
4、希爾排序
希爾排序(Shell Sort)是插入排序的一種，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)數(shù)組恰被分成一組，算法便終止。
1 /*
2 * @brief shell sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void ShellSort(int arr[], int length)
8 {
9 for (int inc = length / 2; inc > 0; inc /= 2) {
10 for (int i = inc; i ) {
11 for (int j = i; j >= inc && arr[j - inc] > arr[j]; j -= inc) {
12 swap(arr[j], arr[j - inc]);
13 }
14 }
15 }
16 }
5、快速排序
快速排序的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
1 /*
2 * 快速排序
3 * 快速排序是一種分治的排序算法，它將一個(gè)數(shù)組分成兩個(gè)子數(shù)組，將兩部分獨(dú)立地排序。
4 * 快速排序和歸并排序是互補(bǔ)的：歸并排序?qū)?shù)組分成兩個(gè)子數(shù)組分別排序，并將有序的子數(shù)組歸并以將整個(gè)數(shù)組排序；
5 * 而快速排序的方式是當(dāng)兩個(gè)子數(shù)組有序時(shí)整個(gè)數(shù)組也就自然有序了。歸并排序中，遞歸發(fā)生在處理整個(gè)數(shù)組之前，
6 * 一個(gè)數(shù)組被分為兩半；快速排序中，遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之后，切分的位置取決于數(shù)組的內(nèi)容。
7 */
8 int Partion(int arr[], int left, int right)
9 {
10 int x = arr[right];
11 int i, j;
12
13 for (i = j = left; i ) {
14 if (arr[i] x) {
15 swap(arr[i], arr[j++]);
16 }
17 }
18 swap(arr[j], arr[right]);
19
20 return j;
21 }
22 void QuickSort(int arr[], int left, int right)
23 {
24 if (left right) {
25 int mid = Partion(arr, left, right);
26 QuickSort(arr, left, mid - 1);
27 QuickSort(arr, mid + 1, right);
28 }
29 }
30 void QuickSort(int arr[], int length)
31 {
32 QuickSort(arr, 0, length - 1);
33 }
6、歸并排序
歸并排序是將兩個(gè)有序的數(shù)組歸并成一個(gè)更大的有序數(shù)組。要將一個(gè)數(shù)組排序，可以先（遞歸的）將他分成兩半分別排序，讓后將結(jié)果歸并起來。它能夠保證將任意長度為N的數(shù)組排序所需時(shí)間和NlogN成正比；它的主要缺點(diǎn)就是所需的額外空間和N成正比。歸并排序是穩(wěn)定的排序算法。
1 /*
2 * 歸并排序
3 * 歸并排序?qū)?shù)組分成兩個(gè)子數(shù)組分別排序，并將有序的子數(shù)組歸并以將整個(gè)數(shù)組排序
4 */
5 void Merge(int arr[], int aux[], int left, int mid, int right) 6 {
7 int i = left;
8 int j = mid + 1;
9 int k = left;
10
11 while (i right) {
12 if (arr[i] > arr[j]) {
13 aux[k++] = arr[j++];
14 }
15 else {
16 aux[k++] = arr[i++];
17 }
18 }
19 while (i mid) {
20 aux[k++] = arr[i++];
21 }
22 while (j right) {
23 aux[k++] = arr[j++];
24 }
25 for (int i = left; i ) {
26 arr[i] = aux[i];
27 }
28 }
29 void MergeSort(int arr[], int aux[], int left, int right)
30 {
31 if (left right) {
32 int mid = left + (right - left) / 2;
33 MergeSort(arr, aux, left, mid);
34 MergeSort(arr, aux, mid + 1, right);
35 Merge(arr, aux, left, mid, right);
36 }
37 }
38 void MergeSort(int arr[], int length)
39 {
40 int *aux = new int[length];
41 MergeSort(arr, aux, 0, length - 1);
42 delete []aux;
43 }
7、 堆排序
堆排序可以分為兩個(gè)階段。在堆的構(gòu)造階段，我們將元使數(shù)組重新組織安排進(jìn)一個(gè)堆中；然后在下沉階段，我們從堆中按遞減順序取出所有元素并得到排序結(jié)果。堆排序主要工作都是在堆的下沉階段完成的，這里我們將堆中最大的元素刪除，然后放入堆縮小后數(shù)組中空出的位置。
1 /*
2 * 堆排序
3 * 堆排序是用堆來實(shí)現(xiàn)的一種排序算法，堆排序分為兩個(gè)階段，在堆的構(gòu)造階段中，我們將原始數(shù)據(jù)重新組織安排
4 * 進(jìn)一個(gè)堆中；然后在下沉排序階段，我們從堆中按照遞減順序取出所有元素并得到排序算法
5 */
6 void Sink(int arr[], int i, int length)
7 {
8 while (2 * i length) {
9 int child = 2 * i;
10 if (child 1]) {
11 child++;
12 }
13 if (arr[i] >= arr[child]) {
14 break;
15 }
16
17 swap(arr[i], arr[child]);
18 i = child;
19 }
20 }
21 void HeapSort(int arr[], int length)
22 {
23 length--; /* 此時(shí)length代表數(shù)組最后一個(gè)元素下標(biāo) */
24 for (int i = length / 2; i >= 0; i--) { /* 這里一定要 i>=0，否則建堆不完全 */
25 Sink(arr, i, length);
26 }
27
28 while(length >= 0) {
29 swap(arr[0], arr[length--]);
30 Sink(arr, 0, length);
31 }
32 }
8、各種排序算法的穩(wěn)定性和時(shí)間復(fù)雜度分析
什么是排序的穩(wěn)定性呢？如果一個(gè)排序算法能夠保留數(shù)組中重復(fù)元素的相對位置則可以稱為是穩(wěn)定的。以下是各個(gè)排序算法穩(wěn)定性總結(jié)：
選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，
冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法。
各個(gè)排序時(shí)間復(fù)雜度總結(jié)：
冒泡法：這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭荩簭?fù)雜度為O(n*n)。當(dāng)數(shù)據(jù)為正序，將不會(huì)有交換。復(fù)雜度為O(n^2)。
直接插入排序：O(n^2)
選擇排序：O(n^2)
快速排序：平均時(shí)間復(fù)雜度log2(n)*n，所有內(nèi)部排序方法中最高好的，大多數(shù)情況下總是最好的。
歸并排序：log2(n)*n
堆排序：log2(n)*n
希爾排序：算法的復(fù)雜度為log2(n)*n
下面是一個(gè)總的表格，大致總結(jié)了我們常見的所有的排序算法的特點(diǎn)。
排序法平均時(shí)間最差情形穩(wěn)定度額外空間備注
冒泡O(n2) O(n2)穩(wěn)定O(1)n小時(shí)較好
交換 O(n2) O(n2)不穩(wěn)定O(1)n小時(shí)較好
選擇O(n2)O(n2)不穩(wěn)定O(1)n小時(shí)較好
插入O(n2)O(n2)穩(wěn)定O(1)大部分已排序時(shí)較好
基數(shù)O(logRB)O(logRB)穩(wěn)定O(n)
B是真數(shù)(0-9)，
R是基數(shù)(個(gè)十百)
ShellO(nlogn)O(ns) 1不穩(wěn)定O(1)s是所選分組
快速O(nlogn)O(n2)不穩(wěn)定O(nlogn)n大時(shí)較好
歸并O(nlogn)O(nlogn)穩(wěn)定O(1)n大時(shí)較好
堆O(nlogn)O(nlogn)不穩(wěn)定O(1)n大時(shí)較好
融科教育信息學(xué)寒假集訓(xùn)營，尋找想突破自己的你！
普及組競賽班
參訓(xùn)對象：已學(xué)信息學(xué)并參加過普及組競賽、想取得更好成績的學(xué)生
普及組提高班
參訓(xùn)對象：有一定的信息學(xué)基礎(chǔ)，但還未參加過競賽的學(xué)生
零基礎(chǔ)班
參訓(xùn)對象：4-7年級(jí)，有良好的數(shù)學(xué)思維能力，有一定的英語基礎(chǔ)，未接觸過信息學(xué)，但對計(jì)算機(jī)編程有濃厚興趣的學(xué)生
