一、冒泡排序
冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
1.算法過程：
（1）比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
（2）對每一對相鄰元素作同樣的操作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；
（3）針對所有的元素重復(fù)以上的步驟，除了最后一個；
（4）重復(fù)步驟1~3，直到?jīng)]有任何一對數(shù)字需要比較。
2.復(fù)雜度
假設(shè)序列有 n 個元素，(n>1)，根據(jù)算法步驟，第 1 輪 需在 n 個元素中兩兩比較 (n-1) 次，第 2 輪 需要在剩余的 (n-1) 個元素中兩兩比較 (n-2) 次，第(n-1) 輪需在最后 2 個元素中僅比較 1 次。
函數(shù)表達(dá)式為：
f(n) = (n-1) + (n-2) +...+ 2 + 1
f(n) = [1+(n-1)]×(n-1)/2
f(n) = n*(n-1)/2
f(n) = (n2 - n)/2
用 大 O 表示法，忽略常量、低階和常數(shù)系數(shù)。
時間復(fù)雜度為：O(n2)
空間復(fù)雜度為：并未開辟額外空間，所以為 O(1)
穩(wěn)定性: 穩(wěn)定
3.代碼
NSMutableArray *array = [NSMutableArray arrayWithObjects:@45,@3,@22,@23,@40,@34, nil];
for (int i = 0; i < array.count - 1; i ++) {//循環(huán)array.count-1次
for (int j = 0; j < array.count - 1 ; j ++) {
if ([array[j] integerValue] >[array[j+1] integerValue] ) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"%@",array);
這樣寫的冒泡排序需要比對（數(shù)組的個數(shù)-1）的平方次，每一圈內(nèi)循環(huán)都把最大的數(shù)換到最后，如上：第一圈 45 被替換到最后一個元素位置，第二圈 40 被替換到倒數(shù)第二個元素的位置，那么 40 和 45 還需要比對么，答案是否定的，所以可以對上述方法進(jìn)行第一次優(yōu)化：
NSMutableArray *array = [NSMutableArray arrayWithObjects:@45,@3,@22,@23,@40,@34, nil];
for (int i = 0; i < array.count - 1; i ++) {//循環(huán)array.count-1次
for (int j = 0; j < array.count - 1 - i; j ++) {
if ([array[j] integerValue] >[array[j+1] integerValue] ) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"%@",array);
當(dāng)循環(huán)結(jié)束前，數(shù)組已經(jīng)排好順序了，那么后面的比較就沒有必要了，可以跳出循環(huán)。繼續(xù)優(yōu)化結(jié)果：
for (int i = 0; i < array.count - 1; i ++) {//循環(huán)array.count-1次
BOOL isEnd = NO;//判斷是否已排序完成
for (int j = 0; j < array.count -1 -i; j++) {
if ([array[j] integerValue] >[array[j+1] integerValue] ) {
isEnd = YES;
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
if (!isEnd) {
break;
}
}
NSLog(@"%@",array);
二、選擇排序
選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時間復(fù)雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。
1.算法過程
（1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
（2）再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。
（3）重復(fù)第二步，直到所有元素均排序完畢。
2.復(fù)雜度
假設(shè)序列有 n 個元素（n>1），根據(jù)算法步驟，第 1 輪 需在 n 個元素中遍歷 n 次查找到最小的元素，第2輪 需在剩余的 (n-1) 個元素中遍歷 (n-1) 次找到最小的元素，… 第 n-1 輪 需在剩余的 2 個元素中找到最小的元素，第 n 輪剩余 1 個元素放在已排序元素的末尾。
函數(shù)表達(dá)式為：
f(n) = n+(n-1)+…+2+1
f(n) = (n+1)*n/2
f(n) = (n2+n)/2
用 大 O 表示法，忽略常量、低階和常數(shù)系數(shù)。
時間復(fù)雜度為：O(n2)
空間復(fù)雜度為：并未開辟額外空間，所以為 O(1)
穩(wěn)定性: 不穩(wěn)定
3.代碼
int count = 0;
NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,nil];
for (int i = 0; i<array.count - 1; i++) {
NSInteger min = [array[i] integerValue];
NSInteger index = i;
for (NSInteger j= i+1; j< array.count; j++) {
if (min > [array[j] integerValue]) {
min = [array[j] integerValue];
index = j;
}
count ++;
}
[array exchangeObjectAtIndex:index withObjectAtIndex:i];
}
NSLog(@"排序后的數(shù)組===%@",array);
NSLog(@"循環(huán)次數(shù)count=%d",count);
優(yōu)化：在循環(huán)選取時，每次掃描未排序區(qū)間分別選擇最小、最大值放于數(shù)組始、末位置
NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
for (int i = 0; i<array.count - 1; i++) {
NSInteger min = [array[i] integerValue];
NSInteger max = [array[array.count - 1 - i] integerValue];
NSInteger minIndex = i;
NSInteger maxIndex = array.count - 1 - i;
if(minIndex +1 == maxIndex||minIndex == maxIndex){
break;
}
for (NSInteger j= i+1; j< array.count-i; j++) {
if (min > [array[j] integerValue]) {
min = [array[j] integerValue];
minIndex = j;
}
if (max < [array[j] integerValue]) {
max = [array[j] integerValue];
maxIndex = j;
}
}
[array exchangeObjectAtIndex:minIndex withObjectAtIndex:i];
[array exchangeObjectAtIndex:maxIndex withObjectAtIndex:array.count - i - 1];
}
NSLog(@"排序后的數(shù)組===%@",array);
4.不穩(wěn)定性
選擇排序是給每個位置選擇當(dāng)前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第 n-1個元素，第 n 個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當(dāng)前元素小，而該小的元素又出現(xiàn)在一個和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列 5,8,5,3,6，我們知道第一遍選擇第 1 個元素 5 會和 3 交換，那么原序列中兩個 5 的 相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。
三、插入排序
插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。可以形象地比喻成打撲克牌的時候整理牌的順序的方法。
1.算法過程描述
（1）從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序；
（2）取出下一個元素作為新元素，在已經(jīng)排序的元素序列中從后向前掃描；
（3）如果該元素（已排序）大于新元素，將該元素移到下一位置；
（4）重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
（5）將新元素插入到該位置后；
（6）重復(fù)步驟2~5。
2.復(fù)雜度
假設(shè)序列有 n 個元素（n>1），根據(jù)算法步驟，第 1 輪取第2個元素插入到已排序數(shù)列（1個元素）中，第 2 輪取 第3個元素插入到已排序數(shù)列（有2個元素）中，… 第 (n-1) 輪取第n個元素插入到已排序數(shù)列（有(n-1)` 個元素）中。
函數(shù)表達(dá)式為：
f(n) = 1+2+…+(n-1)
f(n) = n*(n-1)/2
f(n) = (n2-n)/2
用 大 O 表示法，忽略常量、低階和常數(shù)系數(shù)。
時間復(fù)雜度為：O(n2)
空間復(fù)雜度為：并未開辟額外空間，所以為O(1)
穩(wěn)定性: 穩(wěn)定
3.代碼
NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
for (int i = 0; i<array.count ; i++) {
NSInteger valueI = [array[i] integerValue];
for (int j= i - 1; j >= 0; j--) {
NSInteger valueJ = [array[j] integerValue];
if(valueI < valueJ){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i = j;
}
}
}
NSLog(@"排序后的數(shù)組===%@",array);
四、快速排序
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
基本思想是，通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。
1.算法過程描述
（1）從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）；
（2）重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
（3）遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
如果要排序數(shù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)，我們選擇 p 到 r之間的任意一個數(shù)據(jù)作為 pivot(分區(qū)點), 我們遍歷 p 到r之間的數(shù)據(jù)，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過這一步驟之后，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到r 之間是大于 pivot 的。
剩下，可以用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到 r之間的數(shù)據(jù)，直到區(qū)間縮小為 1，就說明所有的數(shù)據(jù)都有序了。
2.復(fù)雜度
用 大O 表示法，忽略常量、低階和常數(shù)系數(shù)。
時間復(fù)雜度為：最壞 O(n2) ， 最好 O(nlogn)
空間復(fù)雜度為：并未開辟額外空間，所以為 O(1)
穩(wěn)定性: 不穩(wěn)定
3.代碼
- (void)viewDidLoad {
[super viewDidLoad];
self.view.backgroundColor = [UIColor whiteColor];
NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
[self quickSortArray:array withLeftIndex:0 andRightIndex:(int)array.count - 1];
NSLog(@"排序后的數(shù)組===%@",array);
}
//快速排序
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex{
if (leftIndex >= rightIndex) {//如果數(shù)組長度為0或1時返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準(zhǔn)數(shù)
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先從右邊j開始查找比基準(zhǔn)數(shù)小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基準(zhǔn)數(shù)大，繼續(xù)查找
j--;
}
//如果比基準(zhǔn)數(shù)小，則將查找到的小值調(diào)換到i的位置
array[i] = array[j];
/**** 當(dāng)在右邊查找到一個比基準(zhǔn)數(shù)小的值時，就從i開始往后找比基準(zhǔn)數(shù)大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基準(zhǔn)數(shù)小，繼續(xù)查找
i++;
}
//如果比基準(zhǔn)數(shù)大，則將查找到的大值調(diào)換到j(luò)的位置
array[j] = array[i];
}
//將基準(zhǔn)數(shù)放到正確位置
array[i] = @(key);
/**** 遞歸排序 ***/
//排序基準(zhǔn)數(shù)左邊的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基準(zhǔn)數(shù)右邊的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
4.穩(wěn)定性
如果數(shù)組中有兩個相同的元素，比如測試的序列 6，8，7，6，3，5，9，4 在經(jīng)過第一次分區(qū)操作之后，兩個 6 的相對先后順序就會改變。所以，快速排序并不是一個穩(wěn)定的排序算法。
5.快速排序的性能分析
最好的情況下, 選擇的 pivot 都很合適，正好能將大區(qū)間對等地一分為二。這時快排的時間復(fù)雜度遞推求解公式跟歸并是相同的。即為 O(nlogn)。
最壞的情況下，有序數(shù)組中，每次選擇最后一個元素作為 pivot，那每次分區(qū)得到的兩個區(qū)間都是不均等的。我們需要進(jìn)行大約 n 次分區(qū)操作，才能完成快排的整個過程。每次分區(qū)我們平均要掃描大約 n/2 個元素，快排的時間復(fù)雜度就從 O(nlogn) 退化成了 O(n2)。
T(n) 在大部分情況下的時間復(fù)雜度都可以做到 O(nlogn)，只有在極端情況下，才會退化到 O(n2)。
