一、概述
先放两张图，记是记不住，这辈子...不，一个一个去深入研究学习是能记住的。
image
image
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2n)＜Ο(n!)<O(nn)
计算时间复杂度
⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需保留f(n)中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。
如：第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n²)，则整个算法的时间复杂度为Ο(n+n²)=Ο(n²)。
注：加法原则：T(n)=O(f(n))+O(g(n))=O(max(fn,gn))
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。
- 对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个循环的时间复杂度为 O(n×m)。此时时间复杂度为 O(n × 1)，即 O(n)。
- 对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...，则这个循环的时间复杂度为 O(n×a×b×c...)。由里向外分析这些循环的次数，此时时间复杂度为 O(n × n × 1)，即 O(n²)。
- 对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。此时时间复杂度为 max(O(n²), O(n))，即 O(n²)。
- 对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。
- 基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。
算法稳定性：相同元素的前后顺序在任何情况都不会发生改变，这种排序成为稳定排序算法。反之成为不稳定排序算法。
二、详解代码
代码一时半会没看懂，可以看看书《数据结构》C语言版，看看视频，研究的过程印象更深，理解更深，更有成就感。
思路懂了但是代码还是不会写的可以看看视频：归并排序、堆排序。
代码方案不是唯一的，生活也是。
先来个几个测试按钮
-(void)setupButton{
NSArray *textArr = @[@"插入排序",@"希尔排序",@"直接选择排序",@"堆排序",@"冒泡排序",@"快速排序",@"归并排序",@"基数排序"];
for (int i = 0; i < textArr.count; ++i) {
UIButton *button = [UIButton buttonWithType:UIButtonTypeSystem];
button.titleLabel.font = [UIFont boldSystemFontOfSize:20];
[button setTitle:textArr[i] forState:UIControlStateNormal];
button.bounds = CGRectMake(0, 0, button.intrinsicContentSize.width, button.intrinsicContentSize.height);
button.center = CGPointMake(self.view.center.x, 120 + i * 40);
[button addTarget:self action:@selector(clickButton:) forControlEvents:UIControlEventTouchUpInside];
button.tag = i;
[self.view addSubview:button];
}
}
- (void)clickButton:(UIButton *)button {
CFAbsoluteTime startTime =CFAbsoluteTimeGetCurrent();
NSMutableArray *muArr = [NSMutableArray arrayWithObjects:@"1",@"66",@"3",@"2",@"888",@"4",@"55",@"777", nil];
switch (button.tag) {
case 0: {
[self sortByInsertWithArray:muArr andGap:1];
}
break;
case 1: {
[self sortByShellWithArray:muArr];
}
break;
case 2: {
[self sortBySelectWithArray:muArr];
}
break;
case 3: {
[self sortByHeapWithArray:muArr];
}
break;
case 4: {
[self sortByBubbleWithArray:muArr];
}
break;
case 5: {
[self sortByQuickWithArray:muArr low:0 high:(int)muArr.count-1];
}
break;
case 6: {
[self sortByMegerWithArray:muArr];
}
break;
case 7: {
[self sortByRadixWithArray:muArr];
}
break;
default:
break;
}
CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);
NSLog(@"排序结果：%@", muArr);
NSLog(@"Linked in %f ms", linkTime *1000.0);
}
插入排序 : 直接插入排序 & 希尔排序
-直接插入排序
#pragma mark 直接插入排序
-(void)sortByInsertWithArray:(NSMutableArray *)array{
/**
算法步骤：
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
复杂度：
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
*/
//外层for循环从第二个元素开始，i = 1 而不是 0 。有n个数字就要执行n-1次
for (NSInteger i = 1; i < array.count; i ++) {
//待排元素
NSInteger temp = [array[i] integerValue];
//从后向前扫描，与 待排元素 比较。
//待排元素 大于 j元素，不做处理
//待排元素 小于 j元素，j元素 后移，待排元素补上j位置。
for (NSInteger j = i - 1; j >= 0 ; j --) {
if (temp < [array[j] integerValue]) {
array[j + 1] = array[j];
array[j] = [NSNumber numberWithInteger:temp];
}
}
}
}
-希尔排序
#pragma mark 希尔排序
- (void)sortByShellWithArray:(NSMutableArray *)array{
/**
希尔排序（Shell Sort）也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序在插入排序的基础上增加一个叫增量的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……比较完后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这一个分组进行插入排序，整个希尔排序就结束了。
算法步骤：
1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
用这样增量序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
希尔排序复杂度分析：
在最坏的情况下时间复杂度仍为O(n²),而使用最优的增量在最坏的情况下却为O(n²⁄³)。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
*/
int N = (int)array.count;
//设置增量，每次递减 /2
for (int gap= N / 2; gap > 0; gap /= 2) {
//直接进行一个插入排序
[self sortByInsertWithArray:array andGap:gap];
}
}
-(NSMutableArray *)sortByInsertWithArray:(NSMutableArray *)array andGap:(NSInteger)gap{
//循环次数，（array.count - gap ）趟
for (NSInteger i = gap; i < array.count; i ++) {
NSInteger temp = [array[i] integerValue];
//把当前元素插入到前面去
for (NSInteger j = i - gap ; j >= 0 ; j -= gap) {
if (temp < [array[j] integerValue]) {
array[j + gap] = array[j];
array[j] = [NSNumber numberWithInteger:temp];
}
}
}
return array;
}
选择排序 : 直接选择排序 & 堆排序
-直接选择排序
#pragma mark 直接选择排序
-(void)sortBySelectWithArray:(NSMutableArray *)array{
//第一个元素和剩余的元素比较，如果其他的元素小，就交换。
//第二个元素和剩余的元素比较，如果其他的元素小，就交换。
//重复下去
//不稳定，平均时间复杂度 O(n^2)
int i , j , k ;
//有多少个数字就要执行多少次
for (i = 0; i <= array.count - 1; i++) {
k = i;
//第i个元素和余下的比较
for (j = i + 1; j <= array.count - 1; j++) {
//如果余下的某个元素比第i个元素小，记住下标
if ([array[k] integerValue] > [array[j] integerValue]) {
k = j;
}
}
//开始交换
if (k != i) {
id temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
- 堆排序
#pragma mark 堆排序
-(void)sortByHeapWithArray:(NSMutableArray *)array{
/**
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。
如第0个结点左右子结点下标分别为1和2。
堆的添加从A[n]（数组尾）开始，再进行恢复堆次序；删除从A[0]（数组首）开始，由A[n]补到A[0]位，再进行恢复堆次序。
堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)。
算法步骤：
1. 创建一个堆H[0..n-1]
2. 把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1
*/
//创建一个堆
int n =(int) array.count;
[self creatHeapWithArray:array total:n];
//排序
for (int i = n - 1; i >= 0; i--) {
//交换第一个和最后一个元素
id temp = array[0];
array[0] = array[i];
array[i] = temp;
//恢复堆次序
[self heapAdjustWithArray:array startIndex:0 total:i];
}
}
/// 创建一个堆
/// @param array 数组（树）
/// @param total 总节点数
-(void)creatHeapWithArray:(NSMutableArray *)array total:(int)total{
/**
创建一个堆，从最后一个元素的父节点开始，依次向上
*/
int last_node = total - 1; //最后一个节点
int parent_last = (last_node - 1) / 2; //最后一个节点的父节点
for (int i = parent_last; i >= 0; i--) {
[self heapAdjustWithArray:array startIndex:i total:total];
}
}
/// 对某个节点进行 heapify 堆次序
/// @param array 数组（代表树）
/// @param startIndex 开始节点（对那个点进行heapify）
/// @param total 总的节点数
-(void)heapAdjustWithArray:(NSMutableArray *)array startIndex:(int)startIndex total:(int)total{
//递归出口
if (startIndex >= total) return;
int leftIndex = startIndex * 2 + 1; //左子树下标
int rightIndex = startIndex * 2 + 2; //右子树下标
int maxIndex = startIndex; //假设最大下标
//如果 左子树元素 比 根节点元素大，并且 判断子树未出界
if (leftIndex < total && [array[leftIndex] intValue] > [array[maxIndex] intValue]) {
maxIndex = leftIndex;
}
if (rightIndex < total && [array[rightIndex] intValue] > [array[maxIndex] intValue]) {
maxIndex = rightIndex;
}
if (maxIndex != startIndex) {
//进行交换
id temp = array[startIndex];
array[startIndex] = array[maxIndex];
array[maxIndex] = temp;
//递归
[self heapAdjustWithArray:array startIndex:maxIndex total:total];
}
}
交换排序 : 冒泡排序 & 快速排序
-冒泡排序
#pragma mark 冒泡排序
-(void)sortByBubbleWithArray:(NSMutableArray *)array{
//交换相邻的2个元素，值大的必然会交换到末尾
//稳定，平均时间复杂度 O(n^2)
//有 array.count -1 趟交换
for (int i = 0; i< array.count -1 ; i++) {
//内层for循环控制 每趟的 交换次数, 每次递减
for (int j = 0; j< array.count -1 - i; j++) {
if ([array[j] integerValue] > [array[j + 1] integerValue]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
}
-快速排序
#pragma mark 快速排序
-(void)sortByQuickWithArray:(NSMutableArray *)array low:(int )low high:(int )high{
/**
实现思路：
1. 从数列中挑出一个元素，称为 "基准"（pivot）.
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
快速排序是基于分治模式处理的，对一个典型子数组A[p...r]排序的分治过程为三个步骤：
1.分解：
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r]
2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。
3.合并。
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
复杂度：
平均时间复杂度：O(n^2)
平均空间复杂度：O(nlogn) O(nlogn)~O(n^2)
*/
if (low >= high) {
return;
}
int i = low;
int j = high;
int pivotKey = [array[i] intValue];
while (i < j) {
//顺序很重要，先从右边判断, 找到比基数大的
while (i < j && [array[j] intValue] >= pivotKey) {
j--;
}
//从左边判断, 找到比基数小的
while (i < j && [array[i] intValue] <= pivotKey) {
i++;
}
//找到之后交换
if (i<j) {
id temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
//最后将基准数放到正确位置
array[low] = array[i];
array[i] = [NSNumber numberWithInt:pivotKey];
//分别递归左边右边
[self sortByQuickWithArray:array low:low high:i-1];
[self sortByQuickWithArray:array low:i +1 high:high];
}
基数排序
#pragma mark - 基数排序
-(void)sortByRadixWithArray:(NSMutableArray *)array{
/**
1.首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中.
2.将所有桶中所盛数据按照桶号由小到大依次重新收集串起来，得到如下仍然无序的数据序列.
3.再进行一次分配，这次根据十位数值来分配（同上）.
4.重复进行以上的动作直至最高位数为止.
时间复杂度
假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。我们可以看出，基数排序的效率和初始序列是否有序没有关联。
空间复杂度
在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。
算法稳定性
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
*/
// 1.创建10个桶数组
NSMutableArray *buckt = [self createBucket];
// 2.找到数组最大的元素
NSNumber *maxnumber = [self listMaxItem:array];
// 3.最大元素的位数
NSInteger maxLength = [self numberLength:maxnumber];
// digit 位数
for (int digit = 1; digit <= maxLength; digit++) {
// 根据 获取数字的最后一位的值 入桶
for (NSNumber *item in array) {
//数字的最后一位的值
NSInteger baseNumber = [self fetchLastValueWithNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
[mutArray addObject:item];
}
//所有数组归一
NSInteger index = 0;
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *tempArray = buckt[i];
while (tempArray.count != 0) {
NSNumber *number = [tempArray objectAtIndex:0];
array[index] = number;
[tempArray removeObjectAtIndex:0];
index++;
}
}
}
}
/// 创建多个桶数组
- (NSMutableArray *)createBucket {
NSMutableArray *bucket = [NSMutableArray array];
for (int index = 0; index < 10; index++) {
NSMutableArray *array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}
/// 找到数组最大的元素
- (NSNumber *)listMaxItem:(NSArray *)list {
NSNumber *maxNumber = list[0];
for (NSNumber *number in list) {
if ([maxNumber integerValue] < [number integerValue]) {
maxNumber = number;
}
}
return maxNumber;
}
/// 最大元素的位数
- (NSInteger)numberLength:(NSNumber *)number{
NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
return string.length;
}
/// 获取数字的最后一位的值
- (NSInteger)fetchLastValueWithNumber:(NSNumber *)number digit:(NSInteger)digit {
if (digit > 0 && digit <= [self numberLength:number]) {
NSMutableArray *numbersArray = [NSMutableArray array];
NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
//将数字分割成数组
for (int index = 0; index < [self numberLength:number]; index++) {
[numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
}
//获取最后一位的元素值
NSString *str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
归并排序
#pragma mark - 归并排序
-(void)sortByMegerWithArray:(NSMutableArray *)array{
/**
把序列分成元素尽可能相等的两半。
把两半元素分别进行排序。
把两个有序表合并成一个。
*/
int L = 0;
int R = (int)array.count - 1;
[self sortByMeger:array leftIndex:L rightIndex:R];
}
/// 归并排序，无序数组
/// @param array 待排数组
/// @param leftIndex 起始下标
/// @param rightIndex 结束下标
-(void)sortByMeger:(NSMutableArray *)array leftIndex:(int)leftIndex rightIndex:(int)rightIndex{
//跳出递归
if (leftIndex == rightIndex) {
return;
}else{
int midIndex = (rightIndex + leftIndex ) / 2;
//递归 排序左侧
[self sortByMeger:array leftIndex:leftIndex rightIndex:midIndex];
//递归 排序右侧 midIndex+1 ：保证取同一个中间下标
[self sortByMeger:array leftIndex:midIndex+1 rightIndex:rightIndex];
// 左侧 和 右侧 有序，归并
[self meger:array leftIndex:leftIndex midIndex:midIndex+1 rightIndex:rightIndex];
}
}
/// 一次归并排序，假设从中间分开左右数组就有序
/// @param array 待排数组
/// @param leftIndex 起始下标
/// @param midIndex 中间下标
/// @param rightIndex 结束下标
-(void)meger:(NSMutableArray *)array leftIndex:(int)leftIndex midIndex:(int)midIndex rightIndex:(int)rightIndex{
int left_size = midIndex - leftIndex;
int right_size = rightIndex - midIndex + 1;
NSMutableArray *leftArr = [NSMutableArray array];
NSMutableArray *rightArr = [NSMutableArray array];
//分成2组，添加到left数组
for (int i = leftIndex; i < midIndex; i++) {
[leftArr addObject:array[i]];
}
//分成2组，添加到right数组
for (int i = midIndex; i <= rightIndex; i++) {
[rightArr addObject:array[i]];
}
int i = 0, j = 0 , k = leftIndex; //i指向leftArr，j指向rightArr，k指向array
//比较left数组 和 right数组的每一个元素，依次添加到array中
while (i < left_size && j < right_size) {
if ([leftArr[i] intValue] < [rightArr[j] intValue]) {
array[k] = leftArr[i];
i++;
k++;
}else{
array[k] = rightArr[j];
j++;
k++;
}
}
//比较完，某一个数组有剩余的直接添加到array中
while (i < left_size) {
array[k] = leftArr[i];
i++;
k++;
}
while (j < right_size) {
array[k] = rightArr[j];
j++;
k++;
}
}
/// 合并2个有序的数组
/// @param array 结果数组
/// @param leftArr 有序的待合并数组leftArr
/// @param rightArr 有序的待合并数组rightArr
-(void)sortByMeger:(NSMutableArray *)array leftArr:(NSMutableArray *)leftArr rightArr:(NSMutableArray *)rightArr{
int left_size = (int)leftArr.count;
int right_size = (int)rightArr.count;
int i = 0, j = 0 , k = 0; //i指向leftArr，j指向rightArr，k指向array
//比较left数组 和 right数组的每一个元素，依次添加到array中
while (i < left_size && j < right_size) {
if ([leftArr[i] intValue] < [rightArr[j] intValue]) {
array[k] = leftArr[i];
i++;
k++;
}else{
array[k] = rightArr[j];
j++;
k++;
}
}
//比较完，某一个数组有剩余的直接添加到array中
while (i < left_size) {
array[k] = leftArr[i];
i++;
k++;
}
while (j < right_size) {
array[k] = rightArr[j];
j++;
k++;
}
NSLog(@"合并2个有序的数组：- %@",array);
}
