1. 常用數(shù)據(jù)結(jié)構(gòu)

• 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成 。

• 常用的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組奄侠，棧，鏈表载矿，隊(duì)列垄潮，樹，圖闷盔，堆弯洗，散列表等，如圖所示：

  
  
  常用數(shù)據(jù)結(jié)構(gòu)
  
  
  數(shù)據(jù)的邏輯結(jié)構(gòu)

1. 1 數(shù)組

• 數(shù)組是可以再內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu)逢勾，在內(nèi)存中的分配也是連續(xù)的牡整，數(shù)組中的元素通過數(shù)組下標(biāo)進(jìn)行訪問，數(shù)組下標(biāo)從0開始溺拱。例如下面這段代碼就是將數(shù)組的第一個(gè)元素賦值為 1逃贝。

int[] data = new int[100]；data[0]  = 1;

• 優(yōu)點(diǎn)：

1迫摔、按照索引查詢?cè)厮俣瓤?br> 2沐扳、按照索引遍歷數(shù)組方便

• 缺點(diǎn)：

1、數(shù)組的大小固定后就無法擴(kuò)容了
2句占、數(shù)組只能存儲(chǔ)一種類型的數(shù)據(jù)
3沪摄、添加，刪除的操作慢，因?yàn)橐苿?dòng)其他的元素杨拐。

• 適用場(chǎng)景：

頻繁查詢祈餐，對(duì)存儲(chǔ)空間要求不大，很少增加和刪除的情況哄陶。

1. 2 字典

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

1. 3 鏈表

• 鏈表是物理存儲(chǔ)單元上非連續(xù)的昼弟、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實(shí)現(xiàn)奕筐，每個(gè)元素包含兩個(gè)結(jié)點(diǎn)舱痘，一個(gè)是存儲(chǔ)元素的數(shù)據(jù)域 (內(nèi)存空間)，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)地址的指針域离赫。根據(jù)指針的指向芭逝，鏈表能形成不同的結(jié)構(gòu)，例如單鏈表渊胸，雙向鏈表旬盯，循環(huán)鏈表等。

  
  
  鏈表

• 優(yōu)點(diǎn)：

鏈表是很常用的一種數(shù)據(jù)結(jié)構(gòu)翎猛，不需要初始化容量胖翰，可以任意加減元素；
添加或者刪除元素時(shí)只需要改變前后兩個(gè)元素結(jié)點(diǎn)的指針域指向地址即可切厘，所以添加萨咳，刪除很快；

• 缺點(diǎn)：

因?yàn)楹写罅康闹羔樣蛞吒澹加每臻g較大培他；
查找元素需要遍歷鏈表來查找，非常耗時(shí)遗座。

• 適用場(chǎng)景：

數(shù)據(jù)量較小舀凛，需要頻繁增加，刪除操作的場(chǎng)景

1. 4 堆棧

1.4.1 堆

• 堆是一種比較特殊的數(shù)據(jù)結(jié)構(gòu)途蒋，可以被看做一棵樹的數(shù)組對(duì)象猛遍，具有以下的性質(zhì)：

1. 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
2. 堆總是一棵完全二叉樹号坡。

• 將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆懊烤，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。常見的堆有二叉堆筋帖、斐波那契堆等奸晴。
• 堆的定義如下：n個(gè)元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)，稱之為堆日麸。
  (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)寄啼，滿足前者的表達(dá)式的成為小頂堆逮光，滿足后者表達(dá)式的為大頂堆，這兩者的結(jié)構(gòu)圖可以用完全二叉樹排列出來墩划，示例圖如下：

堆

• 因?yàn)槎延行虻奶攸c(diǎn)涕刚，一般用來做數(shù)組中的排序，稱為堆排序乙帮。

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

1.4.2 棧

• 棧是一種特殊的線性表杜漠，僅能在線性表的一端操作，棧頂允許操作察净，棧底不允許操作驾茴。 棧的特點(diǎn)是：先進(jìn)后出，或者說是后進(jìn)先出氢卡，從棧頂放入元素的操作叫入棧锈至，取出元素叫出棧。
  
  棧
• 棧的結(jié)構(gòu)就像一個(gè)集裝箱译秦，越先放進(jìn)去的東西越晚才能拿出來峡捡，所以，棧常應(yīng)用于實(shí)現(xiàn)遞歸功能方面的場(chǎng)景筑悴，例如斐波那契數(shù)列们拙。

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

1.4.2.1 棧的定義和基本運(yùn)算

• 什么是棧：

棧是只能通過訪問它的一端來實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)和檢索的一種線性數(shù)據(jù)結(jié)構(gòu)。換句話說阁吝，棧的修改是按先進(jìn)后出的原則進(jìn)行的砚婆。因此，棧又稱為先進(jìn)后出（FILO）的線性表求摇。在棧中進(jìn)行插入和刪除操作的一端稱為棧頂（top）射沟，相應(yīng)地，另一端稱為棧底（bottom）与境。不含數(shù)據(jù)元素的棧稱為空棧。

• 棧的基本運(yùn)算

1. 初始化棧InitStack(S):創(chuàng)建一個(gè)空棧S猖吴。
2. 判斷空棧StackEmpty（S）：當(dāng)棧為空棧時(shí)返回“真”摔刁，否則返回“假”。
3. 入棧Push（S海蔽，x）：將元素x加入棧頂共屈，并更新棧頂指針。
4. 出棧Pop（S）：將棧頂?shù)脑貜臈Ｖ袆h除党窜，并且更新棧頂指針拗引。
5. 讀棧頂元素Top（S）：返回棧頂元素的值，但不修改棧頂?shù)闹羔槨?/li>

1.4.2.2 棧的存儲(chǔ)結(jié)構(gòu)

• 棧的順序存儲(chǔ)

棧的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)自棧頂?shù)綏５椎臄?shù)據(jù)元素幌衣，同時(shí)附設(shè)指針top指示棧頂元素的位置矾削。采用順序存儲(chǔ)結(jié)構(gòu)的棧也稱為順序棧壤玫。在順序存儲(chǔ)方式下，需要預(yù)先定義或申請(qǐng)棧的存儲(chǔ)空間哼凯，也就是說椨洌空間的容量是有限的。因此在順序棧中断部，當(dāng)一個(gè)元素入棧時(shí)猎贴，需要判斷是否棧滿（即棧空間中沒有空閑單元）蝴光，若棧滿她渴，則元素入棧會(huì)發(fā)生上溢現(xiàn)象。

• 棧的鏈?zhǔn)酱鎯?chǔ)

棧的鏈?zhǔn)酱鎯?chǔ)是為了克服順序存儲(chǔ)的椕锼睿可以存在上溢的不足趁耗，可以用鏈表存儲(chǔ)棧中的元素。用鏈表作為存儲(chǔ)結(jié)構(gòu)的棧也稱為鏈棧做瞪。由于棧中元素的插入和刪除僅在棧頂一端進(jìn)行对粪，因此不必另外設(shè)置頭指針，鏈表的頭指針就是棧頂指針装蓬。

棧的鏈?zhǔn)酱鎯?chǔ)

1.4.2.3 棧的應(yīng)用

• 棧的典型應(yīng)用包括表達(dá)式求值著拭，括號(hào)匹配等。在計(jì)算機(jī)語言的實(shí)現(xiàn)以及將遞歸過程轉(zhuǎn)變?yōu)榉沁f歸過程的處理中牍帚，棧有重要的作用儡遮。
• 棧的實(shí)例1423：

1. 表達(dá)式求值

計(jì)算機(jī)在處理算術(shù)表達(dá)式時(shí)，可將表達(dá)式先轉(zhuǎn)換為后綴形式暗赶，然后利用棧進(jìn)行計(jì)算鄙币。例如，表達(dá)式“46+5 （120-37）”的后綴表達(dá)式為“46 5 120 37 - * +”蹂随。計(jì)算后綴表達(dá)式時(shí)十嘿，從左至右掃描表達(dá)式：若遇到運(yùn)算對(duì)象，則壓入棧中岳锁；遇到運(yùn)算符绩衷，則從棧頂彈出運(yùn)算對(duì)象進(jìn)行計(jì)算，并將運(yùn)算結(jié)果壓入棧中激率。重復(fù)以上過程咳燕，直到后綴表達(dá)式掃描結(jié)束。例如“46 5 120 37 - * +”的計(jì)算過程為：
1乒躺、依次將46招盲，5，120嘉冒，37壓入棧中曹货；
2咆繁、遇到“-”取37，120控乾，計(jì)算120-37么介，得83，將其壓入棧中蜕衡；
3壤短、遇到“”取出83，5慨仿，計(jì)算83*5久脯，得415，將其壓入棧中镰吆；
4帘撰、遇到“+”，取出415万皿，46摧找，計(jì)算46+415，得461牢硅，將其壓入棧中蹬耘；
5、表達(dá)式結(jié)束减余，計(jì)算過程完成综苔。
下面函數(shù)computing(char expr[],int result)的功能是基于棧計(jì)算后綴形式的表達(dá)式（以串形式存入字符數(shù)組expr）的值，并通過參數(shù)result帶回該值。函數(shù)的返回值為-1/0，分別表示表達(dá)時(shí)有/無錯(cuò)誤造寝。假設(shè)表達(dá)式中僅包含數(shù)字,空格和算術(shù)運(yùn)算符號(hào)，其中所有項(xiàng)均以空格分隔睬隶，且運(yùn)算符僅包含（“+”）,（“-”）,（“”）,（“\”）。
void InitStack(STACK *s):初始化棧。
void Push(STACK *s, int e):將一個(gè)整數(shù)壓入棧，棧中元素?cái)?shù)目增加1拭嫁。
void Pop(STACK *s);棧頂元素出棧，棧中元素?cái)?shù)目減1抓于。
int Top(STACK s):返回非空棧的棧頂元素值,棧中元素不變。
int IsEmpty(STACK　 s);若s是空 棧,則返回1浇借；否則返回0捉撮。

實(shí)例1423實(shí)現(xiàn)代碼：

int computing (char expr[], int * result)
{
       STACK s;  int  tnum,a,b;     char *ptr;
       InitStack(&s);
       ptr = expr;            /*字符指針指向后綴表達(dá)式串的第一個(gè)字符*/
       while (*ptr != '\0')
        { 
             if ( *ptr == ' ') /*當(dāng)前字符是空格，則取下一個(gè)字符*/
              {
                     ptr++;
                     continue;
              }
             else  if ( isdigit(*ptr)) /*當(dāng)前字符是數(shù)字,則將數(shù)字串轉(zhuǎn)化為數(shù)值*/
                     {
                          tmun = 0;
                          while(*ptr >= '0'  &&  *ptr <= '9')
                          {
                                 tnum = tnum *10 + *ptr - '0';
                                 ptr++;
                          }
                            Push(&s,tnum);
                     }
             
            else  if ( *ptr == '+' || *ptr == '-'  ||  *ptr == '*'  || *ptr == '/') /*當(dāng)前是運(yùn)算符*/
            {
                   if ( !IsEmpty(s)){
                           a = Top(s);Pop(&s);                /*取運(yùn)算符的第二個(gè)運(yùn)算符妇垢，存入a*/
                           if ( IsEmpty(s)) {
                                 b = Top(s); Pop(&s);        /*取運(yùn)算符的第一個(gè)運(yùn)算符巾遭，存入b*/
                           }
                           else
                           {
                                 return -1;
                           }
                    }
                    else
                    {
                          retun -1;          /*椚饪担空*/
                    }
                    switch ( *ptr) {
                         case '+' : Push(&s,b+a);break;
                         case '-':  Push(&s,b-a);break;
                         case '*':  Push(&s,b*a);break;
                         case '/': Push(&s,b/a);break;
                      }
            }
           else   /*非法字符*/
            {
                   return -1;
            }
             
             ptr++;
  }/*while*/
 
   if (IsEmpty(s))
      return -1;
  else
     {
         *result = Top(s);Pop(&s); /*得到運(yùn)算結(jié)果*/
         if (!IsEmpty(s) 
           return -1;
       retrun 0;
     }
}

1.5 隊(duì)列

• 隊(duì)列與棧一樣，也是一種線性表灼舍，不同的是吼和，隊(duì)列可以在一端添加元素，在另一端取出元素骑素，也就是：先進(jìn)先出炫乓。從一端放入元素的操作稱為入隊(duì)，取出元素為出隊(duì)献丑，示例圖如下：

順序隊(duì)列

• 使用場(chǎng)景：因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn)末捣，在多線程阻塞隊(duì)列管理中非常適用

1.5.1 優(yōu)先隊(duì)列

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

1.5.2 循環(huán)隊(duì)列

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

1.6 樹

• 樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合创橄。把它叫做 “樹” 是因?yàn)樗雌饋硐褚豢玫箳斓臉渎嶙觯簿褪钦f它是根朝上，而葉朝下的妥畏。它具有以下的特點(diǎn)：
  • 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)邦邦；
  • 沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
  • 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)醉蚁；
  • 除了根節(jié)點(diǎn)外燃辖，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；

1.6.1 二叉樹

• 二叉樹是樹的特殊一種馍管，具有如下特點(diǎn)：

1郭赐、每個(gè)結(jié)點(diǎn)最多有兩顆子樹，結(jié)點(diǎn)的度最大為2确沸。
2捌锭、左子樹和右子樹是有順序的，次序不能顛倒罗捎。
3观谦、即使某結(jié)點(diǎn)只有一個(gè)子樹，也要區(qū)分左右子樹桨菜。

• 二叉樹是一種比較有用的折中方案豁状，它添加，刪除元素都很快倒得，并且在查找方面也有很多的算法優(yōu)化泻红，所以，二叉樹既有鏈表的好處霞掺，也有數(shù)組的好處谊路，是兩者的優(yōu)化方案，在處理大批量的動(dòng)態(tài)數(shù)據(jù)方面非常有用菩彬。
• 二叉樹有很多擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)缠劝，包括平衡二叉樹潮梯、紅黑樹、B+樹等惨恭，這些數(shù)據(jù)結(jié)構(gòu)二叉樹的基礎(chǔ)上衍生了很多的功能秉馏，在實(shí)際應(yīng)用中廣泛用到，例如mysql的數(shù)據(jù)庫索引結(jié)構(gòu)用的就是B+樹脱羡，還有HashMap的底層源碼中用到了紅黑樹萝究。

• 優(yōu)點(diǎn)：

二叉樹既有鏈表的好處，也有數(shù)組的好處轻黑，是兩者的優(yōu)化方案

• 缺點(diǎn)：

• 適用場(chǎng)景：

在處理大批量的動(dòng)態(tài)數(shù)據(jù)方面非常有用糊肤。

更多二叉樹相關(guān)知識(shí)請(qǐng)參考這篇博客：二叉樹總結(jié)創(chuàng)建，遍歷

1.6.2 二叉搜索樹

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

1.6.3 平衡二叉樹

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

1.7 圖

• 圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成氓鄙。其中馆揉，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)抖拦，邊是頂點(diǎn)的有序偶對(duì)升酣，若兩個(gè)頂點(diǎn)之間存在一條邊，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系态罪。
• 按照頂點(diǎn)指向的方向可分為無向圖和有向圖：

無向圖

有向圖

• 圖是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)噩茄，在存儲(chǔ)數(shù)據(jù)上有著比較復(fù)雜和高效的算法，分別有鄰接矩陣 复颈、鄰接表绩聘、十字鏈表、鄰接多重表耗啦、邊集數(shù)組等存儲(chǔ)結(jié)構(gòu)凿菩。

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

更多圖相關(guān)知識(shí)可以參考這篇文章：數(shù)據(jù)結(jié)構(gòu)—圖

1.8 散列表

• 散列表，也叫哈希表帜讲，是根據(jù)關(guān)鍵碼和值 (key和value) 直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)衅谷，通過key和value來映射到集合中的一個(gè)位置，這樣就可以很快找到集合中的對(duì)應(yīng)元素似将。

• 記錄的存儲(chǔ)位置=f(key)

• 這里的對(duì)應(yīng)關(guān)系 f 成為散列函數(shù)获黔，又稱為哈希 (hash函數(shù))，而散列表就是把Key通過一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字在验，然后就將該數(shù)字對(duì)數(shù)組長度進(jìn)行取余玷氏，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里腋舌，這種存儲(chǔ)空間可以充分利用數(shù)組的查找優(yōu)勢(shì)來查找元素预茄，所以查找的速度很快。

• 哈希表在應(yīng)用中也是比較常見的，就如Java中有些集合類就是借鑒了哈希原理構(gòu)造的耻陕，例如HashMap，HashTable等刨沦，利用hash表的優(yōu)勢(shì)诗宣，對(duì)于集合的查找元素時(shí)非常方便的，然而想诅，因?yàn)楣１硎腔跀?shù)組衍生的數(shù)據(jù)結(jié)構(gòu)召庞，在添加刪除元素方面是比較慢的，所以很多時(shí)候需要用到一種數(shù)組鏈表來做来破，也就是拉鏈法篮灼。拉鏈法是數(shù)組結(jié)合鏈表的一種結(jié)構(gòu)，較早前的hashMap底層的存儲(chǔ)就是采用這種結(jié)構(gòu)徘禁，直到j(luò)dk1.8之后才換成了數(shù)組加紅黑樹的結(jié)構(gòu)诅诱，其示例圖如下：

  
  
  散列表

• 從圖中可以看出，左邊很明顯是個(gè)數(shù)組送朱，數(shù)組的每個(gè)成員包括一個(gè)指針娘荡，指向一個(gè)鏈表的頭，當(dāng)然這個(gè)鏈表可能為空驶沼，也可能元素很多炮沐。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征回怜，找到正確的鏈表大年，再從鏈表中找出這個(gè)元素。

• 哈希表的應(yīng)用場(chǎng)景很多玉雾，當(dāng)然也有很多問題要考慮翔试，比如哈希沖突的問題，如果處理的不好會(huì)浪費(fèi)大量的時(shí)間抹凳，導(dǎo)致應(yīng)用崩潰遏餐。

• 優(yōu)點(diǎn)：

• 缺點(diǎn)：

• 適用場(chǎng)景：

更多散列表相關(guān)知識(shí)參考這篇博客：數(shù)據(jù)結(jié)構(gòu)—散列表

2. 常用算法

2.1 查找算法

2.1.1 二分查找

2.1.2 廣度優(yōu)先搜索算法

2.1.3 深度優(yōu)先搜索算法

2.2 排序算法

• 相關(guān)術(shù)語解釋

2.2.1 排序算法簡(jiǎn)介

排序算法分類

• 排序算法可以說是一項(xiàng)基本功又官，解決實(shí)際問題中經(jīng)常遇到，針對(duì)實(shí)際數(shù)據(jù)的特點(diǎn)選擇合適的排序算法可以使程序獲得更高的效率漫试，有時(shí)候排序的穩(wěn)定性還是實(shí)際問題中必須考慮的六敬，這篇博客對(duì)常見的排序算法進(jìn)行整理，包括：插入排序驾荣、選擇排序外构、冒泡排序、快速排序播掷、堆排序审编、歸并排序、希爾排序歧匈、二叉樹排序垒酬、計(jì)數(shù)排序、桶排序眯亦、基數(shù)排序伤溉。
• 按大的方向區(qū)分分為：比較排序和非比較排序。
  • 常見的排序算法都是比較排序妻率，非比較排序包括計(jì)數(shù)排序乱顾、桶排序和基數(shù)排序，非比較排序?qū)?shù)據(jù)有要求宫静，因?yàn)閿?shù)據(jù)本身包含了定位特征走净，所有才能不通過比較來確定元素的位置。
  • 比較排序的時(shí)間復(fù)雜度通常為O(n2)或者O(nlogn)孤里，比較排序的時(shí)間復(fù)雜度下界就是O(nlogn)伏伯，而非比較排序的時(shí)間復(fù)雜度可以達(dá)到O(n)，但是都需要額外的空間開銷捌袜。
  • 比較排序時(shí)間復(fù)雜度為O(nlogn)的證明：

  a1,a2,a3……an序列的所有排序有n!種说搅，所以滿足要求的排序a1',a2',a3'……an'（其中a1'<=a2'<=a3'……<=an'）的概率為1/n!÷驳龋基于輸入元素的比較排序弄唧，每一次比較的返回不是0就是1，這恰好可以作為決策樹的一個(gè)決策將一個(gè)事件分成兩個(gè)分支霍衫。比如冒泡排序時(shí)通過比較a1和a2兩個(gè)數(shù)的大小可以把序列分成a1,a2……an與a2,a1……an（氣泡a2上升一個(gè)身位）兩種不同的結(jié)果候引，因此比較排序也可以構(gòu)造決策樹。根節(jié)點(diǎn)代表原始序列a1,a2,a3……an敦跌，所有葉子節(jié)點(diǎn)都是這個(gè)序列的重排（共有n!個(gè)澄干，其中有一個(gè)就是我們排序的結(jié)果a1',a2',a3'……an'）。如果每次比較的結(jié)果都是等概率的話（恰好劃分為概率空間相等的兩個(gè)事件），那么二叉樹就是高度平衡的麸俘，深度至少是log(n!)辩稽。
  又因?yàn)?1. n! < nn ,兩邊取對(duì)數(shù)就得到log(n!)<nlog(n)，所以log(n!) = O(nlogn).
  2. n!=n(n-1)(n-2)(n-3)…1 > (n/2)^(n/2) 兩邊取對(duì)數(shù)得到 log(n!) > (n/2)log(n/2) = Ω(nlogn)疾掰，所以 log(n!) = Ω(nlogn)搂誉。
  因此log(n!)的增長速度與 nlogn 相同,即 log(n!)=Θ(nlogn)，這就是通用排序算法的最低時(shí)間復(fù)雜度O(nlogn)的依據(jù)静檬。

2.2.2 排序算法比較

2.2.2.1 穩(wěn)定性比較

• 插入排序、冒泡排序并级、二叉樹排序拂檩、二路歸并排序及其他線形排序是穩(wěn)定的；

• 選擇排序嘲碧、希爾排序稻励、快速排序、堆排序是不穩(wěn)定的愈涩。

2.2.2.2 時(shí)間復(fù)雜度比較

2.2.2.3 輔助空間比較

• 線形排序、二路歸并排序的輔助空間為O(n),其它排序的輔助空間為O(1)

2.2.2.4 其他比較

• 插入履婉、冒泡排序的速度較慢煤篙，但參加排序的序列局部或整體有序時(shí)，這種排序能達(dá)到較快的速度毁腿。

• 反而在這種情況下辑奈，快速排序反而慢了。

• 當(dāng)n較小時(shí)已烤，對(duì)穩(wěn)定性不作要求時(shí)宜用選擇排序鸠窗，對(duì)穩(wěn)定性有要求時(shí)宜用插入或冒泡排序。

• 若待排序的記錄的關(guān)鍵字在一個(gè)明顯有限范圍內(nèi)時(shí),且空間允許是用桶排序胯究。

• 當(dāng)n較大時(shí)稍计，關(guān)鍵字元素比較隨機(jī)，對(duì)穩(wěn)定性沒要求宜用快速排序裕循。

• 當(dāng)n較大時(shí)臣嚣，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對(duì)穩(wěn)定性有要求時(shí)费韭，空間允許的情況下茧球。宜用歸并排序。

• 當(dāng)n較大時(shí)星持，關(guān)鍵字元素可能出現(xiàn)本身是有序的抢埋，對(duì)穩(wěn)定性沒有要求時(shí)宜用堆排序。

2.2.3 排序算法實(shí)現(xiàn)

2.2.3.1 插入排序

算法簡(jiǎn)介

• 插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列揪垄，對(duì)于未排序數(shù)據(jù)穷吮，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入饥努。插入排序在實(shí)現(xiàn)上捡鱼，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中酷愧，需要反復(fù)把已排序元素逐步向后挪位驾诈，為最新元素提供插入空間。

• 算法描述

一般來說溶浴，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)乍迄。具體算法描述如下：

1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序士败；
2. 取出下一個(gè)元素闯两，在已經(jīng)排序的元素序列中從后向前掃描；
3. 如果該元素（已排序）大于新元素谅将，將該元素移到下一位置漾狼；
   重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置饥臂；
4. 將新元素插入到該位置后逊躁；
5. 重復(fù)步驟2~5。

• 動(dòng)態(tài)圖演示過程

插入排序

• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(n) 最壞情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

算法實(shí)現(xiàn)

• 數(shù)列前面部分看為有序擅笔，依次將后面的無序數(shù)列元素插入到前面的有序數(shù)列中志衣，初始狀態(tài)有序數(shù)列僅有一個(gè)元素，即首元素猛们。在將無序數(shù)列元素插入有序數(shù)列的過程中念脯，采用了逆序遍歷有序數(shù)列，相較于順序遍歷會(huì)稍顯繁瑣弯淘，但當(dāng)數(shù)列本身已近排序狀態(tài)效率會(huì)更高绿店。
• 時(shí)間復(fù)雜度：O(N2) 　　穩(wěn)定性：穩(wěn)定
• 遍歷數(shù)組，遍歷到i時(shí)庐橙，a0,a1...ai-1是已經(jīng)排好序的假勿，取出ai，從ai-1開始向前和每個(gè)比較大小态鳖，如果小于转培，則將此位置元素向后移動(dòng)，繼續(xù)先前比較浆竭，如果不小于浸须，則放到正在比較的元素之后惨寿。可見相等元素比較是删窒，原來靠后的還是拍在后邊裂垦，所以插入排序是穩(wěn)定的。
• 當(dāng)待排序的數(shù)據(jù)基本有序時(shí)肌索，插入排序的效率比較高蕉拢，只需要進(jìn)行很少的數(shù)據(jù)移動(dòng)。
• C語言實(shí)現(xiàn)代碼：

void insertion_sort (int a[], int n) {
    int i,j,v;
    for (i=1; i<n; i++) {　　　　  //如果第i個(gè)元素小于第j個(gè)诚亚，則第j個(gè)向后移動(dòng)
        for (v=a[i], j=i-1; j>=0&&v<a[j]; j--)
            a[j+1]=a[j];
        a[j+1]=v;
    }
}

• C++實(shí)現(xiàn)代碼：

/*插入排序*/
void insertSort(vector<int> &arr, int bgn, int end)
{
    for (int i = bgn + 1; i < end; ++i)
    {
        /*
        * 分為1,2兩部分處理晕换，可以囊括j = beg - 1時(shí)的情況
        * 即需要將arr[i]插入到首元素前的位置，若使用一個(gè)for
        * 包括這兩部分站宗，則會(huì)在發(fā)生這種情況時(shí)退出
        */
        /*1*/
        int j = i - 1;
        for ( ; j >= bgn; --j)
            if (arr[j] <= arr[I])
                break;
        /*2*/
        if (j != i - 1)
        {
            int temp = arr[i];
            for (int k = i; k > j + 1; --k)
            {
                arr[k] = arr[k - 1];
            }
            arr[j + 1] = temp;
        }
    }
}

2.2.3.2 選擇排序

算法簡(jiǎn)介

• 選擇排序（Selection Sort）

表現(xiàn)最穩(wěn)定的排序算法之一届巩，因?yàn)闊o論什么數(shù)據(jù)進(jìn)去都是O(n2)的時(shí)間復(fù)雜度，所以用到它的時(shí)候份乒，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧腕唧。理論上講或辖，選擇排序可能也是平時(shí)排序一般人想到的最多的排序方法了吧。
選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法枣接。它的工作原理：首先在未排序序列中找到最兴滔尽（大）元素，存放到排序序列的起始位置但惶，然后耳鸯，再從剩余未排序元素中繼續(xù)尋找最小（大）元素膀曾，然后放到已排序序列的末尾县爬。以此類推，直到所有元素均排序完畢添谊。

• 算法描述

n個(gè)記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果财喳。具體算法描述如下：

1. 初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空斩狱；
2. 第i趟排序(i=1,2,3…n-1)開始時(shí)耳高，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]所踊，將它與無序區(qū)的第1個(gè)記錄R交換泌枪，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)；
3. n-1趟結(jié)束秕岛，數(shù)組有序化了碌燕。

• 動(dòng)態(tài)圖演示過程
  選擇排序

• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(n2) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

算法實(shí)現(xiàn)

• 首先初始化最小元素索引值為首元素误证，依次遍歷待排序數(shù)列，若遇到小于該最小索引位置處的元素則刷新最小索引為該較小元素的位置陆蟆，直至遇到尾元素雷厂，結(jié)束一次遍歷，并將最小索引處元素與首元素交換叠殷；然后改鲫，初始化最小索引值為第二個(gè)待排序數(shù)列元素位置，同樣的操作林束，可得到數(shù)列第二個(gè)元素即為次小元素像棘；以此類推。
• 時(shí)間復(fù)雜度：O(N2) 　　穩(wěn)定性：不穩(wěn)定
• 遍歷數(shù)組壶冒，遍歷到i時(shí)缕题，a0,a1...ai-1是已經(jīng)排好序的，然后從i到n選擇出最小的胖腾，記錄下位置烟零，如果不是第i個(gè)，則和第i個(gè)元素交換咸作。此時(shí)第i個(gè)元素可能會(huì)排到相等元素之后锨阿，造成排序的不穩(wěn)定猬仁。
• C語言實(shí)現(xiàn)代碼：

void selection_sort (int a[], int n) {
    int i,j,pos,tmp;
    for (i=0; i<n-1; i++) {　　　　  //尋找最小值的下標(biāo)
        for (pos=i, j=i+1; j<n; j++)
            if (a[pos]>a[j])
                pos=j;
        if (pos != i) {
            tmp=a[I];
            a[i]=a[pos];
            a[pos]=tmp;
        }
    }
}

2.2.3.3 冒泡排序

算法簡(jiǎn)介

• 冒泡排序（Bubble Sort）

冒泡排序是一種簡(jiǎn)單的排序算法吴叶。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素障癌，如果它們的順序錯(cuò)誤就把它們交換過來桐智。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換末早，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端说庭。

• 算法描述

1. 比較相鄰的元素然磷。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)口渔；
2. 對(duì)每一對(duì)相鄰元素作同樣的工作样屠，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)缺脉；
3. 針對(duì)所有的元素重復(fù)以上的步驟痪欲，除了最后一個(gè)；
4. 重復(fù)步驟1~3攻礼，直到排序完成业踢。

• 動(dòng)態(tài)圖演示過程

  
  
  冒泡排序
• 最佳情況：T(n) = O(n) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

算法實(shí)現(xiàn)

• 依次比較相鄰兩元素，若前一元素大于后一元素則交換之礁扮，直至最后一個(gè)元素即為最大知举；然后重新從首元素開始重復(fù)同樣的操作瞬沦，直至倒數(shù)第二個(gè)元素即為次大元素；依次類推雇锡。如同水中的氣泡逛钻，依次將最大或最小元素氣泡浮出水面。
• 時(shí)間復(fù)雜度：O(N2) 　　穩(wěn)定性：穩(wěn)定
• 冒泡排序的名字很形象锰提，實(shí)際實(shí)現(xiàn)是相鄰兩節(jié)點(diǎn)進(jìn)行比較曙痘，大的向后移一個(gè)，經(jīng)過第一輪兩兩比較和移動(dòng)立肘，最大的元素移動(dòng)到了最后边坤，第二輪次大的位于倒數(shù)第二個(gè)，依次進(jìn)行谅年。這是最基本的冒泡排序茧痒，還可以進(jìn)行一些優(yōu)化。
• 優(yōu)化一：如果某一輪兩兩比較中沒有任何元素交換融蹂，這說明已經(jīng)都排好序了旺订，算法結(jié)束，可以使用一個(gè)Flag做標(biāo)記超燃，默認(rèn)為false耸峭，如果發(fā)生交互則置為true，每輪結(jié)束時(shí)檢測(cè)Flag淋纲，如果為true則繼續(xù)，如果為false則返回院究。
• 優(yōu)化二：某一輪結(jié)束位置為j洽瞬，但是這一輪的最后一次交換發(fā)生在lastSwap的位置，則lastSwap到j(luò)之間是排好序的业汰，下一輪的結(jié)束點(diǎn)就不必是j--了伙窃，而直接到lastSwap即可，代
• C語言實(shí)現(xiàn)代碼：

void bubble_sort (int a[], int n) {
    int i, j, lastSwap, tmp;
    for (j=n-1; j>0; j=lastSwap) {        lastSwap=0;     //每一輪要初始化為0样漆，防止某一輪未發(fā)生交換为障，lastSwap保留上一輪的值進(jìn)入死循環(huán)
        for (i=0; i<j; i++) {
            if (a[i] > a[i+1]) {
                tmp=a[I];
                a[i]=a[i+1];
                a[i+1]=tmp;
　　　　　　　　   //最后一次交換位置的坐標(biāo)
                lastSwap = I;
            }
        }
    }
}

2.2.3.4 快速排序

算法簡(jiǎn)介

• 快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小放祟，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序鳍怨，以達(dá)到整個(gè)序列有序。

• 算法描述

快速排序使用分治法來把一個(gè)串（list）分為兩個(gè)子串（sub-lists）跪妥。
具體算法描述如下：

1. 從數(shù)列中挑出一個(gè)元素鞋喇，稱為 “基準(zhǔn)”（pivot）；
2. 重新排序數(shù)列眉撵，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面侦香，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）落塑。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置罐韩。這個(gè)稱為分區(qū)（partition）操作憾赁；
3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

• 動(dòng)態(tài)圖演示過程

快速排序

• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(nlogn)

算法實(shí)現(xiàn)

• 類似于選擇排序的定位思想）選一基準(zhǔn)元素散吵，依次將剩余元素中小于該基準(zhǔn)元素的值放置其左側(cè)龙考，大于等于該基準(zhǔn)元素的值放置其右側(cè)；然后错蝴，取基準(zhǔn)元素的前半部分和后半部分分別進(jìn)行同樣的處理洲愤；以此類推，直至各子序列剩余一個(gè)元素時(shí)顷锰，即排序完成（類比二叉樹的思想柬赐，from up to down）.

• 時(shí)間復(fù)雜度：O(NlogN) 　　穩(wěn)定性：不穩(wěn)定

• 快速排序首先找到一個(gè)基準(zhǔn)，下面程序以第一個(gè)元素作為基準(zhǔn)（pivot）官紫，然后先從右向左搜索肛宋，如果發(fā)現(xiàn)比pivot小，則和pivot交換束世，然后從左向右搜索酝陈，如果發(fā)現(xiàn)比pivot大，則和pivot交換毁涉，一直到左邊大于右邊沉帮，此時(shí)pivot左邊的都比它小，而右邊的都比它大贫堰，此時(shí)pivot的位置就是排好序后應(yīng)該在的位置穆壕，此時(shí)pivot將數(shù)組劃分為左右兩部分，可以遞歸采用該方法進(jìn)行其屏±快排的交換使排序成為不穩(wěn)定的。

• C語言實(shí)現(xiàn)代碼：

int mpartition(int a[], int l, int r) {
    int pivot = a[l];
 
    while (l<r) {
        while (l<r && pivot<=a[r]) r--;
        if (l<r) a[l++]=a[r];
        while (l<r && pivot>a[l]) l++;
        if (l<r) a[r--]=a[l];
    }
    a[l]=pivot;
    return l;
}
 
void quick_sort (int a[], int l, int r) {
 
    if (l < r) {
        int q = mpartition(a, l, r);
        msort(a, l, q-1);
        msort(a, q+1, r);
    }
}

C++ 實(shí)現(xiàn)代碼：

/*快排*/
void quickSort(vector<int> &arr, int bgn, int end)  //arr must be the reference of real param
{
    //數(shù)組arr空or僅有一個(gè)元素則退出
    if (bgn >= end - 1)
        return;

    int lindex = bgn;
    int rindex = end - 1;
    int std = arr[lindex];
    while (lindex < rindex)
    {
        while (lindex < rindex)
        {
            if (arr[rindex] < std)
            {
                arr[lindex++] = arr[rindex];
                break;
            }
            --rindex;
        }

        while (lindex < rindex)
        {
            if (arr[lindex] >= std)
            {
                arr[rindex--] = arr[lindex];
                break;
            }
            ++lindex;
        } 
    }

    arr[lindex] = std;
    quickSort(arr, bgn, lindex);
    quickSort(arr, rindex + 1, end);
}

2.2.3.5 堆排序

算法簡(jiǎn)介

• 堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法偎行。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)川背，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

• 算法描述

1. 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆蛤袒，此堆為初始的無序區(qū)熄云；
2. 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]妙真；
3. 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)皱碘，因此需要對(duì)當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，
4. 然后再次將R[1]與無序區(qū)最后一個(gè)元素交換隐孽，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)癌椿。
5. 不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1健蕊，則整個(gè)排序過程完成。

• 動(dòng)態(tài)圖演示過程

堆排序-過程1

堆排序-過程2

• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(nlogn) 平均情況：T(n) = O(nlogn)

算法實(shí)現(xiàn)

• 堆排序的思想借助于二叉堆中的最大堆得以實(shí)現(xiàn)踢俄。首先缩功，將待排序數(shù)列抽象為二叉樹，并構(gòu)造出最大堆都办；然后嫡锌，依次將最大元素（即根節(jié)點(diǎn)元素）與待排序數(shù)列的最后一個(gè)元素交換（即二叉樹最深層最右邊的葉子結(jié)點(diǎn)元素）；每次遍歷琳钉，刷新最后一個(gè)元素的位置（自減1）势木，直至其與首元素相交，即完成排序歌懒。
• 堆排序是把數(shù)組看作堆啦桌，第i個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)為第2i+1和2i+2個(gè)結(jié)點(diǎn)（不超出數(shù)組長度前提下），堆排序的第一步是建堆及皂，然后是取堆頂元素然后調(diào)整堆甫男。建堆的過程是自底向上不斷調(diào)整達(dá)成的，這樣當(dāng)調(diào)整某個(gè)結(jié)點(diǎn)時(shí)验烧，其左節(jié)點(diǎn)和右結(jié)點(diǎn)已經(jīng)是滿足條件的板驳，此時(shí)如果兩個(gè)子結(jié)點(diǎn)不需要?jiǎng)樱瑒t整個(gè)子樹不需要?jiǎng)影穑绻{(diào)整若治，則父結(jié)點(diǎn)交換到子結(jié)點(diǎn)位置，再以此結(jié)點(diǎn)繼續(xù)調(diào)整感混。
• 下述代碼使用的大頂堆直砂，建立好堆后堆頂元素為最大值，此時(shí)取堆頂元素即使堆頂元素和最后一個(gè)元素交換浩习，最大的元素處于數(shù)組最后，此時(shí)調(diào)整小了一個(gè)長度的堆济丘，然后再取堆頂和倒數(shù)第二個(gè)元素交換谱秽，依次類推，完成數(shù)據(jù)的非遞減排序摹迷。
• 堆排序的主要時(shí)間花在初始建堆期間疟赊，建好堆后，堆這種數(shù)據(jù)結(jié)構(gòu)以及它奇妙的特征峡碉，使得找到數(shù)列中最大的數(shù)字這樣的操作只需要O(1)的時(shí)間復(fù)雜度近哟，維護(hù)需要logn的時(shí)間復(fù)雜度。堆排序不適宜于記錄數(shù)較少的文件.
• C語言實(shí)現(xiàn)代碼：

void heapAdjust(int a[], int i, int nLength)
{
    int nChild;
    int nTemp;
    for (nTemp = a[i]; 2 * i + 1 < nLength; i = nChild)
    {
        // 子結(jié)點(diǎn)的位置=2*（父結(jié)點(diǎn)位置）+ 1
        nChild = 2 * i + 1;
        // 得到子結(jié)點(diǎn)中較大的結(jié)點(diǎn)
        if ( nChild < nLength-1 && a[nChild + 1] > a[nChild])
            ++nChild;
        // 如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)鲫寄，替換它的父結(jié)點(diǎn)
        if (nTemp < a[nChild])
        {
            a[i] = a[nChild];
            a[nChild]= nTemp;
        }
        else
        // 否則退出循環(huán)
            break;
    }
}
 
// 堆排序算法
void heap_sort(int a[],int length)
{
    int tmp;
    // 調(diào)整序列的前半部分元素吉执，調(diào)整完之后第一個(gè)元素是序列的最大的元素
    //length/2-1是第一個(gè)非葉節(jié)點(diǎn)疯淫，此處"/"為整除
    for (int i = length / 2 - 1; i >= 0; --i)
        heapAdjust(a, i, length);
    // 從最后一個(gè)元素開始對(duì)序列進(jìn)行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個(gè)元素
    for (int i = length - 1; i > 0; --i)
    {
        // 把第一個(gè)元素和當(dāng)前的最后一個(gè)元素交換戳玫，
        // 保證當(dāng)前的最后一個(gè)位置的元素都是在現(xiàn)在的這個(gè)序列之中最大的
      ///  Swap(&a[0], &a[I]);
          tmp = a[I];
          a[i] = a[0];
          a[0] = tmp;
        // 不斷縮小調(diào)整heap的范圍熙掺，每一次調(diào)整完畢保證第一個(gè)元素是當(dāng)前序列的最大值
        heapAdjust(a, 0, i);
    }
}

2.2.3.6 歸并排序

算法簡(jiǎn)介

• 歸并排序（Merge Sort）

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響咕宿，但表現(xiàn)比選擇排序好的多币绩，因?yàn)槭冀K都是O(n log n）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間府阀。
歸并排序是建立在歸并操作上的一種有效的排序算法缆镣。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。歸并排序是一種穩(wěn)定的排序方法试浙。將已有序的子序列合并董瞻，得到完全有序的序列；即先使每個(gè)子序列有序川队，再使子序列段間有序力细。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并固额。

• 算法描述

1. 把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列眠蚂；
2. 對(duì)這兩個(gè)子序列分別采用歸并排序；
3. 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列斗躏。

• 動(dòng)態(tài)圖演示過程

  
  
  歸并排序
• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(n) 最差情況：T(n) = O(nlogn) 平均情況：T(n) = O(nlogn)

算法實(shí)現(xiàn)

• 歸并排序是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用逝慧。首先考慮下如何將將二個(gè)有序數(shù)列合并。這個(gè)非常簡(jiǎn)單啄糙，只要從比較二個(gè)數(shù)列的第一個(gè)數(shù)笛臣，誰小就先取誰，取了后就在對(duì)應(yīng)數(shù)列中刪除這個(gè)數(shù)隧饼。然后再進(jìn)行比較沈堡，如果有數(shù)列為空，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可燕雁。這需要將待排序序列中的所有記錄掃描一遍诞丽，因此耗費(fèi)O(n)時(shí)間，而由完全二叉樹的深度可知拐格，整個(gè)歸并排序需要進(jìn)行.logn.次僧免，因此，總的時(shí)間復(fù)雜度為O(nlogn)捏浊。
• 歸并排序在歸并過程中需 要與原始記錄序列同樣數(shù)量的存儲(chǔ)空間存放歸并結(jié)果懂衩，因此空間復(fù)雜度為O(n)。
• 歸并算法需要兩兩比較，不存在跳躍浊洞，因此歸并排序是一種穩(wěn)定的排序算法牵敷。
• 有的地方看到在mergearray()合并有序數(shù)列時(shí)分配臨時(shí)數(shù)組，即每一步mergearray的結(jié)果存放的一個(gè)新的臨時(shí)數(shù)組里沛申，這樣會(huì)在遞歸中消耗大量的空間劣领。因此做出小小的變化。只需要new一個(gè)臨時(shí)數(shù)組铁材。后面的操作都共用這一個(gè)臨時(shí)數(shù)組尖淘。合并完后將臨時(shí)數(shù)組中排好序的部分寫回原數(shù)組。
• 歸并排序計(jì)算時(shí)間復(fù)雜度時(shí)可以很容易的列出遞歸方程著觉，也是計(jì)算時(shí)間復(fù)雜度的一種方法村生。
• C語言實(shí)現(xiàn)代碼：

void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;
 
    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
 
    while (i <= m)
        temp[k++] = a[i++];
 
    while (j <= n)
        temp[k++] = a[j++];
 
    for (i = 0; i < k; I++)
        a[first + i] = temp[I];
}
void merge_sort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        merge_sort(a, first, mid, temp);    //左邊有序
        merge_sort(a, mid + 1, last, temp); //右邊有序
        mergearray(a, first, mid, last, temp); //再將二個(gè)有序數(shù)列合并
    }
}

2.2.3.7 希爾排序

算法簡(jiǎn)介

• 希爾排序（Shell Sort）

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序饼丘，它是簡(jiǎn)單插入排序經(jīng)過改進(jìn)之后的一個(gè)更高效的版本趁桃，也稱為縮小增量排序，同時(shí)該算法是沖破O(n2）的第一批算法之一肄鸽。它與插入排序的不同之處在于卫病，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序典徘。
希爾排序是把記錄按下表的一定增量分組蟀苛，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少逮诲，每組包含的關(guān)鍵詞越來越多帜平，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組梅鹦，算法便終止裆甩。

• 算法描述

1. 我們來看下希爾排序的基本步驟，在此我們選擇增量gap=length/2齐唆，縮小增量繼續(xù)以gap = gap/2的方式嗤栓，這種增量選擇我們可以用一個(gè)序列來表示，{n/2,(n/2)/2...1}箍邮，稱為增量序列茉帅。希爾排序的增量序列的選擇與證明是個(gè)數(shù)學(xué)難題，我們選擇的這個(gè)增量序列是比較常用的媒殉，也是希爾建議的增量，稱為希爾增量摔敛，但其實(shí)這個(gè)增量序列不是最優(yōu)的廷蓉。此處我們做示例使用希爾增量。
2. 先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，
   具體算法描述：
3. 選擇一個(gè)增量序列t1桃犬，t2刹悴，…，tk攒暇，其中ti>tj土匀，tk=1；
4. 按增量序列個(gè)數(shù)k形用，對(duì)序列進(jìn)行k 趟排序就轧；
5. 每趟排序，根據(jù)對(duì)應(yīng)的增量ti田度，將待排序列分割成若干長度為m 的子序列妒御，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)镇饺，整個(gè)序列作為一個(gè)表來處理乎莉，表長度即為整個(gè)序列的長度。

• 動(dòng)態(tài)圖演示過程

  
  
  希爾排序
• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(nlog2 n) 最壞情況：T(n) = O(nlog2 n) 平均情況：T(n) =O(nlog2n)

算法實(shí)現(xiàn)

• 希爾排序是插入排序的改進(jìn)版奸笤。為了減少數(shù)據(jù)的移動(dòng)次數(shù)惋啃，在初始序列較大時(shí)取較大的步長，通常取序列長度的一半监右，此時(shí)只有兩個(gè)元素比較边灭，交換一次；之后步長依次減半直至步長為1秸侣，即為插入排序存筏，由于此時(shí)序列已接近有序，故插入元素時(shí)數(shù)據(jù)移動(dòng)的次數(shù)會(huì)相對(duì)較少味榛，效率得到了提高椭坚。
• 時(shí)間復(fù)雜度：通常認(rèn)為是O(N3/2) ，穩(wěn)定性：不穩(wěn)定
• 希爾排序是對(duì)插入排序的優(yōu)化搏色，基于以下兩個(gè)認(rèn)識(shí)：1. 數(shù)據(jù)量較小時(shí)插入排序速度較快善茎，因?yàn)閚和n2差距很小频轿；2. 數(shù)據(jù)基本有序時(shí)插入排序效率很高垂涯，因?yàn)楸容^和移動(dòng)的數(shù)據(jù)量少。
• 因此航邢，希爾排序的基本思想是將需要排序的序列劃分成為若干個(gè)較小的子序列耕赘，對(duì)子序列進(jìn)行插入排序，通過則插入排序能夠使得原來序列成為基本有序膳殷。這樣通過對(duì)較小的序列進(jìn)行插入排序操骡，然后對(duì)基本有序的數(shù)列進(jìn)行插入排序，能夠提高插入排序算法的效率。
• 希爾排序的劃分子序列不是像歸并排序那種的二分册招，而是采用的叫做增量的技術(shù)岔激，例如有十個(gè)元素的數(shù)組進(jìn)行希爾排序，首先選擇增量為10/2=5是掰，此時(shí)第1個(gè)元素和第（1+5）個(gè)元素配對(duì)成子序列使用插入排序進(jìn)行排序虑鼎，第2和（2+5）個(gè)元素組成子序列，完成后增量繼續(xù)減半為2键痛，此時(shí)第1個(gè)元素炫彩、第（1+2）、第（1+4）散休、第（1+6）媒楼、第（1+8）個(gè)元素組成子序列進(jìn)行插入排序。這種增量選擇方法的好處是可以使數(shù)組整體均勻有序戚丸，盡可能的減少比較和移動(dòng)的次數(shù)划址，二分法中即使前一半數(shù)據(jù)有序，后一半中如果有比較小的數(shù)據(jù)限府，還是會(huì)造成大量的比較和移動(dòng)夺颤，因此這種增量的方法和插入排序的配合更佳。
• 希爾排序的時(shí)間復(fù)雜度和增量的選擇策略有關(guān)胁勺，上述增量方法造成希爾排序的不穩(wěn)定性世澜。

希爾排序

• C語言實(shí)現(xiàn)代碼：

void shell_sort(int a[], int n)
{
    int d, i, j, temp; //d為增量
    for(d = n/2;d >= 1;d = d/2) //增量遞減到1使完成排序
    {
        for(i = d; i < n;i++)   //插入排序的一輪
        {
            temp = a[I];
            for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d)
            {
                a[j + d] = a[j];
            }
        a[j + d] = temp;
        }
    }
}

2.2.3.8 二叉樹排序

算法簡(jiǎn)介

• 排序
• 算法描述
• 動(dòng)態(tài)圖演示過程
• 時(shí)間復(fù)雜度：

算法實(shí)現(xiàn)

• 二叉樹排序法借助了數(shù)據(jù)結(jié)構(gòu)二叉排序樹，二叉排序數(shù)滿足三個(gè)條件：（1）若左子樹不空署穗，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值寥裂； （2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值案疲； （3）左封恰、右子樹也分別為二叉排序樹。根據(jù)這三個(gè)特點(diǎn)褐啡，用中序遍歷二叉樹得到的結(jié)果就是排序的結(jié)果诺舔。
• 二叉樹排序法需要首先根據(jù)數(shù)據(jù)構(gòu)建二叉排序樹，然后中序遍歷备畦，排序時(shí)間復(fù)雜度為O(nlogn)低飒，構(gòu)建二叉樹需要額外的O(n)的存儲(chǔ)空間，有相同的元素是可以設(shè)置排在后邊的放在右子樹懂盐，在中序變量的時(shí)候也會(huì)在后邊褥赊，所以二叉樹排序是穩(wěn)定的。
• 在實(shí)現(xiàn)此算法的時(shí)候遇到不小的困難莉恼，指針參數(shù)在函數(shù)中無法通過new賦值拌喉，后來采用取指針地址翼岁，然后函數(shù)設(shè)置BST** tree的方式解決。
• C語言實(shí)現(xiàn)代碼：

int arr[] = {7, 8, 8, 9, 5, 16, 5, 3,56,21,34,15,42};
 
struct BST{
    int number; //保存數(shù)組元素的值
    struct BST* left;
    struct BST* right;
};
 
void insertBST(BST** tree, int v) {
    if (*tree == NULL) {
        *tree = new BST;
        (*tree)->left=(*tree)->right=NULL;
        (*tree)->number=v;
        return;
    }
    if (v < (*tree)->number)
        insertBST(&((*tree)->left), v);
    else
        insertBST(&((*tree)->right), v);
}
 
void printResult(BST* tree) {
    if (tree == NULL)
        return;
    if (tree->left != NULL)
        printResult(tree->left);
    cout << tree->number << "  ";
    if (tree->right != NULL)
        printResult(tree->right);
}
 
void createBST(BST** tree, int a[], int n) {
    *tree = NULL;
    for (int i=0; i<n; I++)
        insertBST(tree, a[I]);
}
 
int main()
{
    int n = sizeof(arr)/sizeof(int);
 
    BST* root;
    createBST(&root, arr, n);
    printResult(root);
 
}

2.2.3.9 計(jì)數(shù)排序

算法簡(jiǎn)介

• 計(jì)數(shù)排序（Counting Sort）

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中司光。 作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)悉患。
計(jì)數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法残家。計(jì)數(shù)排序使用一個(gè)額外的數(shù)組C，其中第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)售躁。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置坞淮。它只能對(duì)整數(shù)進(jìn)行排序。

• 算法描述

1. 找出待排序的數(shù)組中最大和最小的元素陪捷；
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)回窘，存入數(shù)組C的第i項(xiàng)；
3. 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始市袖，每一項(xiàng)和前一項(xiàng)相加）啡直；
4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1苍碟。

• 動(dòng)態(tài)圖演示過程

計(jì)數(shù)排序-過程

• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(n+k) 最差情況：T(n) = O(n+k) 平均情況：T(n) = O(n+k)

當(dāng)輸入的元素是n 個(gè)0到k之間的整數(shù)時(shí)酒觅，它的運(yùn)行時(shí)間是 O(n + k)。計(jì)數(shù)排序不是比較排序微峰，排序的速度快于任何比較排序算法舷丹。由于用來計(jì)數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組蜓肆，需要大量時(shí)間和內(nèi)存颜凯。

算法實(shí)現(xiàn)

• 如果通過比較進(jìn)行排序，那么復(fù)雜度的下界是O(nlogn)仗扬，但是如果數(shù)據(jù)本身有可以利用的特征症概，可以不通過比較進(jìn)行排序，就能使時(shí)間復(fù)雜度降低到O(n)厉颤。
• 計(jì)數(shù)排序要求待排序的數(shù)組元素都是 整數(shù)穴豫，有很多地方都要去是0-K的正整數(shù)，其實(shí)負(fù)整數(shù)也可以通過都加一個(gè)偏移量解決的逼友。
• 計(jì)數(shù)排序的思想是精肃，考慮待排序數(shù)組中的某一個(gè)元素a，如果數(shù)組中比a小的元素有s個(gè)帜乞，那么a在最終排好序的數(shù)組中的位置將會(huì)是s+1司抱，如何知道比a小的元素有多少個(gè)，肯定不是通過比較去覺得黎烈，而是通過數(shù)字本身的屬性习柠，即累加數(shù)組中最小值到a之間的每個(gè)數(shù)字出現(xiàn)的次數(shù)（未出現(xiàn)則為0）匀谣，而每個(gè)數(shù)字出現(xiàn)的次數(shù)可以通過掃描一遍數(shù)組獲得。
• 計(jì)數(shù)排序的步驟：

計(jì)數(shù)排序的步驟：

1. 找出待排序的數(shù)組中最大和最小的元素（計(jì)數(shù)數(shù)組C的長度為max-min+1资溃，其中位置0存放min武翎，依次填充到最后一個(gè)位置存放max）
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
3. 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始溶锭，每一項(xiàng)和前一項(xiàng)相加）
4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)宝恶，每放一個(gè)元素就將C(i)減去1（反向填充是為了保證穩(wěn)定性）

• C語言實(shí)現(xiàn)代碼：

以下代碼中尋找最大和最小元素參考編程之美，比較次數(shù)為1.5n次趴捅。
計(jì)數(shù)排序適合數(shù)據(jù)分布集中的排序垫毙，如果數(shù)據(jù)太分散，會(huì)造成空間的大量浪費(fèi)拱绑，假設(shè)數(shù)據(jù)為（1,2,3,1000000）综芥，這就需要1000000的額外空間，并且有大量的空間浪費(fèi)和時(shí)間浪費(fèi)猎拨。

void findArrMaxMin(int a[], int size, int *min, int *max)
{
    if(size == 0) {
        return;
    }
    if(size == 1) {
        *min = *max = a[0];
        return;
    }
 
    *min = a[0] > a[1] ? a[1] : a[0];
    *max = a[0] <= a[1] ? a[1] : a[0];
 
 
    int i, j;
    for(i = 2, j = 3; i < size, j < size; i += 2, j += 2) {
        int tempmax = a[i] >= a[j] ? a[i] : a[j];
        int tempmin = a[i] < a[j] ? a[i] : a[j];
 
        if(tempmax > *max)
            *max = tempmax;
        if(tempmin < *min)
            *min = tempmin;
    }
 
    //如果數(shù)組元素是奇數(shù)個(gè)膀藐，那么最后一個(gè)元素在分組的過程中沒有包含其中，
    //這里單獨(dú)比較
    if(size % 2 != 0) {
        if(a[size -1] > *max)
            *max = a[size - 1];
        else if(a[size -1] < *min)
            *min = a[size -1];
    }
}
 
void count_sort(int a[], int b[], int n) {
    int max, min;
    findArrMaxMin(a, n, &min, &max);
    int numRange = max-min+1;
    int* counter = new int[numRange];
 
    int i, j, k;
    for (k=0; k<numRange; k++)
        counter[k]=0;
 
    for (i=0; i<n; I++)
        counter[a[i]-min]++;
 
    for (k=1; k<numRange; k++)
        counter[k] += counter[k-1];
 
    for (j=n-1; j>=0; j--) {
        int v = a[j];
        int index = counter[v-min]-1;
        b[index]=v;
        counter[v-min]--;
    }
}

2.2.3.10 桶排序

算法簡(jiǎn)介

• 桶排序（Bucket Sort）

桶排序是計(jì)數(shù)排序的升級(jí)版红省。它利用了函數(shù)的映射關(guān)系消请，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。
桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排.

• 算法描述

1. 人為設(shè)置一個(gè)BucketSize寂屏，作為每個(gè)桶所能放置多少個(gè)不同數(shù)值（例如當(dāng)BucketSize==5時(shí)肢娘，該桶可以存放｛1,2,3,4,5｝這幾種數(shù)字，但是容量不限，即可以存放100個(gè)3）；
2. 遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去需频；
3. 對(duì)每個(gè)不是空的桶進(jìn)行排序，可以使用其它排序方法筷凤，也可以遞歸使用桶排序昭殉；
4. 從不是空的桶里把排好序的數(shù)據(jù)拼接起來。
5. 注意藐守，如果遞歸使用桶排序?yàn)楦鱾€(gè)桶排序挪丢，則當(dāng)桶數(shù)量為1時(shí)要手動(dòng)減小BucketSize增加下一循環(huán)桶的數(shù)量，否則會(huì)陷入死循環(huán)卢厂，導(dǎo)致內(nèi)存溢出乾蓬。

• 動(dòng)態(tài)圖演示過程

  
  
  桶排序1
  
  
  桶排序2

• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(n+k) 最差情況：T(n) = O(n+k) 平均情況：T(n) = O(n2)

桶排序最好情況下使用線性時(shí)間O(n)，桶排序的時(shí)間復(fù)雜度慎恒，取決與對(duì)各個(gè)桶之間數(shù)據(jù)進(jìn)行排序的時(shí)間復(fù)雜度任内，因?yàn)槠渌糠值臅r(shí)間復(fù)雜度都為O(n)撵渡。很顯然，桶劃分的越小死嗦，各個(gè)桶之間的數(shù)據(jù)越少趋距，排序所用的時(shí)間也會(huì)越少。但相應(yīng)的空間消耗就會(huì)增大越除。

算法實(shí)現(xiàn)

• 實(shí)現(xiàn)線性排序棚品，但當(dāng)元素間值得大小有較大差距時(shí)會(huì)帶來內(nèi)存空間的較大浪費(fèi)。首先廊敌，找出待排序列中得最大元素max，申請(qǐng)內(nèi)存大小為max + 1的桶（數(shù)組）并初始化為0门怪；然后骡澈，遍歷排序數(shù)列，并依次將每個(gè)元素作為下標(biāo)的桶元素值自增1掷空；最后肋殴，遍歷桶元素，并依次將值非0的元素下標(biāo)值載入排序數(shù)列（桶元素>1表明有值大小相等的元素坦弟，此時(shí)依次將他們載入排序數(shù)列）护锤，遍歷完成，排序數(shù)列便為有序數(shù)列酿傍。
• 時(shí)間復(fù)雜度：O(x*N) 　　穩(wěn)定性：穩(wěn)定
• 假設(shè)有一組長度為N的待排關(guān)鍵字序列K[1....n]烙懦。首先將這個(gè)序列劃分成M個(gè)的子區(qū)間(桶) 。然后基于某種映射函數(shù) 赤炒，將待排序列的關(guān)鍵字k映射到第i個(gè)桶中(即桶數(shù)組B的下標(biāo) i) 氯析，那么該關(guān)鍵字k就作為B[i]中的元素(每個(gè)桶B[i]都是一組大小為N/M的序列)。接著對(duì)每個(gè)桶B[i]中的所有元素進(jìn)行比較排序(可以使用快排)莺褒。然后依次枚舉輸出B[0]....B[M]中的全部內(nèi)容即是一個(gè)有序序列掩缓。
• 桶排序利用函數(shù)的映射關(guān)系，減少了計(jì)劃所有的比較操作遵岩，是一種Hash的思想你辣，可以用在海量數(shù)據(jù)處理中。
• 我覺得計(jì)數(shù)排序也可以看作是桶排序的特例尘执，數(shù)組關(guān)鍵字范圍為N舍哄，劃分為N個(gè)桶
• C語言實(shí)現(xiàn)代碼：

/*桶排序*/
void bucketSort(vector<int> &arr)
{
    int max = getMaxValue(arr);
    int *pBuf = new int[max + 1];

    memset(pBuf, 0, (max + 1)*sizeof(int));
    for (auto const i : arr)
        ++pBuf[I];

    for (int i = 0, j = 0; i <= max; ++i)
    {
        while (pBuf[i]--)
            arr[j++] = i;
    }
    delete []pBuf;
}

2.2.3.11 基數(shù)排序

算法簡(jiǎn)介

• 基數(shù)排序（Radix Sort）

基數(shù)排序也是非比較的排序算法，對(duì)每一位進(jìn)行排序誊锭，從最低位開始排序蠢熄，復(fù)雜度為O(kn),為數(shù)組長度，k為數(shù)組中的數(shù)的最大的位數(shù)炉旷；
基數(shù)排序是按照低位先排序签孔，然后收集叉讥；再按照高位排序，然后再收集饥追；依次類推图仓，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的但绕，先按低優(yōu)先級(jí)排序救崔，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前捏顺，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前六孵。基數(shù)排序基于分別排序幅骄，分別收集劫窒，所以是穩(wěn)定的。

• 算法描述

1. 取得數(shù)組中的最大數(shù)拆座，并取得位數(shù)主巍；
2. arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組挪凑；
3. 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）孕索；

• 動(dòng)態(tài)圖演示過程

基數(shù)排序

• 時(shí)間復(fù)雜度：最佳情況：T(n) = O(n * k) 最差情況：T(n) = O(n * k) 平均情況：T(n) = O(n * k)

基數(shù)排序有兩種方法：
MSD 從高位開始進(jìn)行排序 LSD 從低位開始進(jìn)行排序
基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶
計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值
桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值

算法實(shí)現(xiàn)

• 桶排序的改進(jìn)版躏碳，桶的大小固定為10搞旭，減少了內(nèi)存空間的開銷。首先菇绵，找出待排序列中得最大元素max选脊，并依次按max的低位到高位對(duì)所有元素排序；桶元素10個(gè)元素的大小即為待排序數(shù)列元素對(duì)應(yīng)數(shù)值為相等元素的個(gè)數(shù)脸甘，即每次遍歷待排序數(shù)列恳啥，桶將其按對(duì)應(yīng)數(shù)值位大小分為了10個(gè)層級(jí)，桶內(nèi)元素值得和為待排序數(shù)列元素個(gè)數(shù)丹诀。
• 時(shí)間復(fù)雜度：O(x*N) 　　穩(wěn)定性：穩(wěn)定
• 基數(shù)排序也可以看作一種桶排序钝的，不斷的使用不同的標(biāo)準(zhǔn)對(duì)數(shù)據(jù)劃分到桶中，最終實(shí)現(xiàn)有序铆遭∠踝基數(shù)排序的思想是對(duì)數(shù)據(jù)選擇多種基數(shù)，對(duì)每一種基數(shù)依次使用桶排序碗脊。
• 基數(shù)排序的步驟：以整數(shù)為例，將整數(shù)按十進(jìn)制位劃分橄妆，從低位到高位執(zhí)行以下過程衙伶。

1. 從個(gè)位開始祈坠，根據(jù)0~9的值將數(shù)據(jù)分到10個(gè)桶桶，例如12會(huì)劃分到2號(hào)桶中矢劲。
2. 將0~9的10個(gè)桶中的數(shù)據(jù)順序放回到數(shù)組中赦拘。
3. 重復(fù)上述過程，一直到最高位芬沉。

• C語言實(shí)現(xiàn)代碼：

int getNumInPos(int num,int pos) //獲得某個(gè)數(shù)字的第pos位的值
{
    int temp = 1;
    for (int i = 0; i < pos - 1; I++)
        temp *= 10;
 
    return (num / temp) % 10;
}
 
#define RADIX_10 10    //十個(gè)桶躺同，表示每一位的十個(gè)數(shù)字
#define KEYNUM 5     //整數(shù)位數(shù)
void radix_sort(int* pDataArray, int iDataNum)
{
    int *radixArrays[RADIX_10];    //分別為0~9的序列空間
    for (int i = 0; i < RADIX_10; I++)
    {
        radixArrays[i] = new int[iDataNum];
        radixArrays[i][0] = 0;    //index為0處記錄這組數(shù)據(jù)的個(gè)數(shù)
    }
 
    for (int pos = 1; pos <= KEYNUM; pos++)    //從個(gè)位開始到31位
    {
        for (int i = 0; i < iDataNum; i++)    //分配過程
        {
            int num = getNumInPos(pDataArray[i], pos);
            int index = ++radixArrays[num][0];
            radixArrays[num][index] = pDataArray[I];
        }
 
        for (int i = 0, j =0; i < RADIX_10; i++) //寫回到原數(shù)組中，復(fù)位radixArrays
        {
            for (int k = 1; k <= radixArrays[i][0]; k++)
                pDataArray[j++] = radixArrays[i][k];
            radixArrays[i][0] = 0;
        }
    }
}

• C++實(shí)現(xiàn)代碼：

/*基數(shù)排序*/
//1. 計(jì)數(shù)排序丸逸，按整形數(shù)值單位進(jìn)行排序
void countSort(vector<int> &arr, int exp)
{
    int bucket[10] = { 0 };
    int arrSize = arr.size();
    int *pTemp = new int[arrSize];
    memset(pTemp, 0, arrSize * sizeof(int));

    //統(tǒng)計(jì)單位exp各數(shù)值計(jì)數(shù)值
    for (auto const val : arr)
        ++bucket[(val / exp) % 10];

    //計(jì)數(shù)分層
    for (int i = 1; i < 10; ++i)
        bucket[i] += bucket[i - 1];

    //按exp位大小用數(shù)組arr元素填充pTemp
    for (int i = arrSize - 1; i >= 0; --i)
        pTemp[ --bucket[(arr[i] / exp) % 10] ] = arr[i];
/*bugs*/
#if 0
    //bug1: bucket各層次的計(jì)數(shù)值沒遍歷一次相應(yīng)自減1
    for (auto const val : arr)
        pTemp[bucket[(val / exp) % 10] - 1] = val;
    //bug2: arr數(shù)組元素每次排序時(shí)蹋艺，下標(biāo)應(yīng)從大到小遍歷，否則無法實(shí)現(xiàn)排序
    for (auto const val : arr)
        pTemp[ --bucket[(val / exp) % 10] ] = val;
#endif

    //pTemp -> arr
    for (int i = 0; i < arrSize; ++i)
        arr[i] = pTemp[i];
    delete []pTemp;
}
//2. 合并各單位計(jì)數(shù)排序結(jié)果
void radixSort(vector<int> &arr)
{
    int max = getMaxValue(arr);
    for (int exp = 1; max / exp != 0; exp *= 10)
        countSort(arr, exp);
}

2.2.3.12

Reference

[1]https://www.cnblogs.com/zhaoshuai1215/p/3448154.html

[2]https://www.cnblogs.com/KevinYZLong/p/5880151.html

3. https://blog.csdn.net/hellozhxy/article/details/79911867