作者：Fly晴天里Fly
Objective-C排序算法
根據(jù)將排序記錄是否全部放置在內(nèi)存中尊沸，將排序分為內(nèi)排序和外排序谤祖，之前講的都是內(nèi)排序兄世，這里總結(jié)一下敬拓，內(nèi)排序分為四類：插入排序邻薯、交換排序、選擇排序和歸并排序乘凸。
快排
快速排序是面試中經(jīng)常會被問的一個排序算法厕诡。一般要求手寫。
快排是對冒泡排序的一種改進营勤。
平均時間復(fù)雜度O（nlogn）灵嫌，最壞時間復(fù)雜度O（n*n）
因為二分查找的時間復(fù)雜度是o(logn), 每次分成兩段壹罚，那么分的次數(shù)就是logn了，每一次處理需要n次計算寿羞，那么時間復(fù)雜度就是nlogn了猖凛！
最壞是O(n^2). 這種情況就是數(shù)組剛好的倒序，然后每次去中間元的時候都是取最大或者最小绪穆。
穩(wěn)定性：不穩(wěn)定辨泳。
+ (void)quickSort:(NSMutableArray *)arr low:(NSInteger)low high:(NSInteger)high {
if (arr.count == 0 || low >= high) {
return;
}
NSInteger i = low, j = high;
NSInteger key = [arr[low] integerValue];
while (i < j && [arr[j] integerValue] >= key) {
j--;
}
arr[i] = arr[j];
while (i < j && [arr[i] integerValue] <= key) {
i++;
}
arr[j] = arr[i];
NSLog(@"一次排序結(jié)果：%@", arr);
arr[i] = @(key);
[[self class] quickSort:arr low:low high:i-1];
[[self class] quickSort:arr low:i+1 high:high];
}
堆排序
堆排序是一種選擇排序，其時間復(fù)雜度為O(nlogn)玖院。
定義：
堆的存儲
其基本思想為(大頂堆)：
- 將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆漠吻，此堆為初始的無序區(qū)；
- 將堆頂元素R[1]與最后一個元素R[n]交換司恳，此時得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n];
- 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)途乃，因此需要對當(dāng)前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換扔傅，得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)耍共。不斷重復(fù)此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成猎塞。
因此對于堆排序试读，最重要的兩個操作就是構(gòu)造初始堆和調(diào)整堆，其實構(gòu)造初始堆事實上也是調(diào)整堆的過程荠耽，只不過構(gòu)造初始堆是對所有的非葉節(jié)點都進行調(diào)整钩骇。
由于堆也是用數(shù)組模擬的，故堆化數(shù)組后铝量，第一次將A[0]與A[n - 1]交換倘屹，再對A[0…n-2]重新恢復(fù)堆。第二次將A[0]與A[n – 2]交換慢叨，再對A[0…n - 3]重新恢復(fù)堆纽匙，重復(fù)這樣的操作直到A[0]與A[1]交換。由于每次都是將最大的數(shù)據(jù)并入到后面的有序區(qū)間拍谐，故操作完成后整個數(shù)組就有序了烛缔。
作為一個開發(fā)者，有一個學(xué)習(xí)的氛圍跟一個交流圈子特別重要轩拨，這是一個我的iOS交流群：761407670 進群密碼123践瓷，不管你是小白還是大牛歡迎入駐 ，分享BAT,阿里面試題亡蓉、面試經(jīng)驗晕翠，討論技術(shù)， 大家一起交流學(xué)習(xí)成長寸宵！
另附上一份各好友收集的大廠面試題崖面，進群可自行下載！
已知一棵完全二叉樹各節(jié)點的編號為0到n梯影，如何得出其第一個非葉子節(jié)點的編號
最后一個葉子節(jié)點的索引值是n-1巫员，它的父節(jié)點索引值是[(n-1)-1]/2 = n/2 -1
/* (最大)堆的向下調(diào)整算法
*
* 注：數(shù)組實現(xiàn)的堆中，第N個節(jié)點的左孩子的索引值是(2N+1)甲棍，右孩子的索引是(2N+2)简识。
* 其中，N為數(shù)組下標(biāo)索引值感猛，如數(shù)組中第1個數(shù)對應(yīng)的N為0七扰。
*
* 參數(shù)說明：
* a -- 待排序的數(shù)組
* start -- 被下調(diào)節(jié)點的起始位置(一般為0，表示從第1個開始)
* end -- 截至范圍(一般為數(shù)組中最后一個元素的索引)
*/
- (void)heapAdjust:(NSMutableArray *)marr start:(int)start end:(int)end {
int lchild = 2*start; //i的左孩子節(jié)點序號
int rchild = 2*start+1; //i的右孩子節(jié)點序號
int max = start; //臨時變量
if (start <= end/2) { //如果i是葉節(jié)點就不用進行調(diào)整
if (lchild <= end && [marr[lchild] integerValue] > [marr[max] integerValue]) {
max = lchild;
}
if (rchild <= end && [marr[rchild] integerValue] > [marr[max] integerValue] ) {
max = rchild;
}
if (max != start) {
[marr exchangeObjectAtIndex:start withObjectAtIndex:max];
// 避免調(diào)整之后以max為父節(jié)點的子樹不是堆
[self heapAdjust:marr start:max end:end];
}
}
}
// 建大根堆
- (void)buildHeap:(NSMutableArray *)marr {
int size = (int)marr.count;
// 最后一個葉子節(jié)點的索引值是n-1陪白，它的父節(jié)點索引值是[(n-1)-1]/2 = n/2 -1
for (int i = size/2-1; i >= 0; --i) {
[self heapAdjust:marr start:i end:size-1];
}
}
- (void)heapSort:(NSMutableArray *)marr {
[self buildHeap:marr];
NSLog(@"build after: %@", marr);
int len = (int)marr.count-1;
for (int i = len; i >= 0; i--) {
// 交換堆頂和最后一個元素颈走，即每次將剩余元素中的最大者放到最后面
[marr exchangeObjectAtIndex:0 withObjectAtIndex:i];
// 重新調(diào)整堆頂節(jié)點成為大頂堆
[self heapAdjust:marr start:0 end:i-1];
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *arr = @[@(12), @(14), @(100), @(29), @(8), @(21), @(15), @(59), @(50), @(99)];
NSMutableArray *marr = [NSMutableArray arrayWithArray:arr];
SGSort *sort = [[SGSort alloc] init];
[sort heapSort:marr];
NSLog(@"heapsort result =%@", marr);
}
return 0;
}
// 輸出結(jié)果
2017-08-27 19:55:04.657 SuanFaXueXi[3487:106882] build after: (
100,
99,
50,
59,
14,
21,
15,
29,
12,
8
)
2017-08-27 19:55:07.151 SuanFaXueXi[3487:106882] heapsort result =(
8,
12,
14,
15,
21,
29,
50,
59,
99,
100
)
由于每次重新恢復(fù)堆的時間復(fù)雜度為O(logN)，共N - 1次重新恢復(fù)堆操作咱士，再加上前面建立堆時N / 2次向下調(diào)整立由，每次調(diào)整時間復(fù)雜度也為O(logN)。二次操作時間相加還是O(N * logN)序厉。故堆排序的時間復(fù)雜度為O(N * logN)
堆排序適合于數(shù)據(jù)量非常大的場合（百萬數(shù)據(jù)）锐膜。
堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對于數(shù)據(jù)量非常巨大的序列是合適的弛房。比如超過數(shù)百萬條記錄道盏，因為快速排序，歸并排序都使用遞歸來設(shè)計算法文捶，在數(shù)據(jù)量非常大的時候荷逞，可能會發(fā)生堆棧溢出錯誤。
歸并排序
希爾排序
基本思想是：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序粹排，待整個序列中的記錄基本有序時再對全體記錄進行一次直接插入排序颅围。
計數(shù)排序
如果在面試中有面試官要求你寫一個O(n)時間復(fù)雜度的排序算法，你千萬不要立刻說：這不可能恨搓！雖然前面基于比較的排序的下限是O(nlogn)院促。但是確實也有線性時間復(fù)雜度的排序，只不過有前提條件斧抱，就是待排序的數(shù)要滿足一定的范圍的整數(shù)常拓，而且計數(shù)排序需要比較多的輔助空間。其基本思想是辉浦，用待排序的數(shù)作為計數(shù)數(shù)組的下標(biāo)弄抬，統(tǒng)計每個數(shù)字的個數(shù)咧欣。然后依次輸出即可得到有序序列娶桦。
今天學(xué)習(xí)了計數(shù)排序昼激，貌似計數(shù)排序的復(fù)雜度為o(n)障本。很強大。他的基本思路為：
我們希望能線性的時間復(fù)雜度排序懊亡，如果一個一個比較依啰，顯然是不實際的，書上也在決策樹模型中論證了店枣，比較排序的情況為nlogn的復(fù)雜度速警。
既然不能一個一個比較，我們想到一個辦法鸯两，就是如果我在排序的時候就知道他的位置闷旧，那不就是掃描一遍，把他放入他應(yīng)該的位置不就可以了嘛钧唐。
3.要知道他的位置忙灼，我們只需要知道有多少不大于他不就可以了嗎？
以此為出發(fā)點钝侠，我們怎么確定不大于他的個數(shù)呢缀棍？我們先來個約定，如果數(shù)組中的元素都比較集中机错，都在[0, max]范圍內(nèi)爬范。我們開一個max的空間b數(shù)組，把b數(shù)組下標(biāo)對應(yīng)的元素和要排序的A數(shù)組下標(biāo)對應(yīng)起來弱匪。這樣不就可以知道不比他大的有多少個了嗎青瀑？我們只要把比他小的位置元素個數(shù)求和，就是不比他大的萧诫。例如：A={3,5,7};我們開一個大小為8的數(shù)組b斥难，把a[0] = 3 放入b[3]中，使b[3] = 0; 同理 b[5] = 1; b[7] = 2;其他我們都設(shè)置為-1帘饶，哈哈我們只需要遍歷一下b數(shù)組哑诊，如果他有數(shù)據(jù)，就來出來及刻，鐵定是當(dāng)前最小的镀裤。如果要知道比a[2]小的數(shù)字有多少個，值只需要求出b[0] – b[6]的有數(shù)據(jù)的和就可以了缴饭。這個0(n)的速度不是蓋得暑劝。
思路就是這樣咯。但是要注意兩個數(shù)相同的情況A = {1,2,3,3,4}颗搂，這種情況就不可以咯担猛，所以還是有點小技巧的。
6.處理小技巧：我們不把A的元素大小與B的下標(biāo)一一對應(yīng)，而是在B數(shù)組對應(yīng)處記錄該元素大小的個數(shù)傅联。這不久解決了嗎先改。哈哈。例如A = {1,2,3,3,4}我們開大小為5的數(shù)組b;記錄數(shù)組A中元素值為0的個數(shù)為b[0] = 0, 記錄數(shù)組A中元素個數(shù)為1的b[1] = 1,同理b[2] = 1, b[3] = 2, b[4] = 1;好了蒸走，這樣我們就知道比A4小的元素個數(shù)是多少了：count = b[0] + b[1] + b[2] + b[3] = 4;他就把A[4]的元素放在第4個位置仇奶。
桶排序
基數(shù)排序
總結(jié)
在前面的介紹和分析中我們提到了冒泡排序、選擇排序载碌、插入排序三種簡單的排序及其變種快速排序猜嘱、堆排序衅枫、希爾排序三種比較高效的排序嫁艇。后面我們又分析了基于分治遞歸思想的歸并排序還有計數(shù)排序、桶排序弦撩、基數(shù)排序三種線性排序步咪。我們可以知道排序算法要么簡單有效，要么是利用簡單排序的特點加以改進益楼，要么是以空間換取時間在特定情況下的高效排序猾漫。
1. 從平均時間來看，快速排序是效率最高的感凤，但快速排序在最壞情況下的時間性能不如堆排序和歸并排序悯周。而后者相比較的結(jié)果是，在n較大時歸并排序使用時間較少陪竿，但使用輔助空間較多禽翼。
2. 上面說的簡單排序包括除希爾排序之外的所有冒泡排序、插入排序族跛、簡單選擇排序闰挡。其中直接插入排序最簡單，但序列基本有序或者n較小時礁哄，直接插入排序是好的方法长酗，因此常將它和其他的排序方法，如快速排序桐绒、歸并排序等結(jié)合在一起使用夺脾。
3. 基數(shù)排序的時間復(fù)雜度也可以寫成O(d*n)。因此它最使用于n值很大而關(guān)鍵字較小的的序列茉继。若關(guān)鍵字也很大劳翰，而序列中大多數(shù)記錄的最高關(guān)鍵字均不同，則亦可先按最高關(guān)鍵字不同馒疹，將序列分成若干小的子序列佳簸，而后進行直接插入排序。
4. 從方法的穩(wěn)定性來比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法生均，所有時間復(fù)雜度為O(n^2)的簡單排序也是穩(wěn)定的听想。但是快速排序、堆排序马胧、希爾排序等時間性能較好的排序方法都是不穩(wěn)定的汉买。穩(wěn)定性需要根據(jù)具體需求選擇。
5. 上面的算法實現(xiàn)大多數(shù)是使用線性存儲結(jié)構(gòu)佩脊，像插入排序這種算法用鏈表實現(xiàn)更好蛙粘，省去了移動元素的時間。具體的存儲結(jié)構(gòu)在具體的實現(xiàn)版本中也是不同的威彰。
參考
排序 Heap Sort
堆排序算法解析
堆排序
面試中的排序算法總結(jié)
計數(shù)排序出牧，傳說時間復(fù)雜度為0(n)的排序
