網(wǎng)上搜羅了一些資料，整理了下算法的OC的實(shí)現(xiàn)代碼，雖然平時(shí)開(kāi)發(fā)中一般用不到，但是多積累一些技術(shù)知識(shí)，還是對(duì)以后發(fā)展大有裨益的
1. 冒泡排序算法(Bubble Sort)
相鄰元素進(jìn)行比較，按照升序或者降序，交換兩個(gè)相鄰元素的位置 是一種“穩(wěn)定排序算法”
1.2算法步驟：
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
1.3 動(dòng)圖演示
1.4 什么時(shí)候最快
當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)。
1.5 什么時(shí)候最慢
當(dāng)輸入的數(shù)據(jù)是反序時(shí)。
1.6 冒泡排序代碼示例
- (void)bubbleSortWithArray:(NSMutableArray *)array {
for (int i = 0; i < array.count - 1; i++) {
//外層for循環(huán)控制循環(huán)次數(shù)
for (int j = 0; j < array.count - 1 - i; j++) {
//內(nèi)層for循環(huán)控制交換次數(shù)
if ([array[j] integerValue] > [array[j + 1] integerValue]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
}
NSLog(@"%@",array);
}
[self bubbleSortWithArray:[@[@"1",@"7",@"3",@"5"] mutableCopy]];
2. 快速排序算法(quick sort)
快速排序(Quick Sort) 的基本思想是：
通過(guò)一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。
排序思路：
數(shù)組選第一個(gè)數(shù)，把比數(shù)小的放到數(shù)的左邊，比數(shù)大的放到右邊，結(jié)束后對(duì)左右兩邊的數(shù)組作重復(fù)處理即可。
快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。
2.2 算法步驟
從數(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ù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
2.3 動(dòng)圖演示
2.4 快速排序代碼示例
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果數(shù)組長(zhǎng)度為0或1時(shí)返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準(zhǔn)數(shù)
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先從右邊j開(kāi)始查找比基準(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)在右邊查找到一個(gè)比基準(zhǔn)數(shù)小的值時(shí)，就從i開(kā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];
}
NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count-1];
NSLog(@"%@",array);
二叉樹的遍歷
1、前序遍歷： 規(guī)則是若二叉樹為空，則空操作返回，否則先訪問(wèn)根節(jié)點(diǎn)，在前序遍歷左子樹，再前序遍歷右子樹。 （輸出、左重新遞歸、右重新遞歸）
2、中序遍歷: 規(guī)則是若樹為空，則空操作返回，否則從根節(jié)點(diǎn)開(kāi)始（注意并不是先訪問(wèn)哪根節(jié)點(diǎn)），中序遍歷根節(jié)點(diǎn)的左子樹，然后訪問(wèn)根節(jié)點(diǎn)，最后中序遍歷右子樹。 （左重新遞歸、輸出、右重新遞歸）
3、后序遍歷：規(guī)則是若樹為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹，最后是訪問(wèn)根節(jié)點(diǎn)。
4、層序遍歷：規(guī)則是若樹為空，則空操作返回，否則從樹的第一層，也就是根節(jié)點(diǎn)開(kāi)始訪問(wèn)，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問(wèn)。
算法四：二分查找算法
二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜素過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區(qū)域減少一半，時(shí)間復(fù)雜度為Ο(logn)。
使用二分法好處:可以加快尋找的效率。
二分法的思路： 它是通過(guò)與數(shù)組的中間值進(jìn)行比較的
步驟如下：
1.我們要查找的值為X
2.數(shù)組是從小到大排序的
**
1.先取出數(shù)組中間的元素
2.把中間元素和X進(jìn)行比較，如果中間元素大于X，那么X就位于第一個(gè)元素，和中間元素之間。反之，如果中間元素小于X，那么X就位于中間元素和最大值之間。
3.這樣進(jìn)行比較之后，我們的查找范圍就小了一半。
NSArray *arr = @[@1,@20,@30,@45,@50,@55,@60,@66,@70];
NSInteger x = 70,min,max,mid;
min = 0;
max = arr.count - 1;
mid = (min + max) / 2;
for (int i = 0; i < arr.count; i++){
if ([arr[mid] integerValue] == x){
NSLog(@"查找次數(shù)為--->%d次",i);
NSLog(@"尋找值位置為--->%ld",mid);
return;
}
else if ([arr[mid] integerValue] > x){
max = mid - 1;
mid = (min + max) / 2;
}
else if ([arr[mid] integerValue] < x){
min = mid + 1;
mid = (min + max) / 2;
}
