算法概念
1.算法分類
十種常見(jiàn)排序算法可以分為兩大類：
- 比較類排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)朝群，因此也稱為非線性時(shí)間比較類排序。
- 非比較類排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序中符，它可以突破基于比較排序的時(shí)間下界姜胖，以線性時(shí)間運(yùn)行，因此也稱為線性時(shí)間非比較類排序淀散。
算法分類2.相關(guān)概念
- 穩(wěn)定：如果a原本在b前面右莱，而a=b，排序之后a仍然在b的前面档插。
- 不穩(wěn)定：如果a原本在b的前面慢蜓，而a=b，排序之后 a 可能會(huì)出現(xiàn)在 b 的后面郭膛。
- 時(shí)間復(fù)雜度：對(duì)排序數(shù)據(jù)的總的操作次數(shù)晨抡。反映當(dāng)n變化時(shí)，操作次數(shù)呈現(xiàn)什么規(guī)律。
- 空間復(fù)雜度：是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量耘柱，它也是數(shù)據(jù)規(guī)模n的函數(shù)
3.算法復(fù)雜度
排序方法 時(shí)間復(fù)雜度(平均) 時(shí)間復(fù)雜度(最壞) 時(shí)間復(fù)雜度(最好) 空間復(fù)雜度 穩(wěn)定性 插入排序 穩(wěn)定 希爾排序 穩(wěn)定 選擇排序 穩(wěn)定 冒泡排序 穩(wěn)定 快速排序 穩(wěn)定 堆排序 穩(wěn)定 歸并排序 穩(wěn)定 計(jì)數(shù)排序 穩(wěn)定 桶排序 穩(wěn)定 基數(shù)排序 穩(wěn)定
十種算法
一如捅、插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列调煎，對(duì)于未排序數(shù)據(jù)镜遣，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入汛蝙。
算法描述
- 一般來(lái)說(shuō)烈涮，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
- 從第一個(gè)元素開(kāi)始窖剑，該元素可以認(rèn)為已經(jīng)被排序坚洽；
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描西土；
- 如果該元素（已排序）大于新元素讶舰，將該元素移到下一位置；
- 重復(fù)步驟3需了，直到找到已排序的元素小于或者等于新元素的位置跳昼；
- 將新元素插入到該位置后；
- 重復(fù)步驟2~5肋乍。
算法演示
插入排序
代碼實(shí)現(xiàn)
- (NSArray *)insertionSort:(NSArray *)arr { NSMutableArray *array = [[NSMutableArray alloc] initWithArray:arr]; int preIndex = 0; id current; for (int i = 1; i < array.count; i++) { preIndex = i - 1; current = array[I]; while (preIndex >= 0 && array[preIndex] > current) { array[preIndex + 1] = array[preIndex]; preIndex--; } array[preIndex + 1] = current; } return array; }
算法分析
插入排序在實(shí)現(xiàn)上鹅颊，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過(guò)程中墓造，需要反復(fù)把已排序元素逐步向后挪位堪伍，為最新元素提供插入空間。
二觅闽、希爾排序（Shell Sort）
希爾排序也是一種插入排序帝雇，它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序蛉拙，同時(shí)該算法是沖破
的第一批算法之一尸闸。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素孕锄。希爾排序又叫縮小增量排序吮廉。
希爾排序是把記錄按下表的一定增量分組，對(duì)每組使用直接插入排序算法排序畸肆；隨著增量逐漸減少宦芦，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)恼除，整個(gè)文件恰被分成一組踪旷，算法便終止。
算法描述
增量gap的范圍: 1<= gap < 待排序數(shù)組的長(zhǎng)度 （gap 需為 int 值）
增量的取值: 一般的初次取序列（數(shù)組）的一半為增量豁辉，以后每次減半令野，直到增量為1。
第一個(gè)增量=數(shù)組的長(zhǎng)度/2,
第二個(gè)增量= 第一個(gè)增量/2,
第三個(gè)增量=第二個(gè)增量/2,
以此類推徽级，最后一個(gè)增量=1气破。
- 根據(jù)增量gap將數(shù)組分成若干組；
- 分別對(duì)每個(gè)增量序列進(jìn)行插入排序餐抢；
- 重復(fù)步驟1~2现使，直至gap=1。
算法演示
希爾排序
代碼實(shí)現(xiàn)
- (NSArray *)ShellSort:(NSArray *)arr { NSMutableArray *array = [[NSMutableArray alloc] initWithArray:arr]; int len = (int)array.count; id temp; int gap = len / 2; while (gap > 0) { for (int i = gap; i < array.count; i++) { temp = array[I]; int preIndex = i - gap; while (preIndex >= 0 && array[preIndex] > temp) { array[preIndex + gap] = array[preIndex]; preIndex -= gap; } array[preIndex + gap] = temp; } gap /= 2; } return array; }
算法分析
希爾排序的核心在于間隔序列的設(shè)定旷痕。既可以提前設(shè)定好間隔序列碳锈，也可以動(dòng)態(tài)的定義間隔序列。動(dòng)態(tài)定義間隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的欺抗。
由于多次插入排序售碳，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序绞呈，但在不同的插入排序過(guò)程中贸人，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂佃声，所以希爾排序是不穩(wěn)定的艺智。
三、選擇排序（Selection Sort）
選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法圾亏。它的工作原理：首先在未排序序列中找到最惺稹（大）元素，存放到排序序列的起始位置召嘶，然后父晶，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素弄跌，然后放到已排序序列的末尾甲喝。以此類推，直到所有元素均排序完畢铛只。
算法描述
n個(gè)記錄的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果埠胖。
- 初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空淳玩；
- 第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí)直撤，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]蜕着，將它與無(wú)序區(qū)的第1個(gè)記錄R交換谋竖，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)红柱；
- n-1趟結(jié)束，數(shù)組有序化了
算法演示
選擇排序
代碼實(shí)現(xiàn)
- (NSArray *)selectionSort:(NSArray *)arr { NSMutableArray *array = [[NSMutableArray alloc] initWithArray:arr]; int len = (int)array.count; int minIndex; id temp; for (int i = 0; i < len - 1; i++) { minIndex = I; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { // 尋找最小的數(shù) minIndex = j; // 將最小數(shù)的索引保存 } } temp = arr[i]; array[i] = arr[minIndex]; array[minIndex] = temp; } return arr; }
算法分析
表現(xiàn)最穩(wěn)定的排序算法之一蓖乘，因?yàn)闊o(wú)論什么數(shù)據(jù)進(jìn)去都是
的時(shí)間復(fù)雜度锤悄，所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好嘉抒。唯一的好處可能就是不占用額外的內(nèi)存空間了吧零聚。
四、冒泡排序（Bubble Sort）
冒泡排序是一種簡(jiǎn)單的排序算法些侍。它重復(fù)地走訪過(guò)要排序的數(shù)列隶症，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)岗宣。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換蚂会，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端耗式。
算法描述
- 比較相鄰的元素颂龙。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)伦乔，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
- 針對(duì)所有的元素重復(fù)以上的步驟企巢，除了最后一個(gè)；
- 重復(fù)步驟1~3让蕾，直到排序完成浪规。
算法演示
冒泡排序
代碼實(shí)現(xiàn)
- (NSArray *)bubbleSort:(NSArray *)arr { NSMutableArray *array = [[NSMutableArray alloc] initWithArray:arr]; int len = (int)array.count; for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (array[j] > array[j+1]) { // 相鄰元素兩兩對(duì)比 id temp = array[j+1]; // 元素交換 array[j+1] = array[j]; array[j] = temp; } } } return arr; }
算法分析
程序員第一排序，你懂得~
五探孝、快速排序（Quick Sort）
快速排序的基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分笋婿，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序顿颅，以達(dá)到整個(gè)序列有序缸濒。
算法描述
快速排序使用分治法來(lái)把一個(gè)串（list）分為兩個(gè)子串（sub-lists）
- 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）粱腻；
- 重新排序數(shù)列庇配，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）绍些。在這個(gè)分區(qū)退出之后捞慌，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作柬批；
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序啸澡。
算法演示
快速排序
代碼實(shí)現(xiàn)
@property (nonatomic, strong) NSMutableArray *array; - (NSArray *)quickSort:(NSArray *)arr left:(int)left right:(int)right { self.array = [[NSMutableArray alloc] initWithArray:arr]; if (left < right) { int partitionIndex = [self partitionLeft:left right:right]; [self quickSort:self.array left:left right:partitionIndex-1]; [self quickSort:self.array left:partitionIndex+1 right:right]; } return self.array; } - (int)partitionLeft:(int)left right:(int)right { int pivot = left; // 設(shè)定基準(zhǔn)值（pivot） int index = pivot + 1; for (int i = index; i <= right; i++) { if (self.array[i] < self.array[pivot]) { [self swap:i j:index]; index++; } } [self swap:pivot j:index-1]; return index-1; } - (void)swap:(int)i j:(int)j { id temp = self.array[I]; self.array[i] = self.array[j]; self.array[j] = temp; }
六袖订、堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)嗅虏，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)著角。
算法描述
將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)旋恼。
1.1.假設(shè)給定無(wú)序序列結(jié)構(gòu)如下:
1.2.此時(shí)我們從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始（葉結(jié)點(diǎn)自然不用調(diào)整，第一個(gè)非葉子結(jié)點(diǎn) arr.length/2-1=5/2-1=1奄容，也就是下面的6結(jié)點(diǎn)）冰更，從左至右，從下至上進(jìn)行調(diào)整昂勒。
1.3.找到第二個(gè)非葉節(jié)點(diǎn)4蜀细，由于[4,9,8]中9元素最大，4和9交換戈盈。
1.4.這時(shí)奠衔，交換導(dǎo)致了子根[4,5,6]結(jié)構(gòu)混亂，繼續(xù)調(diào)整塘娶，[4,5,6]中6最大归斤，交換4和6。將堆頂元素R[1]與最后一個(gè)元素R[n]交換刁岸，此時(shí)得到新的無(wú)序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]脏里；
將堆頂元素9和末尾元素4進(jìn)行交換
由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆虹曙，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換迫横，得到新的無(wú)序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1酝碳，則整個(gè)排序過(guò)程完成矾踱。
3.1.重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義疏哗。
3.2.再將堆頂元素8與末尾元素5進(jìn)行交換呛讲，得到第二大元素8。
3.3.后續(xù)過(guò)程返奉，繼續(xù)進(jìn)行調(diào)整圣蝎，交換，如此反復(fù)進(jìn)行衡瓶，最終使得整個(gè)序列有序徘公。
算法演示
堆排序
代碼實(shí)現(xiàn)
- (NSArray *)HeapSort:(NSArray *)arr { NSMutableArray *array = [NSMutableArray arrayWithArray:arr]; // 初始化一個(gè)終止計(jì)算結(jié)點(diǎn)索引位置(一次排序后把最大值移動(dòng)到數(shù)組計(jì)算結(jié)點(diǎn)范圍的末尾) int endIndex = (int)(array.count - 1); while (endIndex > 0) { // 遍歷一次數(shù)組按照堆的規(guī)則排序一次 [self binaryTreeSortWithArray:array maxIndex:endIndex]; // 將建立堆得到的最大根與數(shù)組中最后一個(gè)數(shù)組互換 [array exchangeObjectAtIndex:0 withObjectAtIndex:endIndex--]; } return array; } /// 二叉樹(shù)規(guī)則(大根堆)排序 -- (排序范圍為索引為0的位置到待排序結(jié)點(diǎn)最大索引位置) - (void)binaryTreeSortWithArray:(NSMutableArray *)array maxIndex:(int)maxIndex { // 從可排序結(jié)點(diǎn)的最大索引處開(kāi)始進(jìn)行排序 for (int i = maxIndex; i >= 0; i--) { // 獲取移動(dòng)后的子結(jié)點(diǎn)的索引 int newIndex = [self compareNodesSizeWithArray:array maxIndex:maxIndex fatherNodeIndex:i]; while (newIndex > 0) { newIndex = [self compareNodesSizeWithArray:array maxIndex:maxIndex fatherNodeIndex:newIndex]; } } } /// 遞歸比較指定索引位置的結(jié)點(diǎn)與其左右子節(jié)點(diǎn)的大小 - (int)compareNodesSizeWithArray:(NSMutableArray *)array maxIndex:(int)maxIndex fatherNodeIndex:(int)fatherIndex { // 獲取當(dāng)前索引位置的左右子節(jié)點(diǎn)索引 int leftIndex = fatherIndex * 2 + 1; int rightIndex = fatherIndex * 2 + 2; // 該索引和左右子節(jié)點(diǎn)值 NSNumber *currentValue = [array objectAtIndex:fatherIndex]; NSNumber *leftValue = nil; NSNumber *rightValue = nil; if (leftIndex <= maxIndex) { leftValue = [array objectAtIndex:leftIndex]; } if (rightIndex <= maxIndex) { rightValue = [array objectAtIndex:rightIndex]; } if (rightValue != nil) { // 右子節(jié)點(diǎn)存在, 則左子節(jié)點(diǎn)必定存在, 判斷三者的值并把最大值換到父節(jié)點(diǎn)上 if (currentValue.doubleValue > leftValue.doubleValue && currentValue.doubleValue > rightValue.doubleValue) { return -1; } else { // 與父節(jié)點(diǎn)進(jìn)行交換的結(jié)點(diǎn)的索引 int index = (leftValue.doubleValue > rightValue.doubleValue ? leftIndex : rightIndex); [array exchangeObjectAtIndex:fatherIndex withObjectAtIndex: index]; // 移動(dòng)完畢之后同時(shí)還要進(jìn)行(被移動(dòng)到子節(jié)點(diǎn)的值)與(該被移動(dòng)節(jié)點(diǎn)的左右子節(jié)點(diǎn)值)進(jìn)行比較 -- 遞歸 return index; } } else if (leftValue != nil) {// 右結(jié)點(diǎn)不存在, 左結(jié)點(diǎn)存在, 判斷左結(jié)點(diǎn)是否大于父結(jié)點(diǎn)的值 if (currentValue.doubleValue < leftValue.doubleValue) { [array exchangeObjectAtIndex:fatherIndex withObjectAtIndex:leftIndex]; return leftIndex; } else { return -1; } } return -1; }
算法分析
堆排序的基本思想是：將待排序序列構(gòu)造成一個(gè)大頂堆，此時(shí)哮针，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)关面。將其與末尾元素進(jìn)行交換坦袍，此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆等太，這樣會(huì)得到n個(gè)元素的次小值捂齐。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了
堆排序是一種選擇排序缩抡，整體主要由構(gòu)建初始堆+交換堆頂元素和末尾元素并重建堆兩部分組成奠宜。其中構(gòu)建初始堆經(jīng)推導(dǎo)復(fù)雜度為O(n)，在交換并重建堆的過(guò)程中瞻想，需交換n-1次压真，而重建堆的過(guò)程中，根據(jù)完全二叉樹(shù)的性質(zhì)蘑险，[log2(n-1),log2(n-2)...1]逐步遞減滴肿，近似為nlogn。所以堆排序時(shí)間復(fù)雜度一般認(rèn)為就是O(nlogn)級(jí)佃迄。
七泼差、歸并排序（Merge Sort）
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用呵俏。將已有序的子序列合并堆缘，得到完全有序的序列；即先使每個(gè)子序列有序普碎，再使子序列段間有序套啤。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并随常。
算法描述
- 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列潜沦；
- 對(duì)這兩個(gè)子序列分別采用歸并排序；
- 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列绪氛。
算法演示
歸并排序
代碼實(shí)現(xiàn)
#import "ViewController.h" @interface ViewController () @end @implementation ViewController - (void)viewDidLoad { [super viewDidLoad]; NSMutableArray * array = [NSMutableArray arrayWithObjects:@5,@6,@2,@4,@3,@8,@7,@1, nil]; //調(diào)用排序 [self mergeSortArray:array]; NSLog(@"%@", array); // Do any additional setup after loading the view. } - (void)mergeSortArray:(NSMutableArray *)array { //創(chuàng)建一個(gè)副本數(shù)組 NSMutableArray * auxiliaryArray = [[NSMutableArray alloc]initWithCapacity:array.count]; //對(duì)數(shù)組進(jìn)行第一次二分唆鸡，初始范圍為0到array.count-1 [self mergeSort:array auxiliary:auxiliaryArray low:0 high:array.count-1]; } - (void)mergeSort:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low high:(int)high { //遞歸跳出判斷 if (low>=high) { return; } //對(duì)分組進(jìn)行二分 int middle = (high - low)/2 + low; //對(duì)左側(cè)的分組進(jìn)行遞歸二分 low為第一個(gè)元素索引，middle為最后一個(gè)元素索引 [self mergeSort:array auxiliary:auxiliaryArray low:low high:middle]; //對(duì)右側(cè)的分組進(jìn)行遞歸二分 middle+1為第一個(gè)元素的索引枣察，high為最后一個(gè)元素的索引 [self mergeSort:array auxiliary:auxiliaryArray low:middle + 1 high:high]; //對(duì)每個(gè)有序數(shù)組進(jìn)行回歸合并 [self merge:array auxiliary:auxiliaryArray low:low middel:middle high:high]; } - (void)merge:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low middel:(int)middle high:(int)high { //將數(shù)組元素復(fù)制到副本 for (int i=low; i<=high; i++) { auxiliaryArray[i] = array[I]; } //左側(cè)數(shù)組標(biāo)記 int leftIndex = low; //右側(cè)數(shù)組標(biāo)記 int rightIndex = middle + 1; //比較完成后比較小的元素要放的位置標(biāo)記 int currentIndex = low; while (leftIndex <= middle && rightIndex <= high) { //此處是使用NSNumber進(jìn)行的比較争占，你也可以轉(zhuǎn)成NSInteger再比較 if ([auxiliaryArray[leftIndex] compare:auxiliaryArray[rightIndex]]!=NSOrderedDescending) { //左側(cè)標(biāo)記的元素小于等于右側(cè)標(biāo)記的元素 array[currentIndex] = auxiliaryArray[leftIndex]; currentIndex++; leftIndex++; } else { //右側(cè)標(biāo)記的元素小于左側(cè)標(biāo)記的元素 array[currentIndex] = auxiliaryArray[rightIndex]; currentIndex++; rightIndex++; } } //如果完成后左側(cè)數(shù)組有剩余 if (leftIndex <= middle) { for (int i = 0; i<=middle - leftIndex; i++) { array[currentIndex +i] = auxiliaryArray[leftIndex +I ]; } } } @end
算法分析
歸并排序是一種穩(wěn)定的排序方法。和選擇排序一樣序目，歸并排序的性能不受輸入數(shù)據(jù)的影響臂痕，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是O(nlogn）的時(shí)間復(fù)雜度猿涨。代價(jià)是需要額外的內(nèi)存空間握童。
八、計(jì)數(shù)排序（Counting Sort）
計(jì)數(shù)排序 的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(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來(lái)將A中的元素排到正確的位置。它只能對(duì)整數(shù)進(jìn)行排序步鉴。
算法描述
1.找出待排序的數(shù)組中最大和最小的元素揪胃；
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)氛琢；
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始喊递，每一項(xiàng)和前一項(xiàng)相加）；
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)艺沼，每放一個(gè)元素就將C(i)減去1。
算法演示
計(jì)數(shù)排序
代碼實(shí)現(xiàn)
- (NSArray *)countSort:(NSArray *)arr { int maxValue = 0; for (NSNumber *num in arr) { if (num.intValue > maxValue) { maxValue = num.intValue; } } NSMutableArray *array = [NSMutableArray array]; int arrLen = (int)arr.count; NSMutableDictionary<NSString *,NSNumber *> *bucket = [NSMutableDictionary dictionary]; int sortedIndex = 0; int bucketLen = maxValue + 1; for (int i = 0; i < arrLen; i++) { NSString *key = [NSString stringWithFormat:@"%@", arr[I]]; if (!bucket[key]) { bucket[key] = @0; } NSNumber *num = bucket[key]; bucket[key] = @(num.intValue + 1); } for (int j = 0; j < bucketLen; j++) { NSString *key = [NSString stringWithFormat:@"%d", j]; while(bucket[key].intValue > 0) { array[sortedIndex ++] = @(j); bucket[key] = @(bucket[key].intValue - 1); } } return array; }
算法分析
計(jì)數(shù)排序是一個(gè)穩(wěn)定的排序算法蕴掏。當(dāng)輸入的元素是 n 個(gè) 0到 k 之間的整數(shù)時(shí)障般，時(shí)間復(fù)雜度是O(n+k)，空間復(fù)雜度也是O(n+k)盛杰，其排序速度快于任何比較排序算法挽荡。當(dāng)k不是很大并且序列比較集中時(shí)，計(jì)數(shù)排序是一個(gè)很有效的排序算法即供。
九定拟、桶排序（Bucket Sort）
桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系逗嫡，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定青自。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里驱证，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排）延窜。
算法描述
- 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
- 遍歷輸入數(shù)據(jù)抹锄，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去逆瑞；
- 對(duì)每個(gè)不是空的桶進(jìn)行排序；
- 從不是空的桶里把排好序的數(shù)據(jù)拼接起來(lái)伙单。
算法演示
桶排序
代碼實(shí)現(xiàn)
- (NSArray *)bucketSort:(NSArray *)arr{ NSMutableArray *array = [NSMutableArray arrayWithArray:arr]; //預(yù)計(jì)每個(gè)桶內(nèi)能裝3個(gè) NSInteger size = 3; //桶的數(shù)量 NSInteger bucketsCount = array.count / size; if ((array.count % size) > 0) { bucketsCount ++; } //找出最小值和最大值 NSInteger min = [array[0] integerValue]; NSInteger max = [array[0] integerValue]; for (NSNumber *number in array) { if (number.integerValue < min) { min = number.integerValue; } if (number.integerValue > max) { max = number.integerValue; } } //平均值 NSInteger average = ceil((double)(max - min)/(double)bucketsCount); NSMutableDictionary *dictionary = [NSMutableDictionary dictionary]; for (NSInteger i = 0; i < bucketsCount; i++) { NSMutableArray *bucketArray = [NSMutableArray array]; NSString *key = [NSString stringWithFormat:@"%@-%@",@(min + i * average),@(min + (i + 1) * average)]; [dictionary setValue:bucketArray forKey:key]; } for (NSNumber *number in array) { NSInteger i = floor((double)(number.integerValue - min) / >(double)average); NSString *key = [NSString stringWithFormat:@"%@-%@",@(min + i * average),@(min + (i + 1) * average)]; NSMutableArray *bucketArray = [dictionary valueForKey:key]; [bucketArray addObject:number]; } NSInteger length = 0; for (NSInteger i = 0; i < dictionary.allKeys.count; i++) { NSString *key = [NSString stringWithFormat:@"%@-%@",@(min + i * average),@(min + (i + 1) * average)]; NSMutableArray *bucketArray = [dictionary objectForKey:key]; [self mergeSortArray:bucketArray]; [array replaceObjectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(length, bucketArray.count)] withObjects:bucketArray]; length += bucketArray.count; } return array; }
算法分析
桶排序最好情況下使用線性時(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ù)排序（Radix Sort）
基數(shù)排序是按照低位先排序总寻，然后收集；再按照高位排序梢为，然后再收集渐行；依次類推，直到最高位铸董。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的祟印，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序粟害。最后的次序就是高優(yōu)先級(jí)高的在前蕴忆，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。
算法描述
- 取得數(shù)組中的最大數(shù)悲幅，并取得位數(shù)套鹅；
- arr為原始數(shù)組，從最低位開(kāi)始取每個(gè)位組成radix數(shù)組汰具；
- 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）卓鹿；
算法演示
基數(shù)排序
代碼實(shí)現(xiàn)
- (NSArray *)radixSort:(NSMutableArray *)arr { NSMutableArray *array = [NSMutableArray arrayWithArray:arr]; int len = (int)array.count; NSMutableArray *radixArrays = [NSMutableArray array]; for (int i=0; i<10; i++) { NSMutableArray *arr = [NSMutableArray array]; for (int i=0; i<len; i++) { [arr addObject:@0]; } [radixArrays addObject:arr]; } int KEYNUM_31 = 10; //關(guān)鍵字個(gè)數(shù)，這里為32位整形位數(shù) for (int pos = 1; pos <= KEYNUM_31; pos++) { for (int i = 0; i < len; i++) { int num = [self GetNumInPos:[array[i] intValue] pos:pos]; int num2 = [radixArrays[num][0] intValue]+1; radixArrays[num][0] = @(num2); radixArrays[num][num2] = array[I]; } for (int i = 0,j = 0; i < 10; i++) { for (int k = 1; k <= [radixArrays[i][0] intValue]; k++) { array[j] = radixArrays[i][k]; j=j+1; } radixArrays[i][0] = @0; //復(fù)位 } } return array; } - (int)GetNumInPos:(int)num pos:(int)pos{ int temp = 1; for (int i=0; i<pos-1; i++) { temp *= 10; } return (num/temp)%10; }
算法分析
基數(shù)排序基于分別排序留荔，分別收集吟孙，所以是穩(wěn)定的。但基數(shù)排序的性能比桶排序要略差聚蝶，每一次關(guān)鍵字的桶分配都需要O(n)的時(shí)間復(fù)雜度杰妓，而且分配之后得到新的關(guān)鍵字序列又需要O(n)的時(shí)間復(fù)雜度。假如待排數(shù)據(jù)可以分為d個(gè)關(guān)鍵字碘勉，則基數(shù)排序的時(shí)間復(fù)雜度將是O(d*2n) 稚失，當(dāng)然d要遠(yuǎn)遠(yuǎn)小于n，因此基本上還是線性級(jí)別的恰聘。
基數(shù)排序的空間復(fù)雜度為O(n+k)句各，其中k為桶的數(shù)量。一般來(lái)說(shuō)n>>k晴叨，因此額外空間需要大概n個(gè)左右凿宾。
