冒泡排序
概念
冒泡排序是一種簡單的排序算法畏梆。它重復地走訪過要排序的數(shù)列芍碧，一次比較兩個元素痕惋，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換皆怕，也就是說該數(shù)列已經(jīng)排序完成毅舆。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端西篓。
算法分析
比較相鄰的元素。如果第一個比第二個大憋活，就交換他們兩個岂津。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對悦即。在這一點吮成，最后的元素應該會是最大的數(shù)。針對所有的元素重復以上的步驟辜梳，除了最后一個粱甫。持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較作瞄。
代碼
-(void)maopao:(NSMutableArray *)arr{
for (int i = 0; i < arr.count; i++){
for (int j = 0; j < arr.count - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
}
快排
概念
快速排序（Quicksort）是對冒泡排序的一種改進茶宵。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小粉洼，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序节预，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列属韧。在平均狀況下安拟，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較宵喂，但這種狀況并不常見糠赦。快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists)锅棕。
算法步驟
從數(shù)列中挑出一個元素拙泽，稱為 “基準”(pivot)，重新排序數(shù)列裸燎，所有元素比基準值小的擺放在基準前面顾瞻，所有元素比基準值大的擺在基準的后面(相同的數(shù)可以到任一邊)。在這個分區(qū)退出之后德绿，該基準就處于數(shù)列的中間位置荷荤。這個稱為分區(qū)(partition)操作。遞歸地(recursive)把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序移稳。遞歸的最底部情形蕴纳，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了个粱。雖然一直遞歸下去古毛，但是這個算法總會退出，因為在每次的迭代(iteration)中都许，它至少會把一個元素擺到它最后的位置去稻薇。
代碼(遞歸實現(xiàn))
-(void)quickSortWithArray:(NSMutableArray *)array withLeft:(NSInteger)left andRight:(NSInteger)right{
if (left >= right) return;
NSInteger i = left;
NSInteger j = right;
NSInteger key = [array[left] integerValue];
while (i < j) {
while (i < j && key <= [array[j] integerValue]) {
j--;
}
array[i] = array[j];
while (i < j && key >= [array[i] integerValue]) {
i++;
}
array[j] = array[i];
}
array[i] = [NSNumber numberWithInteger:key];
[self quickSortWithArray:array withLeft:left andRight:i - 1];
[self quickSortWithArray:array withLeft:i + 1 andRight:right];
}
二分查找
定義中間值和所查找值進行比較嫂冻，小于中間值就查找中間值左邊的值，大于則相反颖低。所以絮吵，二分查找要滿足被查的數(shù)組是有序排列的弧烤。
代碼
非遞歸寫法
- (NSInteger)binarySearchNoRecursion:(NSArray *)srcArray withDes:(NSNumber *)des{
NSInteger low = 0;
NSInteger high = [srcArray count] - 1;
while (low <= high) {
NSInteger middle = low + ((high - low)>>1);//中間位置計算,low+ 最高位置減去最低位置,右移一位,相當于除2.也可以用(high+low)/2
if ([des integerValue] == [srcArray[middle] integerValue]) return middle;
else if([des integerValue] < [srcArray[middle] integerValue]) high = middle - 1;
else low = middle + 1;
}
return -1;//沒有找到
}
遞歸寫法
- (NSUInteger)binarySearchWithRecursion:(NSArray *)array withDes:(NSNumber *)target start:(NSUInteger)start end:(NSUInteger)end {
if (start > end) {
return -1;//沒有找到
}
NSUInteger mid = start + (end - start) / 2;
if (target > array[mid]) {
return [self binarySearchWithRecursion:array withDes:target start:mid+1 end:end];
}else if (target < array[mid]) {
return [self binarySearchWithRecursion:array withDes:target start:start end:mid-1];
}else {
return mid;
}
}
更多算法參考：吳白
