1.冒泡排序
依次循環(huán)旁邊的比較放到后邊去
/**
最好時間復(fù)雜度是O(n)
最壞時間復(fù)雜度是O(n^2)
平均時間復(fù)雜度：O(n^2)
平均空間復(fù)雜度：O(1)
*/
- (void)foolSortArray:(NSMutableArray *)array {
? ? for (int i = 0; i < array.count-1; i++) {
? ? ? ? for (int j = 0; j < array.count-i-1; j++) {
? ? ? ? ? ? if (array[j] > array[j+1]) {
? ? ? ? ? ? ? ? id tmp = array[j];
? ? ? ? ? ? ? ? array[j] = array[j+1];
? ? ? ? ? ? ? ? array[j+1] = tmp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
2.選擇排序
用前邊的和后邊的依次比較放到前邊去，就是先排好前邊的
- (void)selectSortArray:(NSMutableArray *)array {
? ? for (int i = 0; i < array.count-1; i++) {
? ? ? ? for (int j = i+1; j < array.count; j++) {
? ? ? ? ? ? if (array[i] > array[j]) {
? ? ? ? ? ? ? ? id tmp = array[i];
? ? ? ? ? ? ? ? array[i] = array[j];
? ? ? ? ? ? ? ? array[j] = tmp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
3.插入排序
- (void)insertSortArray:(NSMutableArray *)array {
? ? for (int i = 1; i < [array count]; i++) {
? ? ? ? int j = i;
? ? ? ? NSInteger temp = [[array objectAtIndex:i] integerValue];
? ? ? ? while (j > 0 && temp < [[array objectAtIndex:j - 1] integerValue]) {
? ? ? ? ? ? [array replaceObjectAtIndex:j withObject:[array objectAtIndex:(j - 1)]];
? ? ? ? ? ? j--;
? ? ? ? }
? ? ? ? [array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
? ? }
}
4.希爾排序
是把記錄按下標的一定增量分組扮饶，對每組使用直接插入排序算法排序啦撮；隨著增量逐漸減少艇纺，每組包含的關(guān)鍵詞越來越多嗜侮，當增量減至1時役纹，整個文件恰被分成一組贡羔，算法便終止尸饺。
增量：插入排序只能與相鄰的元素進行比較，而希爾排序則是進行跳躍比較沈堡，而增量就是步長静陈。
/**
最優(yōu)的增量在最壞的情況下卻為O(n2?3)，最壞的情況下時間復(fù)雜度仍為O(n2)
需要注意的是诞丽，增量序列的最后一個增量值必須等于1才行
另外由于記錄是跳躍式的移動鲸拥，希爾排序并不是一種穩(wěn)定的排序算法
*/
- (void)shellSortArray:(NSMutableArray *)array {
? ? int count = (int)array.count;
? ? // 初始增量為數(shù)組長度的一半，然后每次除以2取整
? ? for (int increment = count/2; increment > 0; increment/=2) {
? ? ? ? // 初始下標設(shè)為第一個增量的位置僧免，然后遞增
? ? ? ? for (int i = increment; i<count; i++) {
? ? ? ? ? ? // 獲取當前位置
? ? ? ? ? ? int j = i;
? ? ? ? ? ? // 然后將此位置之前的元素刑赶，按照增量進行跳躍式比較
? ? ? ? ? ? while (j-increment>=0 && [array[j] integerValue]<[array[j-increment] integerValue]) {
? ? ? ? ? ? ? ? [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
? ? ? ? ? ? ? ? j-=increment;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
5.快速排序
/**
最理想情況算法時間復(fù)雜度O(nlogn)，最壞O(n^2),平均O(nlogn)
平均空間復(fù)雜度：O(nlogn)? ? ? O(nlogn)~O(n^2)
*/
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
? ? if (leftIndex >= rightIndex) { // 如果數(shù)組長度為0或1時返回
? ? ? ? return ;
? ? }
? ? NSInteger i = leftIndex;
? ? NSInteger j = rightIndex;
? ? NSInteger key = [array[i] integerValue]; // 記錄比較基準數(shù)
? ? 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(luò)的位置
? ? ? ? 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];
}
6.堆排序
堆（heap）是計算機科學中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱
堆總是滿足下列性質(zhì)：1. 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；2. 堆總是一棵完全二叉樹法希，將根節(jié)點最大的堆叫做最大堆或大根堆枷餐，根節(jié)點最小的堆叫做最小堆或小根堆
完全二叉樹：
若設(shè)二叉樹的深度為h，除第 h 層外苫亦，其它各層 (1～h-1) 的結(jié)點數(shù)都達到最大個數(shù)毛肋，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹屋剑。
/**
時間復(fù)雜度為O(nlogn)
*/
- (void)heapSortArray:(NSMutableArray *)heapList len:(NSInteger)len {
? ? // 建立堆润匙，從最底層的父節(jié)點開始
? ? for(NSInteger i = (heapList.count/2 -1); i>=0; i--)
? ? ? ? [self adjustHeap:heapList location:i len:heapList.count];
? ? for(NSInteger i = heapList.count -1; i >= 0; i--){
? ? ? ? NSInteger maxEle = ((NSString *)heapList[0]).integerValue;
? ? ? ? heapList[0] = heapList[i];
? ? ? ? heapList[i] = @(maxEle).stringValue;
? ? ? ? [self adjustHeap:heapList location:0 len:i];
? ? }
}
- (void)adjustHeap:(NSMutableArray *)heapList location:(NSInteger)p len:(NSInteger)len {
? ? NSInteger curParent = ((NSString *)heapList[p]).integerValue;
? ? NSInteger child = 2*p + 1;
? ? while (child < len) {
? ? ? ? // left < right
? ? ? ? if (child+1 < len && ((NSString *)heapList[child]).integerValue < ((NSString *)heapList[child+1]).integerValue) {
? ? ? ? ? ? child ++;
? ? ? ? }
? ? ? ? if (curParent < ((NSString *)heapList[child]).integerValue) {
? ? ? ? ? ? heapList[p] = heapList[child];
? ? ? ? ? ? p = child;
? ? ? ? ? ? child = 2*p + 1;
? ? ? ? }
? ? ? ? else
? ? ? ? ? ? break;
? ? }
? ? heapList[p] = @(curParent).stringValue;
}
7.歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并饼丘，得到完全有序的序列趁桃；即先使每個子序列有序，再使子序列段間有序肄鸽。若將兩個有序表合并成一個有序表卫病，稱為二路歸并。
/**
時間復(fù)雜度為O(nlogn)
（1）“分解”——將序列每次折半劃分
（2）“合并”——將劃分后的序列段兩兩合并后排序
*/
- (NSArray *)mergeSortArray:(NSMutableArray *)array {
? ? // 排序數(shù)組
? ? NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
? ? // 第一趟排序是的子數(shù)組個數(shù)為ascendingArr.count
? ? for (NSNumber *num in array) {
? ? ? ? NSMutableArray *subArray = [NSMutableArray array];
? ? ? ? [subArray addObject:num];
? ? ? ? [tempArray addObject:subArray];
? ? }
? ? /**
? ? 分解操作 每一次歸并操作
? ? 當數(shù)組個數(shù)為偶數(shù)時tempArray.count/2; 當數(shù)組個數(shù)為奇數(shù)時tempArray.count/2+1; 當tempArray.count == 1時典徘，歸并排序完成
? ? */
? ? while (tempArray.count != 1) {
? ? ? ? NSInteger i = 0;
? ? ? ? // 當數(shù)組個數(shù)為偶數(shù)時 進行合并操作蟀苛， 當數(shù)組個數(shù)為奇數(shù)時，最后一位輪空
? ? ? ? while (i < tempArray.count - 1) {
? ? ? ? ? ? // 將i 與i+1 進行合并操作 將合并結(jié)果放入i位置上 將i+1位置上的元素刪除
? ? ? ? ? ? tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
? ? ? ? ? ? [tempArray removeObjectAtIndex:i + 1];
? ? ? ? ? ? // i++ 繼續(xù)下一循環(huán)的合并操作
? ? ? ? ? ? i++;
? ? ? ? }
? ? }
? ? return tempArray.copy;
}
// 合并
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
? ? // 合并序列數(shù)組
? ? NSMutableArray *resultArray = [NSMutableArray array];
? ? // firstIndex是第一段序列的下標 secondIndex是第二段序列的下標
? ? NSInteger firstIndex = 0, secondIndex = 0;
? ? // 掃描第一段和第二段序列逮诲，直到有一個掃描結(jié)束
? ? while (firstIndex < array1.count && secondIndex < array2.count) {
? ? ? ? // 判斷第一段和第二段取出的數(shù)哪個更小帜平，將其存入合并序列幽告，并繼續(xù)向下掃描
? ? ? ? if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
? ? ? ? ? ? [resultArray addObject:array1[firstIndex]];
? ? ? ? ? ? firstIndex++;
? ? ? ? } else {
? ? ? ? ? ? [resultArray addObject:array2[secondIndex]];
? ? ? ? ? ? secondIndex++;
? ? ? ? }
? ? }
? ? // 若第一段序列還沒掃描完，將其全部復(fù)制到合并序列
? ? while (firstIndex < array1.count) {
? ? ? ? [resultArray addObject:array1[firstIndex]];
? ? ? ? firstIndex++;
? ? }
? ? // 若第二段序列還沒掃描完裆甩，將其全部復(fù)制到合并序列
? ? while (secondIndex < array2.count) {
? ? ? ? [resultArray addObject:array2[secondIndex]];
? ? ? ? secondIndex++;
? ? }
? ? // 返回合并序列數(shù)組
? ? return resultArray.copy;
}
8.二分查找
/**
二分查找法只適用于已經(jīng)排好序的查找
*/
- (NSInteger)dichotomySearch:(NSArray *)array target:(id)key {
? ? NSInteger left = 0;
? ? NSInteger right = [array count] - 1;
? ? NSInteger middle = [array count] / 2;
? ? while (right >= left) {
? ? ? ? middle = (right + left) / 2;
? ? ? ? if (array[middle] == key) {
? ? ? ? ? ? return middle;
? ? ? ? }
? ? ? ? if (array[middle] > key) {
? ? ? ? ? ? right = middle - 1;
? ? ? ? }else if (array[middle] < key) {
? ? ? ? ? ? left = middle + 1;
? ? ? ? }
? ? }
? ? return -1;
}
9.遞歸
斐波那契數(shù)列問題
- (NSInteger)recursion0:(NSInteger)n {
? ? if (n <= 1) return n;
? ? return [self recursion0:n-1] + [self recursion0:n-2];
}
階乘
- (NSInteger)recursion1:(NSInteger)n {
? ? if (n == 0) { //遞歸邊界
? ? ? ? return 1;
? ? }
? ? return n*[self recursion1:(n-1)];//遞歸公式
}
