前言
排序算法也算是老生常談了，如果你大學專業(yè)是計算機或軟件，甚至你參加過國二國三都會學到排序算法，如果我沒猜錯的話你接觸的第一個算法是冒泡。
排序算法老生常談，但確實多少大廠面試題中的必考題。
廢話不多說，開始正題
常見的八種排序算法他們的關系如下：
排序一：冒泡排序
冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
算法步驟：
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
- 針對所有的元素重復以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
上代碼：
/**
冒泡排序
@param array 目標數(shù)組
@return 排序后數(shù)組
*/
+ (NSArray *)bubblingSorting:(NSMutableArray *)array {
int count = 0;
int forcount = 0;
for (int i = 0; i < array.count; i++) {
forcount++;
for (int j = (int)array.count-2; j >= i; j--) {
count++;
if ([array[j] doubleValue] > [array[j+1] doubleValue]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
return array;
}
排序二-選擇排序
選擇排序（Selection Sort）也是一種簡單直觀的排序算法。
算法步驟：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
- 重復第二步，直到所有元素均排序完畢。
上代碼：
/**
選擇排序
@param array 目標數(shù)組
@return 排序后數(shù)組
*/
+ (NSArray *)chooseSort:(NSMutableArray *)array {
for (int i=0; i<array.count; i++) {
for (int j=i+1; j<array.count; j++) {
if ([array[i] doubleValue] > [array[j] doubleValue]) {
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
return array;
}
排序三-歸并排序
歸并排序（Merge Sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
算法步驟：
- 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
- 重復步驟3直到某一指針達到序列尾
- 將另一序列剩下的所有元素直接復制到合并序列尾
上代碼：
/**
歸并排序
@param array 目標數(shù)組
@return 排序后數(shù)組
*/
+ (NSArray *)megerSort:(NSMutableArray *)array {
/**
歸并排序其實要做兩件事：
（1）“分解”——將序列每次折半劃分。
（2）“合并”——將劃分后的序列段兩兩合并后排序。
*/
//排序數(shù)組
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
//第一趟排序是的子數(shù)組個數(shù)為ascendingArr.count
for (NSNumber *num in array) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
/**
分解操作 每一次歸并操作 tempArray的個數(shù)為
（當數(shù)組個數(shù)為偶數(shù)時tempArray.count/2;當數(shù)組個數(shù)為奇數(shù)時tempArray.count/2+1）
當tempArray.count == 1時，歸并排序完成
*/
while (tempArray.count != 1) {
NSInteger i = 0;
//當數(shù)組個數(shù)為偶數(shù)時 進行合并操作， 當數(shù)組個數(shù)為奇數(shù)時，最后一位輪空
while (i < tempArray.count - 1) {
//將i 與i+1 進行合并操作 將合并結果放入i位置上 將i+1位置上的元素刪除
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
//i++ 繼續(xù)下一循環(huán)的合并操作
i++;
}
}
NSLog(@"歸并排序結果：%@", tempArray);
return (NSArray *)tempArray[0];
}
//合并
+ (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
// 合并序列數(shù)組
NSMutableArray *resultArray = [NSMutableArray array];
// firstIndex是第一段序列的下標 secondIndex是第二段序列的下標
NSInteger firstIndex = 0, secondIndex = 0;
// 掃描第一段和第二段序列，直到有一個掃描結束
while (firstIndex < array1.count && secondIndex < array2.count) {
// 判斷第一段和第二段取出的數(shù)哪個更小，將其存入合并序列，并繼續(xù)向下掃描
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
// 若第一段序列還沒掃描完，將其全部復制到合并序列
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
// 若第二段序列還沒掃描完，將其全部復制到合并序列
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
// 返回合并序列數(shù)組
return resultArray.copy;
}
排序四：快速排序
快速排序（Quick Sort）是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
算法步驟：
- 從數(shù)列中挑出一個元素，稱為 “基準”（pivot），
- 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
- 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
上代碼：
/**
快速排序
@param array 目標數(shù)組
@param left 左標記
@param right 右標記
@return 排序后數(shù)組
*/
+ (NSArray *)quickSortArray:(NSMutableArray *)array
leftIndex:(NSInteger)left
rightIndex:(NSInteger)right {
if (left > right) {
return @[];
}
NSInteger i = left;
NSInteger j = right;
//記錄基準數(shù) pivoty
id key = array[i];
while (i < j) {
//首先從右邊j開始查找(從最右邊往左找)比基準數(shù)(key)小的值<---
while (i < j && [key doubleValue] <= [array[j] doubleValue]) {
j--;
}
//如果從右邊j開始查找的值[array[j] integerValue]比基準數(shù)小，則將查找的小值調換到i的位置
if (i < j) {
array[i] = array[j];
}
//從i的右邊往右查找到一個比基準數(shù)小的值時，就從i開始往后找比基準數(shù)大的值 --->
while (i < j && [array[i] doubleValue] <= [key doubleValue]) {
i++;
}
//如果從i的右邊往右查找的值[array[i] integerValue]比基準數(shù)大，則將查找的大值調換到j的位置
if (i < j) {
array[j] = array[i];
}
}
//將基準數(shù)放到正確的位置，----改變的是基準值的位置(數(shù)組下標)---
array[i] = key;
//遞歸排序
//將i左邊的數(shù)重新排序
[self quickSortArray:array leftIndex:left rightIndex:i - 1];
//將i右邊的數(shù)重新排序
[self quickSortArray:array leftIndex:i + 1 rightIndex:right];
return array;
}
排序五：插入排序
插入排序（Insertion Sort）是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。
算法步驟：
- 將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
- 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）
上代碼：
/**
插入排序
@param array 目標數(shù)組
@return 排序后數(shù)組
*/
+ (NSArray *)inserSort:(NSMutableArray *)array {
//插入排序的原理：始終定義第一個元素為有序的，將元素逐個插入到有序排列之中，其特點是要不斷的
//移動數(shù)據(jù)，空出一個適當?shù)奈恢茫汛迦氲脑胤诺嚼锩嫒ァ? for (int i = 0; i < array.count; i++) {
id temp = array[i];
//temp 為待排元素 i為其位置 j為已排元素最后一個元素的位置（即取下一個元素，在已經(jīng)排好序的元素序列中從后向前掃描）
int j = i-1;
//當j < 0 時， i 為第一個元素 該元素認為已經(jīng)是排好序的 所以不進入while循環(huán)
// [array[j] compare:temp] == NSOrderedDescending與[array[j] intValue] > [temp intValue] 作用相同
while (j >= 0 && [array[j] doubleValue] > [temp doubleValue]) {
//如果已經(jīng)排好序的序列中元素大于新元素，則將該元素往右移動一個位置
[array replaceObjectAtIndex:j+1 withObject:array[j]];
j--;
}
//跳出while循環(huán)時，j的元素小于或等于i的元素(待排元素)。插入新元素 i= j+1
[array replaceObjectAtIndex:j+1 withObject:temp];
NSLog(@"插入排序排序中:%@",array);
}
return array;
}
排序六：希爾排序
希爾排序（Shell Sort）也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時， 效率高， 即可以達到線性排序的效率
但插入排序一般來說是低效的， 因為插入排序每次只能將數(shù)據(jù)移動一位
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
算法步驟：
- 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列個數(shù)k，對序列進行k 趟排序；
- 每趟排序，根據(jù)對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
上代碼：
/**
希爾排序
@param array 目標數(shù)組
@return 排序后數(shù)組
*/
+ (NSArray *)shellSort:(NSMutableArray *)array {
int gap = (int)array.count / 2;
while (gap >= 1) {
for(int i = gap ; i < [array count]; i++) {
id temp = array[i];
int j = i;
while (j >= gap && [temp doubleValue] < [[array objectAtIndex:(j - gap)] doubleValue]) {
[array replaceObjectAtIndex:j withObject:[array objectAtIndex:j-gap]];
j -= gap;
}
[array replaceObjectAtIndex:j withObject:temp];
}
gap = gap / 2;
}
return array;
}
排序七-堆排序
堆排序（Heap Sort）是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點。
堆排序的平均時間復雜度為Ο(nlogn) 。
算法步驟：
- 創(chuàng)建一個堆H[0..n-1]
- 把堆首（最大值）和堆尾互換
- 把堆的尺寸縮小1，并調用shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調整到相應位置
- 重復步驟2，直到堆的尺寸為1
上代碼：
/**
堆排序
@param array 目標數(shù)組
@return 排序后數(shù)組
*/
+ (NSArray *)heapSort:(NSMutableArray *)array {
NSInteger i ,size;
size = array.count;
//找出最大的元素放到堆頂
for (i= array.count/2-1; i>=0; i--) {
[self createBiggesHeap:array withSize:size beIndex:i];
}
while(size > 0){
[array exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //將根(最大) 與數(shù)組最末交換
size -- ;//樹大小減小
[self createBiggesHeap:array withSize:size beIndex:0];
}
NSLog(@"%@",array);
return array;
}
+ (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger)size beIndex:(NSInteger)element {
NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子樹
while (rchild < size) { //子樹均在范圍內
if ([list[element] doubleValue] >= [list[lchild] doubleValue] && [list[element] doubleValue] >= [list[rchild] doubleValue]) return; //如果比左右子樹都大，完成整理
if ([list[lchild] doubleValue] > [list[rchild] doubleValue]) { //如果左邊最大
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循環(huán)時整理子樹
}else{//否則右面最大
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新計算子樹位置
}
//只有左子樹且子樹大于自己
if (lchild < size && [list[lchild] integerValue] > [list[element] integerValue]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
排序八-基數(shù)排序
基數(shù)排序（Radix Sort）是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
說基數(shù)排序之前，我們簡單介紹桶排序：
算法思想：是將陣列分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使 用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
簡單來說，就是把數(shù)據(jù)分組，放在一個個的桶中，然后對每個桶里面的在進行排序。
例如要對大小為[1..1000]范圍內的n個整數(shù)A[1..n]排序
首先，可以把桶設為大小為10的范圍，具體而言，設集合B[1]存儲[1..10]的整數(shù)，集合B[2]存儲 (10..20]的整數(shù)，……集合B[i]存儲( (i-1)10, i10]的整數(shù)，i = 1,2,..100。總共有 100個桶。
然后，對A[1..n]從頭到尾掃描一遍，把每個A[i]放入對應的桶B[j]中。 再對這100個桶中每個桶里的數(shù)字排序，這時可用冒泡，選擇，乃至快排，一般來說任 何排序法都可以。
最后，依次輸出每個桶里面的數(shù)字，且每個桶中的數(shù)字從小到大輸出，這 樣就得到所有數(shù)字排好序的一個序列了。
假設有n個數(shù)字，有m個桶，如果數(shù)字是平均分布的，則每個桶里面平均有n/m個數(shù)字。如果
對每個桶中的數(shù)字采用快速排序，那么整個算法的復雜度是
O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)
從上式看出，當m接近n的時候，桶排序復雜度接近O(n)
當然，以上復雜度的計算是基于輸入的n個數(shù)字是平均分布這個假設的。這個假設是很強的 ，實際應用中效果并沒有這么好。如果所有的數(shù)字都落在同一個桶中，那就退化成一般的排序了。
前面說的幾大排序算法 ，大部分時間復雜度都是O（n2），也有部分排序算法時間復雜度是O(nlogn)。而桶式排序卻能實現(xiàn)O（n）的時間復雜度。但桶排序的缺點是：
- 首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數(shù)組的空間開銷，一個存放待排序數(shù)組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數(shù)組就要至少m個空間。
- 其次待排序的元素都要在一定的范圍內等等。
上代碼：
/**
基數(shù)排序
@param array 目標數(shù)組
@return 排序后的array
*/
+ (NSArray *)radixSort:(NSMutableArray *)array {
NSMutableArray *bucket = [self createBucket];
double maxNumber = [self listMaxItem:array];
NSInteger maxLength = [self numberLength:maxNumber];
for (NSInteger digit = 1; digit <= maxLength; digit++) {
//入桶
for (NSNumber *number in array) {
NSInteger baseNumber = [self fetchBaseNumber:number.doubleValue digit:digit];
NSMutableArray *subArray = bucket[baseNumber];
[subArray addObject:number];
}
//出桶
NSInteger index = 0;
for (NSInteger i = 0; i < bucket.count; i++) {
NSMutableArray *subArray = bucket[i];
while (subArray.count > 0) {
NSNumber *item = subArray[0];
[array replaceObjectAtIndex:index withObject:item];
[subArray removeObjectAtIndex:0];
index++;
}
}
}
return array;
}
//創(chuàng)建10個空桶
+ (NSMutableArray *)createBucket {
NSMutableArray *bucketArray = [NSMutableArray array];
for (NSInteger i = 0; i < 10; i++) {
[bucketArray addObject:[NSMutableArray array]];
}
return bucketArray;
}
//計算無序序列中最大的數(shù)值
+ (double)listMaxItem:(NSArray *)array {
double maxNumber = [array[0] doubleValue];
for (NSNumber *number in array) {
if (maxNumber < number.doubleValue) {
maxNumber = number.doubleValue;
}
}
return maxNumber;
}
//獲取數(shù)字的長度
+ (NSInteger)numberLength:(double)number {
NSString *numberStr = [NSString stringWithFormat:@"%f",number];
return numberStr.length;
}
//獲取數(shù)值中特定位數(shù)的值
+ (NSInteger)fetchBaseNumber:(double)number digit:(NSInteger)digit {
if (digit > 0 && digit <= [self numberLength:number]) {
NSMutableArray *numbersArray = [NSMutableArray array];
NSString *numberStr = [NSString stringWithFormat:@"%f",number];
for (NSInteger i = 0; i < numberStr.length; i++) {
NSString *subStr = [numberStr substringWithRange:NSMakeRange(i, 1)];
[numbersArray addObject:[NSNumber numberWithInteger:subStr.doubleValue]];
}
return [numbersArray[numbersArray.count - digit] integerValue];
}
return 0;
}
總結
各種排序的穩(wěn)定性，時間復雜度、空間復雜度、穩(wěn)定性總結如下圖：
關于時間復雜度：
平方階(O(n2))排序：
各類簡單排序:直接插入、直接選擇和冒泡排序；線性對數(shù)階(O(nlog2n))排序：
快速排序、堆排序和歸并排序O(n1+§))排序,§是介于0和1之間的常數(shù)：
希爾排序線性階(O(n))排序：
基數(shù)排序，此外還有桶、箱排序。
關于時間復雜度：
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序
