排序算法可以分為內(nèi)部排序和外部排序愉老，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序舌稀，而外部排序是因排序的數(shù)據(jù)很大啊犬，一次不能容納全部的排序記錄，在排序過程中需要訪問外存扩借。
常見的內(nèi)部排序算法有：冒泡排序椒惨、快速排序、插入排序潮罪、希爾排序康谆、選擇排序、堆排序嫉到、歸并排序沃暗、基數(shù)排序等。
算法一：冒泡排序
冒泡排序.gif
算法步驟：
1.比較相鄰的元素何恶。如果第一個比第二個大孽锥，就交換他們兩個
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對细层。這步做完后惜辑，最后的元素會是最大的數(shù)
3.針對所有的元素重復以上的步驟，除了最后一個
4.持續(xù)每次對越來越少的元素重復上面的步驟疫赎，直到?jīng)]有任何一對數(shù)字需要比較
//冒泡排序
-(void)bubbleSort:(NSMutableArray *)mtArr
{
if (mtArr.count == 0 || mtArr == nil) {
return;
}
for (int i = 0; i < mtArr.count; i ++) {
for (int j = 0; j < mtArr.count; j ++) {
if ([mtArr[i] compare:mtArr[j]] == NSOrderedAscending )
{
[mtArr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
算法二：快速排序
快速排序.gif
算法步驟：
1.從數(shù)列中挑出一個元素盛撑，稱為 “基準”（pivot）。
2.重新排序數(shù)列捧搞，所有元素比基準值小的擺放在基準前面抵卫，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后胎撇，該基準就處于數(shù)列的中間位置介粘。這個稱為分區(qū)（partition）操作。
3.遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序晚树。
4.遞歸的最底部情形姻采，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了爵憎。雖然一直遞歸下去慨亲，但是這個算法總會退出，因為在每次的迭代（iteration）中纲堵，它至少會把一個元素擺到它最后的位置去巡雨。
//快速排序
-(void)quickSort:(NSMutableArray *)mtArr withLeftIndex:(int)leftIndex andRightIndex:(int)rightIndex
{
if (leftIndex >= rightIndex ) {
return;
}
int i = leftIndex;
int j = rightIndex;
int number = [mtArr[i] intValue];
while (i < j) {
while (i < j && ([mtArr[j] intValue] >= number)){
j --;
}
[mtArr replaceObjectAtIndex:i withObject:mtArr[j]];
while (i < j && ([mtArr[i] intValue] <= number)) {
i ++;
}
[mtArr replaceObjectAtIndex:j withObject:mtArr[i]];
}
mtArr[i] = @(number);
[self quickSort:mtArr withLeftIndex:leftIndex andRightIndex:i -1];
[self quickSort:mtArr withLeftIndex:i + 1 andRightIndex:rightIndex];
}
詳細介紹：
算法三：插入排序
插入排序.gif
算法步驟：
1.將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列
2.從頭到尾依次掃描未排序序列席函，將掃描到的每個元素插入有序序列的適當位置（如果待插入的元素與有序序列中的某個元素相等铐望，則將待插入元素插入到相等元素的后面）
//插入排序
-(void)insertSort:(NSMutableArray *)mtArr
{
if (mtArr == nil || mtArr.count == 0) {
return;
}
for (int i = 0; i < mtArr.count; i ++) {
NSNumber * number = mtArr[i];
int j = i -1;
while (j >= 0 && [mtArr[j] compare:number] == NSOrderedDescending) {
[mtArr replaceObjectAtIndex:j + 1 withObject:mtArr[j]];
j --;
}
[mtArr replaceObjectAtIndex:j + 1 withObject:number];
}
}
算法四：希爾排序
希爾排序.gif
算法步驟：
1.選擇一個增量序列t1，t2茂附，…正蛙，tk，其中ti>tj营曼，tk=1
2.按增量序列個數(shù)k乒验，對序列進行k 趟排序
3.每趟排序，根據(jù)對應的增量ti蒂阱，將待排序列分割成若干長度為m 的子序列锻全，分別對各子表進行直接插入排序狂塘。僅增量因子為1 時，整個序列作為一個表來處理鳄厌，表長度即為整個序列的長度
//希爾排序
-(void)shellSort:(NSMutableArray *)mtArr
{
NSInteger bs = mtArr.count/2 ;
while (bs > 0) {
for (NSInteger i = bs; i < mtArr.count; i ++) {
NSInteger temp = [mtArr[i] integerValue];
NSInteger j = i;
while (j >= bs && temp < [mtArr[j - bs] integerValue]) {
[mtArr replaceObjectAtIndex:j withObject:mtArr[j - bs]];
j -= bs;
}
[mtArr replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
bs = bs/2;
}
}
算法五：選擇排序
選擇排序.gif
算法步驟：
1.首先在未排序序列中找到最熊窈（大）元素，存放到排序序列的起始位置
2.再從剩余未排序元素中繼續(xù)尋找最辛撕俊（大）元素泪漂，然后放到已排序序列的末尾
3.重復第二步，直到所有元素均排序完畢
//選擇排序
-(void)selectionSort:(NSMutableArray *)mtArr
{
if (mtArr == nil || mtArr.count == 0) {
return;
}
int minIndex; //最小值索引
for (int i = 0; i < mtArr.count; i ++) {
minIndex = i;
for (int j = i +1; j < mtArr.count; j ++) {
if (mtArr[minIndex] > mtArr[j]) {
minIndex = j;
}
}
[mtArr exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
}
}
算法六：堆排序
堆排序.gif
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法歪泳。堆積是一個近似完全二叉樹的結構萝勤，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點。
堆排序的平均時間復雜度為Ο(nlogn) 呐伞。
算法步驟：
1.創(chuàng)建一個堆H[0..n-1]
2.把堆首（最大值）和堆尾互換
3.把堆的尺寸縮小1敌卓，并調(diào)用shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應位置
4.重復步驟2，直到堆的尺寸為1
算法七：歸并排序
歸并排序.gif
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法荸哟。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用假哎。
算法步驟：
1.申請空間，使其大小為兩個已經(jīng)排序序列之和鞍历，該空間用來存放合并后的序列舵抹；
2.設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
3.比較兩個指針所指向的元素劣砍，選擇相對小的元素放入到合并空間惧蛹，并移動指針到下一位置
4.重復步驟3直到某一指針達到序列尾
5.將另一序列剩下的所有元素直接復制到合并序列尾
算法八：基數(shù)排序
總結：
各種排序的時間復雜度、空間復雜度刑枝、穩(wěn)定性如下圖：
關于時間復雜度：
1.平方階(O(n2))排序：各類簡單排序:直接插入香嗓、直接選擇和冒泡排序
2.線性對數(shù)階(O(nlog2n))排序：快速排序、堆排序和歸并排序装畅。
O(n1+§))排序：§是介于0和1之間的常數(shù)
3.線性階(O(n))排序：基數(shù)排序靠娱，此外還有桶、箱排序
關于穩(wěn)定性：
1.穩(wěn)定的排序算法：冒泡排序掠兄、插入排序像云、歸并排序和基數(shù)排序
2.不是穩(wěn)定的排序算法：選擇排序、快速排序蚂夕、希爾排序迅诬、堆排序
參考:
http://blog.csdn.net/hguisu/article/details/7776068
http://www.reibang.com/p/481c26283d33
