網(wǎng)上搜羅了一些資料，整理了下算法的OC的實現(xiàn)代碼，雖然平時開發(fā)中一般用不到，但是多積累一些技術知識，還是對以后發(fā)展大有裨益的
1. 冒泡排序算法(Bubble Sort)
相鄰元素進行比較，按照升序或者降序，交換兩個相鄰元素的位置 是一種“穩(wěn)定排序算法”
1.2算法步驟：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
針對所有的元素重復以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
1.3 動圖演示
1.4 什么時候最快
當輸入的數(shù)據(jù)已經(jīng)是正序時。
1.5 什么時候最慢
當輸入的數(shù)據(jù)是反序時。
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) 的基本思想是：
通過一趟排序?qū)⒋判虻挠涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序的目的。
排序思路：
數(shù)組選第一個數(shù)，把比數(shù)小的放到數(shù)的左邊，比數(shù)大的放到右邊，結(jié)束后對左右兩邊的數(shù)組作重復處理即可。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
2.2 算法步驟
從數(shù)列中挑出一個元素，稱為 “基準”（pivot）;
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序；
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
2.3 動圖演示
2.4 快速排序代碼示例
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果數(shù)組長度為0或1時返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準數(shù)
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先從右邊j開始查找比基準數(shù)小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基準數(shù)大，繼續(xù)查找
j--;
}
//如果比基準數(shù)小，則將查找到的小值調(diào)換到i的位置
array[i] = array[j];
/**** 當在右邊查找到一個比基準數(shù)小的值時，就從i開始往后找比基準數(shù)大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基準數(shù)小，繼續(xù)查找
i++;
}
//如果比基準數(shù)大，則將查找到的大值調(diào)換到j的位置
array[j] = array[i];
}
//將基準數(shù)放到正確位置
array[i] = @(key);
/**** 遞歸排序 ***/
//排序基準數(shù)左邊的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基準數(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ī)則是若二叉樹為空，則空操作返回，否則先訪問根節(jié)點，在前序遍歷左子樹，再前序遍歷右子樹。 （輸出、左重新遞歸、右重新遞歸）
2、中序遍歷: 規(guī)則是若樹為空，則空操作返回，否則從根節(jié)點開始（注意并不是先訪問哪根節(jié)點），中序遍歷根節(jié)點的左子樹，然后訪問根節(jié)點，最后中序遍歷右子樹。 （左重新遞歸、輸出、右重新遞歸）
3、后序遍歷：規(guī)則是若樹為空，則空操作返回，否則從左到右先葉子后結(jié)點的方式遍歷訪問左右子樹，最后是訪問根節(jié)點。
4、層序遍歷：規(guī)則是若樹為空，則空操作返回，否則從樹的第一層，也就是根節(jié)點開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點逐一訪問。
算法四：二分查找算法
二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區(qū)域減少一半，時間復雜度為Ο(logn)。
使用二分法好處:可以加快尋找的效率。
二分法的思路： 它是通過與數(shù)組的中間值進行比較的
步驟如下：
1.我們要查找的值為X
2.數(shù)組是從小到大排序的
**
1.先取出數(shù)組中間的元素
2.把中間元素和X進行比較，如果中間元素大于X，那么X就位于第一個元素，和中間元素之間。反之，如果中間元素小于X，那么X就位于中間元素和最大值之間。
3.這樣進行比較之后，我們的查找范圍就小了一半。
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;
}
