知識星球點選上方“芋道原始碼”，選擇“置頂公眾號”
技術文章第一時間送達！
原始碼精品專欄
來源：http://yikun.github.io/2014/11/20/algorithm_sort/
1. 概述
| 演演算法名稱 | 複雜度 | 實現關鍵 |
|---|---|---|
| 氣泡排序 | O(n^2) | （無序區，有序區）。從無序區透過交換找出最大元素放到有序區前端。 |
| 選擇排序 | O(n^2) | （有序區，無序區）。在無序區裡選擇一個最小的元素跟在有序區的後面。 |
| 插入排序 | O(n^2) | （有序區，無序區）。把無序區的第一個元素插入到有序區的合適的位置。 |
| 希爾排序 | nlog^2(n) | 每一輪按照事先決定的間隔進行插入排序，間隔會依次縮小，最後一次一定要是1(插入)。 |
| 快速排序 | nlog(n) | （小數，樞紐元，大數）。 |
| 堆排序 | nlog(n) | |
| 桶排序 | O(n) | 將值為i的元素放入i號桶，最後依次把桶裡的元素倒出來。 |
不穩定的排序：
穩定性一個形象的比喻，本來有兩個併列第三，一排序把原來併列的順序給變了。
比如：選擇排序、快速排序、堆排序、希爾排序；
參考連結
2. 氣泡排序
每次都把未排序的第一個作為起始點，然後逐漸冒泡上升，之後未排序區越來越少，最終排序完成
1// 氣泡排序
2void bubble_sort(int a[], int n)
3{
4 int i = 0;
5 int j = 0;
6 for (i=0; i1; i++)
7 {
8 // 比較相鄰元素，若a[j]比a[j+1]大，則交換
9 // a[j]就像一個氣泡一樣“浮”到合適位置了
10 for(j=0; j1-i; j++)
11 {
12 if(a[j]>a[j+1])
13 {
14 swap(&a;[j], &a;[j+1]);
15 }
16 }
17 }
18}
3. 選擇排序
每一趟從待排序的資料元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。
1// 選擇排序
2void select_sort(int a[], int n)
3{
4 int i=0,j=0,min=0;
5 for (i=0; i 1; i++)
6 {
7 min = i;
8 // 找到最小值
9 for (j=i+1; j <= n-1; j++)
10 {
11 if (a[min] > a[j])
12 min = j;
13 }
14 if(min != i)
15 {
16 swap(&a;[min], &a;[i]);
17 }
18 }
19}
4. 插入排序
每次排序從未排序區取一個“牌”，然後往前插入(包括了兩步：大的往後移，把牌放到合適位置)。
1// 插入排序
2void insert_sort(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 int tmp=0;
7 for (i = 1; i 8 {
9 // 取牌
10 tmp = a[i];
11 // 往前插的起始位置
12 j = i - 1;
13
14 // 大的a[j]都放後面，尋找出j
15 while ((j >= 0) && a[j] > tmp)
16 {
17 // 往後放一個
18 a[j+1] = a[j];
19 j--;
20 }
21
22 // 放到該放的位置
23 a[j+1]=tmp;
24 }
25}
另外還有種思路，把資料後移的過程換成交換的過程
1// 插入排序，選中的牌冒泡向前插入
2void insert_sort_2(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 //透過i選牌
7 for (i=1; i 8 {
9 // 冒泡向前插入(i-1 --> 0)
10 for (j=i-1; j>=0 && a[j] > a[j + 1]; j--)
11 {
12 swap(&a;[j], &a;[j+1]);
13 }
14 }
15 print_a(a, n);
16}
17`
5. 希爾排序
對插入排序再加一個步長的迴圈就是希爾排序了，例如
1[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
按照5步長排序，則相當於按列先進行排序(實際是透過下標實現的)
113 14 94 33 82
225 59 94 65 23
345 27 73 25 39
410
排序後結果為
110 14 73 25 23
213 27 94 33 39
325 59 94 65 82
445
多次迴圈後，只需要最終步長為1即可。
1// 希爾排序
2void shell_sort(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 int tmp=0;
7 int gap=0;
8 while (gap <= n)
9 {
10 gap = gap*3 + 1;
11 }
12 while (gap > 0)
13 {
14 // 取牌
15 for (i = gap; i 16 {
17 // 冒泡向前插入(i-gap : gap : 0), 保證每列ok
18 for (j = i - gap; (j >= 0) && (a[j] > a[j + gap]); j = j - gap)
19 {
20 swap(&a;[j], &a;[j+gap]);
21 }
22 }
23 gap = (gap-1) / 3;
24 }
25}
6. 快速排序
每次迭代都選出一個基準，左邊放小的，右邊放大的，最終迭代完成。
1// 快速排序分割槽
2static int partition(int a[], int p, int r)
3{
4 int x=0;
5 int i=0;
6 int j=0;
7 // x為基準
8 x = a[r];
9 // i為界限,發現小於x的，就i++，再放到i處
10 i = p-1;
11 for (j=p; j<= r-1; j++)
12 {
13 if (a[j]<=x)
14 {
15 i++;
16 swap(&a;[i], &a;[j]);
17 }
18 }
19 // 至此，所有小於x的都到i左邊了(a[0]~a[i-1])，a[r]是x，因此交換a[i+1]和a[r]
20 swap(&a;[i+1], &a;[r]);
21 return i+1;
22}
23
24// 快速排序
25void quick_sort(int a[], int p, int r)
26{
27 int q=0;
28 if (p 29 {
30 // 在資料集之中，選擇一個元素作為"基準"（pivot）
31 // 所有小於"基準"的元素，都移到"基準"的左邊；所有大於"基準"的元素，都移到"基準"的右邊
32 q = partition(a, p, r);
33 // 對"基準"左邊和右邊的兩個子集，不斷重覆第一步和第二步，直到所有子集只剩下一個元素為止。
34 quick_sort(a, p, q-1);
35 quick_sort(a, q+1, r);
36 }
37}如果你對 Dubbo / Netty 等等原始碼與原理感興趣，歡迎加入我的知識星球一起交流。長按下方二維碼噢：
目前在知識星球更新了《Dubbo 原始碼解析》目錄如下：
01. 除錯環境搭建
02. 專案結構一覽
03. 配置 Configuration
04. 核心流程一覽
05. 拓展機制 SPI
06. 執行緒池
07. 服務暴露 Export
08. 服務取用 Refer
09. 註冊中心 Registry
10. 動態編譯 Compile
11. 動態代理 Proxy
12. 服務呼叫 Invoke
13. 呼叫特性
14. 過濾器 Filter
15. NIO 伺服器
16. P2P 伺服器
17. HTTP 伺服器
18. 序列化 Serialization
19. 叢集容錯 Cluster
20. 優雅停機
21. 日誌適配
22. 狀態檢查
23. 監控中心 Monitor
24. 管理中心 Admin
25. 運維命令 QOS
26. 鏈路追蹤 Tracing
… 一共 69+ 篇
目前在知識星球更新了《Netty 原始碼解析》目錄如下：
01. 除錯環境搭建
02. NIO 基礎
03. Netty 簡介
04. 啟動 Bootstrap
05. 事件輪詢 EventLoop
06. 通道管道 ChannelPipeline
07. 通道 Channel
08. 位元組緩衝區 ByteBuf
09. 通道處理器 ChannelHandler
10. 編解碼 Codec
11. 工具類 Util
… 一共 61+ 篇
目前在知識星球更新了《資料庫物體設計》目錄如下：
01. 商品模組
02. 交易模組
03. 營銷模組
04. 公用模組
… 一共 17+ 篇
原始碼不易↓↓↓↓↓
點贊支援老艿艿↓↓
