OC-排序算法总结（冒泡、快速、插入、选择、希尔、堆）
一、时间复杂度和空间复杂度
要学习算法首先要弄明白两个概念
1、时间复杂度：即一个算法执行所耗费的时间，理论上不可计算，只能通过上机测试，但可以根据它的变化规律预估出一个时间，记为T(n)，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。
计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。
2、空间复杂度：一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
参考：算法的时间复杂度和空间复杂度-总结
二、算法原理及实现代码
各算法时间复杂度和空间复杂度对比图
1、冒泡排序
原理：这种算法会重复的比较数组中相邻的两个元素，如果一个元素比另一个元素大（小），那么就交换这两个元素的位置。重复这一比较直至最后一个元素。每一趟比较都能找出未排序元素中最大或者最小的那个数字。这就如同水泡从水底逐个飘到水面一样。冒泡排序是一种时间复杂度较高，效率较低的排序方法。
时间复杂度：O(n^2),优化后可能达到O(n)，但会增加空间复杂度
空间复杂度：O(1)
-(void)bubbleSequence:(NSMutableArray *)arr
{
//普通排序-交换次数较多
for (int i = 0; i < arr.count; ++i) {
for (int j = 0; j < arr.count-1-i; ++j) {
if ([arr[j+1] intValue] < [arr[j] intValue]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
//优化后算法-从第一个开始排序，空间复杂度相对更大一点
for (int i = 0; i < arr.count; ++i) {
bool flag=false;
//遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
for (int j = 0; j < arr.count-1-i; ++j) {
//根据索引的`相邻两位`进行`比较`
if ([arr[j+1] intValue] < [arr[j] intValue]) {
flag = true;
[arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
if (!flag) {
break;//没发生交换直接退出，说明是有序数组
}
}
//优化后算法-从最后一个开始排序
for (int i = 0; i <arr.count; ++i) {
bool flag=false;
//遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
for (int j = (int)arr.count-1; j >i; --j) {
//根据索引的`相邻两位`进行`比较`
if ([arr[j-1] intValue] > [arr[j] intValue]) {
flag = true;
[arr exchangeObjectAtIndex:j withObjectAtIndex:j-1];
}
}
if (!flag) {
break;//没发生交换直接退出，说明是有序数组
}
}
}
2、选择排序
原理：从第一个元素开始，依次查找对比，找到最小的元素与第一个元素交换，再从第二个元素开始找后面元素的最小值与第二个元素交换，以此类推，直到整个数组有序。
时间复杂度和空间复杂度与冒泡排序一致
-(void)chooseSequence:(NSMutableArray *)arr
{
//选择排序-依次找出剩余元素最小值 ,对于长度为 N 的数组,选择排序需要大约 N^2 次比较和 N 次交换
for (int i = 0; i<arr.count; i++) {
int min = I;
int a = [arr[i] intValue];
for (int j = i+1; j<arr.count; j++) {
if ([arr[j] intValue]<a) {
min = j;
a = [arr[j] intValue];
}
}
[arr exchangeObjectAtIndex:i withObjectAtIndex:min];
}
//或者下面方法，就是交换次数比较多
for (int i = 0; i<arr.count; i++) {
for (int j = i+1; j<arr.count; j++) {
if ([arr[j] intValue]<[arr[i] intValue]) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
}
冒泡与选择对比：
选择比冒泡效率高，一次循环只交换一次，冒泡也可以记录坐标进行一次交换，但空间复杂度就增加，冒泡可以检验数组是否有序，如果循环中没有一次交换说明是有序的，可以提前终止
冒泡排序在内循环交换，选择排序在外循环交换，效率差也就在这个交换次数上，毕竟O(n)<O(n^2)。如果数组完全有序，冒泡内循环的交换一次都不会执行，而选择排序每次还要和本身交换一次，此时冒泡效率高。
3、插入排序
原理：由数组的第2个位置开始比较，若果前方位置的元素比较大，则交换位置，若自己元素较大，而继续下一个元素，如此排列，那么被操作的那个元素前方位置的所有元素皆为有序。最坏情况下需要~ N^2/2 次比较和~ N^2/2 次交换,最好情况下需要 N-1次比较和 0 次交换
时间空间复杂度与冒泡排序一致
-(void)insertSequence:(NSMutableArray *)arr
{
for (int i = 1; i<arr.count; i++) {
int a=[arr[i] intValue];
int k = i-1;
while (k>=0&&[arr[k] intValue]>a) {
arr[k + 1] = arr[k];
k-=1;
}
arr[k+1] = [NSString stringWithFormat:@"%d",a];
NSLog(@"%@",arr);
}
}
或者
NSMutableArray *InsetSort(NSMutableArray *mArray, NSInteger start) {
if (start == mArray.count) {
return mArray;
}
for (NSInteger i = start; i > 0; i --) {
if ([mArray[i] intValue] < [mArray[i-1] intValue]) {
int temp = [mArray[i] intValue];
int k = (int)(i - 1);
while (k >= 0 && [mArray[k] intValue] > temp) {
mArray[k + 1] = mArray[k];
k -= 1;
}
mArray[k+1] = [NSString stringWithFormat:@"%d",temp];
}
}
InsetSort(mArray, start + 1);
return mArray;
}
插入排序优势：对于有序数组或部分有序数组，此排序方法是十分高效的，很适合小规模的数组，很多高级的排序算法都会利用到插入排序。
插入排序劣势：若果最少的元素都在最后部分的位置，那么该排序方法就会变得非常费劲了，最后的元素都要比较改元素位置减一次。
4、快速排序
原理：从数列中挑出一个元素，称为 "基准"， 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，再以该基准为分界，分左右两边，分别挑选基准递归的进行排序。
时间复杂度：最差O(n^2)，平均O(nlogn)
空间复杂度：O(nlogn)
-(void)quickSequence:(NSMutableArray *)arr andleft:(int)left andright:(int)right
{
if (left >= right) {//如果数组长度为0或1时返回
return ;
}
int key = [arr[left] intValue];
int i = left;
int j = right;
while (i<j){
while (i<j&&[arr[j] intValue]>=key) {
j--;
}
arr[i] = arr[j];
while (i<j&&[arr[i] intValue]<=key) {
I++;
}
arr[j] = arr[i];
}
arr[i] = [NSString stringWithFormat:@"%d",key];
[self quickSequence:arr andleft:left andright:i-1];
[self quickSequence:arr andleft:i+1 andright:right];
}
5、希尔排序
原理：插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……比较完后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这一个分组进行插入排序，整个希尔排序就结束了。
//起始间隔值gap设置为总数的一半，直到gap==1结束
-(void)shellSort:(NSMutableArray *)list{
int gap = (int)list.count / 2;
while (gap >= 1) {
for(int i = gap ; i < [list count]; i++){
NSInteger temp = [[list objectAtIndex:i] intValue];
int j = i;
while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
j -= gap;
}
[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap / 2;
}
}
希尔排序优势：希尔排序优化了插入排序，在性能上比选择排序和插入排序快得多，而这种优势会随着数组越大变得越为明显。而且算法代码短简单，非常容易实现，所以我们基本上所有排序工作一开始都是用希尔排序，若在实际中不够快，我们再改成快速排序等更为高级的算法。
希尔排序劣势： 希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
6、堆排序
原理：
1、 从下往上，从右往左的顺序查找每个非叶子结点，对比子结点，与最大结点交换位置，交换的新位置再与其子结点比较、移动，遍历后最终找到最大值，形成一个大顶堆（小顶堆也行）。
2、把堆顶和最后的元素交换位置，排除最后的位置，重复1步骤，找到遍历后的最大值，放到倒数第二的位置，依次直到结束。
其他算法后续更新
堆 是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；或者每个节点的值都小于或等于其左右孩子结点的值称为小顶堆。
- (void)heapSort:(NSMutableArray *)list
{
NSInteger i ,size;
size = list.count;
//找出最大的元素放到堆顶
for (i= list.count/2; i>=0; i--) {
[self createBiggesHeap:list withSize:size beIndex:i];
}
while(size > 0){
[list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
size -- ;//树大小减小
[self createBiggesHeap:list withSize:size beIndex:0];
}
NSLog(@"%@",list);
}
- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element
{
NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
while (rchild < size) { //子树均在范围内
if (list[element]>=list[lchild] && list[element]>=list[rchild]) return; //如果比左右子树都大，完成整理
if (list[lchild] > list[rchild]) { //如果左边最大
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循环时整理子树
}else{//否则右面最大
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新计算子树位置
}
//只有左子树且子树大于自己
if (lchild < size && list[lchild] > list[element]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
堆排序运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。在构建堆的过程中，对每个终端节点最多进行两次比较操作，因此整个排序堆的时间复杂度为O(n)。
空间复杂度上，它只有一个用来交换的暂存单元，也是非常不错。不过由于记录的比较和交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。
另外，由于初始构建堆排序需要的比较次数较多，因此，它不适合待排序序列个数较少的情况。
参考：
冒泡排序及其复杂度分析
iOS 开发中常用的排序（冒泡、选择、快速、插入、希尔、归并、基数）算法
学习IOS的一些简单的排序算法
iOS算法总结-希尔排序
iOS算法总结-堆排序
iOS算法总结-归并排序
