本文主要讲述了常见的各种排序方法，通过简单的排序方法的解读来提高算法思维能力
许多排序算法的性能都与输入模型有很大关系，在不同场景可以选择不同的排序算法
内容：
1、分别学习插入排序、交换排序、选择排序，归并排序
2、每种排序都了解算法原理、算法实现，算法分析
3、最后会进行各排序算法的比较和总结
0、排序介绍
所谓排序就是整理表中的元素，使之按关键字递增或递减的顺序排列。接下来都以递增排序来解读
算法分析：
包括时间复杂度、空间复杂度，再加上一个稳定性的判断。
时间复杂度和空间复杂度的详细介绍和计算通过这个笔记来学习 https://kdocs.cn/l/che5xm63oTyM
[金山文档] 第1章绪论.pof
-
时间复杂度
- 算法的执行效率由最基本的运算执行次数来衡量
- 有这么几种，其执行效率为Ｏ(1) < Ｏ(logn) < Ｏ(n) < Ｏ(nlogn) < Ｏ(n^2) < Ｏ(n^3) <Ｏ(2^n) < Ｏ(n!) < Ｏ(n^n)
- 在本文中所涉及的算法最终都以加权平均时间复杂度来计算。
-
空间复杂度
额外的内存开销可以分为两种- 除了函数调用所需要的栈以及固定数目的实例变量之外无需额外内存的原地排序算法
- 需要额外内存空间来存储另一份数组副本的非原地排序算法
-
稳定性
- 待排序的关键字各不相同时，排序的结构是唯一的，否则排序的结果不一定唯一
- 如果待排序的表中，存在多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，这种排序方式是稳定的
- 如果相对次序会发生变化，则称为这种排序方式是不稳定的
- 简单解释，就是两个相同的元素是否会发生交换
1、插入排序
插入排序的基本思想是：每次将一个待排序的元素，按其关键字大小插入到已经排好序的子表中的适当位置，直到全部元素插入完成为止，也就是在插入的过程中进行排序。总共有三种，直接插入排序，折半插入排序，希尔排序，本文只分析直接插入排序和希尔排序
1、直接插入排序
核心思想：
- 将字符串分为有序区和无序区，从无序区取出元素插入到有序区
- 在插入时需要进行比较以查找适合的位置
实现思路：
1、先有一层循环，用来在无序区取出一个个元素，每趟取出无序区的第一个元素
2、再有一层循环，用来在有序区中从后往前比较，遇到大于该元素的就往后移动，一直到不大于就将该元素放进去
代码：
//插入排序
/*
1、第一轮，拿到无序区的第一个数据
2、第二轮：在有序区中从后往前比较，将所有大于tmp的元素都向后挪，一直到不大于的时候就将tmp放入当前位置
*/
/*
这里需要注意的是：
并不是先一个个比较得到所在位置，再去移动该位置之后的其他数据
而是直接从后往前比较每一个数据，只要大于的就往后移动
*/
void insertSort(NSMutableArray *arr,int n){
int i,j;
NSString *tmp;
for (i=1; i<n; i++) {//遍历无序区，所以从下标1开始
tmp = arr[i];
j=i-1;//先拿到有序区的最后一个，j最大值是无序区的前一个
//不断遍历，将所有大于tmp的值都挪到后面
while (j>=0 && [tmp intValue] < [arr[j] intValue]) {
arr[j+1] = arr[j];
j--;
}
//插入到当前位置
arr[j+1] =tmp;
}
NSLog(@"insertSort:%@",arr);
}
算法分析：
时间复杂度：容易看出有两层循环，所以平均时间复杂度为O(n^2)
空间复杂度：容易看出为O(1),使用了三个辅助变量，都与问题规模n无关，所以空间复杂度为O(1)
稳定性： 是一种稳定的排序，当拿到一个元素在有序区中不断从后往前比较时，如果遇到相等的元素是不会向后挪的，所以相对位置是不会变的。
重要性质：
1、运行时间与输入有关，如果输入的元素趋向正序的，则效率越高，输入的元素趋向逆序的，效率越低
2、因此如果倒置的数量很少时，插入排序和可能比其他所有算法的效率都要高（基于这一点，就出现了希尔排序）
3、插入排序对部分有序的数组十分高效，也很适合小规模数组，因为这样就可以避免大量数据的移动
2、希尔排序
认识：
在直接插入排序基础上进行改良，基于直接插入排序的性质，即越趋向于正序，效率越高，就出现了希尔排序。
希尔排序又称为缩小增量排序法，通过缩小增量，可以使得元素的排序不停的趋向于正序，以此来提高效率。
疑问：
可是这样会进行多轮排序呀，而且刚开始排序的时候倒序的数量还是不变和直接插入的倒序数量是一样的，并且最后一轮排序也是会将所有的元素整体进行排序。为什么可以提高效率呢？
解答：
1、这是因为刚开始虽然倒序的数量还是那么多，但是排序的增量很大，一次性排的数量很少，所以会提高效率
2、虽然最后一次排序也是对所有元素整体排序，但是此时已经基本趋向于正序了，所以效率很高。
核心思想：
1. 对所有元素进行分组，每趟只排序分组后的元素，对于每组元素通过直接插入排序方式
2. 一次排序完，会再一次进行分组
3. 各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止
4. 各趟比较所用的距离就是增量
4.1. 增量的意思是在从当前位置计算下一个位置需要增加的量，也就是待排序的元素的间隔。
4.2. 在直接插入排序中，元素间隔为1（不按照0来算，因为我所指的间隔是指从这个元素跳到下一个元素需要+1）
4.3. 在希尔排序中，元素间隔为一个增量，也就是从这个元素跳到下一个元素需要+gap
5. 这里涉及到增量的计算，此处采用希尔推荐的初始增量为gap = length/2，缩小增量为gap=gap/2的方式
实现思路：
1. 获取到初始增量
2. 直接插入排序，此处就和普通的直接插入排序一样，只是增量从1变为了gap
3. 缩小增量
代码：
/*
1、获取到初始增量
2、直接插入排序
3、缩小增量
*/
/*
1、增量的意思是在从当前位置计算下一个位置需要增加的量，也就是待排序的元素的间隔。
2、在直接插入排序中，元素间隔为1（不按照0来算，因为我所指的间隔是从这个元素跳到下一个元素需要+1）
3、在希尔排序中，元素间隔为一个增量，也就是从这个元素跳到下一个元素需要+gap
*/
void ShellSort(NSMutableArray *arr,int n){
int i,j,gap;
NSString *tmp;
gap = n/2;//初始增量
while (gap > 0) {//不断缩小增量，直到增量为1，此时1/2 = 0，便不再进入.增量为1就和普通的直接插入排序一样了
//对每组都进行直接插入排序，相距的间隔为gap，其他的都一样
for (i = gap; i<n; i++) {
tmp = arr[i];
j = i-gap;
while (j >= 0 && [tmp intValue] < [arr[j] intValue]) {
arr[j+gap] = arr[j];
j = j-gap;
}
arr[j+gap] = tmp;
}
//缩小增量
gap = gap/2;
}
NSLog(@"binaryInsertSort:%@",arr);
}
图示：
为了更形象的理解，下面以数组[7,6,9,3,1,5,2,4]来进行举例演示
第一趟：
初始增量为gap = length/2 = 4，增量为4，也就是总共有4组，每组为2个元素
第二趟：
第二轮再次计算gap = gap/2 = 2，增量为2，说明分为两组，每组就是4个元素，每组的元素进行直接插入排序
第三趟：
第三轮再次计算gap = gap/2 = 2/2 = 1。增量为1，也就是只有1组了，全部元素进行排序
插入排序
与直接插入排序的比较
- 直接插入排序的增量为1，也就是从上一个元素+1，跳到下一个待比较的元素
- 希尔排序的增量不断变化，一方面需要不断计算增量值gap，一方面从上一个元素+gap，跳到下一个待比较的元素
算法分析：
时间复杂度： O(n^(1.3))
空间复杂度：只有四个临时变量，与问题规模n无关，所以是O(1)
稳定性：稳定，和直接插入排序一样
重要性质：
1、它的高效在于权衡了数组的规模和有序性，排序之初，各个子数组都很短，排序之后子数组都是部分有序的，子数组很短和部分有序两种情况都很适合插入排序
2、适用于中等规模
3、可以看到在直接插入排序算法中，如果已经是正序，那么时间复杂度就为O(n),如果是反序就为O(n^2)，所以希尔排序就是通过多轮排序会不断的将其修正为正序。
4、没有时间复杂度为n(logn)的快速排序算法快，因此对于中等规模大小的表现比较好，对规模非常大的数据排序不是最优选择
5、但是要比直接插入排序，冒泡排序等O(n^2)的算法要好
6、增量序列的选择十分重要，直接影响到了希尔排序的性能，上面所选择的是希尔建议的增量
7、希尔排序的每趟并不产生有序区，在最后一趟结束前，所有元素不一定归位，但是每趟排序完成后，数据越来越接近有序
2、交换排序
交换排序的基本思想：两两比较待排序元素的关键字，发现两个元素的次序相反时即进行交换，直到没有反序的元素为止。包含冒泡排序、快速排序。
1、冒泡排序
认识
下边的元素依次通过两两比较，每次比较都把更大的元素放在上面，这样上边的元素越来越大，最后最大的元素就到达顶端。就像是水里的泡泡往上冒一样，随着水压的减小，越往上泡泡越大，这就是所谓的冒泡。
核心思想
相邻字符两两比较，较大的挪到后面
实现思路
- 第一层循环依次取出所有的元素
- 第二层循环取出当前所选元素的后边元素并进行比较大小，较大的放在后边，较小的放在前边
代码实现
/*
可以看做是下边的元素不断往上走，元素越来越大，最后最大的元素放到顶端，就像是水里的泡泡往上冒一样，随着水压的减小，越往上泡泡越大，这就是所谓的冒泡
1、第一个for循环依次取出所有的元素
2、第二个for循环依次取出当前所选元素的后边元素并进行比较大小
3、较大的放在后边，较小的放在前边
*/
void BubbleSort1(NSMutableArray *arr,int n){
int i,j;
NSString *tmp;
for (i=0;i<n-1; i++) {//一趟遍历就是一个元素的归位
for (j = 0; j<n-i-1; j++) {//每次将最后一个元素归位，所以这里是j<n-i-1,而不是j<n-1
if ([arr[j] intValue] > [arr[j+1] intValue]) {//如果下边的元素较大，就进行交换，往上冒一下
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
NSLog(@"BubbleSort1:%@",arr);
}
算法分析
时间复杂度：显然有两层for循环，所以时间复杂度为O(n^2)
空间复杂度：i、j、tmp与问题规模n无关，所以是O(1)
稳定性：是稳定的排序方式，很明显，如果两两比较发现相等，就不进行交换
冒泡优化：
问题：当经过某一趟的排序，已经不再发生交换，也就是已经完全有序了，但是第一层的循环仍然会不停的执行。
优化思想：如果有一轮没有发生任何交换，说明已经排好序了，此时应该退出排序
实现思路：在原来代码的基础上增加一个bool判断，如果这一趟比较没有一次交换，就说明已经排好序了，就直接停止排序
代码后代码:
//优化后的冒泡排序
/*
在原来的基础上增加一个bool判断，如果这一趟比较没有一次交换，就说明已经排好序了，就直接停止排序
*/
void bubbleSort_better(NSMutableArray *arr,int n){
int i,j;
bool exchange;
NSString *tmp;
for (i = 0; i<n-1; i++) {
exchange = false;
for (j = 0; j<n-i-1; j++) {//每次将最后一个元素归位，所以这里是j<n-i-1,而不是j<n-1
if ([arr[j] intValue] > [arr[j+1] intValue]) {//如果下边的元素较大，就进行交换，往上冒一下
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
exchange = true;
}
}
if (!exchange) {
NSLog(@"bubbleSort_better:%@",arr);
return;
}
}
}
其他演化版本
为了更符合冒泡的这个说法，我采用了从下往上比较，而且得到结果为顶部为最大，底部最小。其实只要是上下两两比较，也可以从上到下比较，结果也可以是顶部最小，底部最大。简单演示一下
简单代码案例
oid BubbleSort(NSMutableArray *arr,int n){
int i,j;
NSString *tmp;
for (i=0;i<n-1; i++) {//一趟遍历就是一个元素的归位
for (j=n-1; j>i; j--) {//采用从顶到底的比较，比较出最小的元素
if ([arr[j] intValue] < [arr[j-1] intValue]) {//如果后边的元素较小，就进行交换
tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
}
NSLog(@"BubbleSort:%@",arr);
}
重要性质
1、每趟产生的有序区中的元素都是归位，不会发生改变了
2、重点在于相邻元素两两比较。
2、快速排序
认识
快速排序采用分治思想的递归算法来实现，一次只能将一个元素归位，所以需要采用递归将所有的元素归位。
核心思想
- 每次递归取出第一个元素作为基准，将其他元素与其作比较，较大的放左边，较小的放右边
- 一次递归就可以将这个元素进行归位,并且将整个要排序的数据划分成两部分
- 后面再针对所有划分出来的两部分递归重复进行上述过程，就可以将每部分元素归位，此处就是递归实现
实现思路
- 以第一个元素作为基准tmp
- 从右到左扫描，找到小于tmp的值，放到左区间的空位置
- 从左到右扫描，找到大于tmp的值，放到右区间的空位置
代码
//快速排序
/*
1、以第一个元素作为基准tmp
2、从右到左扫描，找到小于tmp的值，放到左区间的空位置（第一次的空位置是第一个位置，这是没问题的，因为已经赋给tmp了）
3、从左到右扫描，找到大于tmp的值，放到右区间的空位置（此时右区间肯定会有空位置，否则i=j了，就不会执行从左到右扫描了）
*/
/*
实现细节：
1、一次只能将一个元素归位，采用递归可以将所有的元素归位
2、一个元素的归位需要将当前区间的所有元素都进行比较，从右到左和从左到右交替扫描，一直到i=j
3、如果在右区间进行交换，直接将左区间的第一个元素进行覆盖，这是没问题的，因为已经赋给tmp了
4、如果右区间没有进行交换，左区间交换的元素往哪里放呢，此时i=j了，是不会进行从左到右扫描的
5、在交换的过程中，始终有一个位置是留给tmp的，初始是在arr[0]上，之后进行交换时，交换出去的那个位置就是留给tmp的
6、当i=j时，此时的i或j的位置就是tmp的位置，因为此时肯定是上一次交换之后剩下的位置
*/
void quickSort(NSMutableArray *arr,int s,int t){
int i = s, j = t;
NSString *tmp;
if (s<t) {//区间内至少存在两个元素
tmp = arr[s];//以第一个元素作为基准
while (i!=j) {//从区间两端交替向中间扫描，直至i=j为止
while (j>i && [arr[j] intValue]>=[tmp intValue]) {
j--;//从右到左扫描，找到第一个小于tmp的值
}
//这里也一样，加判断i != j
arr[i] = arr[j];//进行交换
while (i<j && [arr[i] intValue] <= [tmp intValue]) {
i++;//从左到右扫描，找到第一个大于tmp的值
}
//这里可以加一个判断优化一下，只有当i != j的时候才进行交换了。i==j交换也没啥用，只不过影响微不足道
arr[j] = arr[i];//进行交换
}
arr[i] = tmp;//元素归为
quickSort(arr, s,i-1);//左区间递归
quickSort(arr, i+1,t);//右区间递归
}
}
空位置思想
为便于理解，我这里采用空位置思想来解读，看代码时可以结合这里思考
- 取出基准元素，该位置就是空位置
- 在交换的过程中，始终有一个位置是空位置，供最后tmp赋值
- 在判断当前位置大于或小于tmp时，将当前位置的元素赋出去，当前位置就是空位置了
- 当i==j时，此时的i/j的位置就是最终的空位置，就将tmp放到这里
疑问1：
问：可能会有人问在第2步中第一次放的时候没有空位置，放到哪都会将原来的数据覆盖掉，往哪里放呢？
答：第一次的左区间空位置是第一个位置，这是没问题的，不用怕覆盖掉，因为已经赋给tmp。所以就将第一个位置作为初始的空位置疑问2：
问：可能有人会问，第3步中此时右区间如果没有空位置咋办，往哪里放呢？
答：如果右区间没有空位置，代码已经是i=j了，此时就不会执行从左到右的扫描，也不会知道大于tmp的值了。也就是说如果找到了大于tmp的值，右区间肯定会有空位置的。否则就找不到大于tmp的值
实现细节思考
一次只能将一个元素归位，采用递归可以将所有的元素归位
一个元素的归位需要将当前区间的所有元素都进行比较，从右到左和从左到右交替扫描，一直到i=j
如果右区间没有进行交换，左区间交换的元素往哪里放呢，此时i=j了，是不会进行从左到右扫描的
-
空位置的使用
4.1. 开始的空位置- 开始的空位置是第一个元素,空位置为arr[i],i==0.
- 所以当右区间进行交换，直接将左区间的第一个元素进行覆盖
4.2. 交换中的空位置
- 左区间的某个位置的元素赋值到右区间的空位置，此时该位置就是空位置,空位置为arr[i]
- 右区间的某个位置的元素赋值到左区间的空位置，此时该位置就是空位置,空位置为arr[j]
- 也正因为这样不断交换空位置，就需要左右区间交替扫描
4.3. 最终的空位置
- 当i==j时说明左区间+右区间所有的元素都比较完了，此时剩下的这个位置就是空位置
- 所以最终的空位置就是arr[i]或arr[j]
图示
为了更形象的看到元素的交换过程，以及空位置的转换，下面以数组[3 6 1 4 7 2 5]为例讲解，看代码时可以结合下面图示分析
算法分析
时间复杂度：平均时间复杂度是O(nlgn)
空间复杂度：是O(1)，因为i，j,tmp三个临时变量均与问题规模n无关
稳定性：不稳定
优点
- 原地排序，只需要很小的辅助栈
- 长度为N的数组排序所需的时间和nlgn成正比，也就是说算法实现时间与输入序列无关
重要性质
使用的最广泛的排序算法
实现简单，适用于各种不同的输入数据，且在一般应用中比其他排序算法都要快得多。
3、选择排序
选择排序的核心思想： 每一趟从待排序的元素中选出关键字最小的元素，顺序放在已排好序的子表的最后，也就是从无序区中选出最小的放到有序区中。
2、选择排序
认识
不断地选择剩余元素之中的最小者，并附到有序区中的末尾，这是最简单的排序算法。
核心思想
- 分为有序区和无序区，
- 在无序区中选出最小的元素，将它与无序区中的第一个元素R[i]进行交换
- 这样这个R[i]从无序区进入到了有序区，并且这个元素插入到有序区中排好了顺序，而i位置所在原来的元素仍然在无序区中
实现思路
- 第一层循环是表示第几趟排序，也就是需要得到第几小的元素
- 第二层循环是在无序区中得到最小的元素，通过无序区中的第一个元素向后面不停的比较，遇到较小者就将下标存入到临时k值中
- 判断取出的最小元素不是无序区的第一个元素，就进行交换
简单说明：
- 首先，找到数组中最小的元素，与数组中对第一个元素进行交换位置
- 其次，在剩下的元素中找到最小的元素，与数组中第二个元素进行交换位置
- 如此往复，就可以对整个数组排好序
代码
//选择排序
/*
1、循环给所有的元素进行排序
2、得到无序区中的最小值
3、与本趟待排序元素进行交换
*/
void selectSort(NSMutableArray *arr,int n){
int i,j,k;//k作为最小元素的下标临时值
NSString *tmp;
//对第几个数进行排序
for (i=0; i<n-1; i++) {
k = i;//将当前需要比较的数元素下标拿出来
//对无序区进行比较
for (j = i+1; j<n; j++) {
//如果
if ([arr[j] intValue] < [arr[k] intValue]) {
k = j;
}
}
//将当前的i的值与无序区中取出的最小元素进行交换
if (k!=i) {
tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
}
}
NSLog(@"selectSort:%@",arr);
}
算法分析
时间复杂度：明显看出有两层for循环，因此是O(n^2)
空间复杂度：因为创建的临时变量与问题规模无关，代码上很容易看出是O(1)
稳定性：是不稳定排序。
1、无序区中的元素总是在变化的
2、 因为在无序区中找到的最小元素会与第一个元素进行交换，所以位置会发生变化
3、比如待排序序列为{5,3,2,5,4,1},这里有两个5，第一趟排序时，选择出最小关键字1，与第一个位置的5进行交换，交换完之后的序列为{1,3,2,5,4,5}。这样两个5的相对位置发生了变化
重要性质
- 每趟比较都会让一个元素在全局归位
- 运行时间与输入无关
- 在找出最小元素而扫描一次数组之后并不能为下一次扫描提供什么信息
- 也就是说不能依据输入的元素的状态而改变运行效率,针对正序和反序两种情况其运行时间是一样的,这样是不好的，因为在实际使用中可能其对象更偏向于正序或偏向于反序，这样无法起到更好的效果
- 也不能依据输入元素的数量而改变运行效率,注意这里我说的是效率，而不是时间,这么说是因为有的排序算法在较小规模的数据下排序效率并不高，但是在较大规模的数据下效率反而会明显提高。有的排序算法刚好相反。但是选择排序并不会改变
- 数据移动是最少的
- 每次交换都会改变两个数据元素的值，
- 因此只需要N次交换，其他的元素不会跟着移动，比如冒泡排序，会比较和移动一系列数据，其实我们研究的其他任何算法都不具备这一点。
2、堆排序
认识
堆排序是一种树形选择排序方法，排序过程与直接选择排序类似，只是挑选最大或最小元素的方式不同，堆排序通过将数组看做是一个完全二叉树的顺序存储结构，利用完全二叉树中的双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素
堆可以分为大根堆和小根堆
大根堆： 双亲节点大于左右孩子节点，根节点的值最大
小根堆： 双亲节点小于左右孩子节点，根节点的值最小
核心思想
1、构建一个大根堆，通过大根堆的定义可知，此时根节点是最大的
2、构造堆需要从下往上遍历双亲节点，这样下面的节点先排好序，也就是使其双亲结点都比孩子节点大，再往上比较。一直到最大的根节点
3、取出根节点的值与无序区中的最后一个值进行交换，这个值也就进入有序区（因为是大根堆，且本文均是升序排序，因此此时无序区在数组的后端）
4、交换后的堆移除有序部分，再次构造大根堆，也就是找出无序区中的最大值，再次与无序区中的最后一个值进行交换
简单说：
1、交换过程与直接选择排序一样，选出最大值后与无序区的最后一个值进行交换，使其进入有序区
2、重点在于选择最大值是通过构建大根堆来实现的，大根堆的实现是依据完全二叉树中的双亲节点和孩子节点之间的内在关系得出的。
实现思路
直接看代码注释
代码
//堆排序
/*
通过筛选算法构建堆
1、左右孩子节点比较较大者
2、左右孩子节点的较大者与双亲节点比较较大者
3、如果双亲节点较大，就不做处理，如果孩子节点较大，
因为当前的双亲节点+左右孩子节点的基本结构修改后，可能会破坏下一级的堆，所以需要不断的向下筛选，一直到high
*/
//low表示需要筛选的点，high表示需要筛选的节点数量
void sift(NSMutableArray *arr,int low,int high){
int i = low,j = 2 * i;//arr[j]是arr[i]的左孩子，arr[j+1]是arr[i]的右孩子
NSString *tmp = arr[i];
//high表示最大的节点位置
while (j <= high) {
//左右孩子节点比较较大者
if (j < high && [arr[j] intValue] < [arr[j+1] intValue]) {//若左孩子<右孩子，把j指向右孩子
j++;
}
//左右孩子节点的较大者与双亲节点比较
/*
做了两件事
1)交换双亲结点与左(右)节点位置
2)修改i和j值，以便继续向下筛选
*/
if ([tmp intValue] < [arr[j] intValue]) {
//将arr[j]调整到双亲节点位置上
arr[i] = arr[j];
//修改i和j值，以便继续向下筛选
i = j;
j = 2 * i;
} else {
break;//筛选结束
}
}
//也就是找到了最终的位置，此时把它放进去
arr[i] = tmp;//被筛选节点的值放入最终位置
}
/*
1、创建初始堆
2、堆顶最大值与最后一个元素交换
3、筛选剩下的节点
*/
void HeapSort(NSMutableArray *arr,int n){
int i;
NSString *tmp;
//循环建立初始堆
/*
i表示根节点，i取值范围为1~n/2，1很好理解，就是第一个根节点，n/2是因为完全二叉树的特性，根节点总数为n/2
所以这里就是取出每个根节点，并且循环进行构造。
最基本的构造：双亲结点与左右孩子节点进行比较，较大者作为双亲节点
循环最基本的构造来实现所有的节点的比较。
*/
//倒序排序，也就是先从最后一个非叶子节点排序，
for (i = n/2; i >= 1; i--) {
sift(arr,i,n);
}
/*
1、每趟获取到最后一个节点，为什么是i>=2呢，这是因为当只有一个元素时就不需要比较了，所以比较的是n-1趟，也就是[n,2]
2、将当前根节点与第一个元素进行交换
3、再次构建堆
*/
for (i = n; i >= 2; i--) {//进行n-1趟堆排序，每一趟堆排序的元素个数减1
tmp = arr[1];//将最后一个元素同当前区间内arr[1]对换
arr[1] = arr[i];
arr[i] = tmp;
sift(arr, 1, i-1);//筛选arr[1]节点，得到i-1个节点的堆
}
NSLog(@"HeapSort:%@",arr);
}
算法分析
时间复杂度：O(nlgn)
空间复杂度：O(1)
稳定性：不稳定排序
重要性质
1、构造大根堆的过程是找到最大值放到跟节点
2、构造堆需要从下往上遍历双亲节点
4、归并排序
认识
归并排序是建立在归并操作上的一种有效、稳定的排序算法，用到了分治思想。
核心思想
- 将整个序列分成多个子序列
- 先使每个子序列有序，再将多个序列表合并成一个有序序列表
- 一直到最终合并成完整的列表
实现思路
- 分解整个数组为多个子序列，不停分解，直到每个子序列为1个元素
- 将分解的所有子序列进行归并
- 初始子序列长度为1，之后循环增加子序列长度，每次子序列长度翻倍
代码
注释已足够详细，不再赘言
///归并排序
//先使每个子序列有序，再使子序列段间有序，再将多个序列表合并成一个有序序列表
/*
一次归并
1、将数组中的一组数据进行排序，通过low和high分割区间作为一个待排序的无序列表，
2、使用mid将待比较区间分成左右区间两部分。
3、将两个子序列合并成一个有序序列，通过一个临时数组接收
4、将有序的临时数组存储到无序的待排序数组中
*/
//注：通过mid，将数组待比较部分分成两部分，low-mid和mid-high
void merge(NSMutableArray *arr,int low,int mid,int high){
//i用来对左区间进行比较，j对右区间进行比较，k用来对临时数组的数据进行处理
int i = low,j = mid+1,k=0;
NSMutableArray *arr2 = [[NSMutableArray alloc] initWithCapacity:1];
while (i <= mid && j <= high) {
if ([arr[i] intValue] <= [arr[j] intValue]) {
arr2[k] = arr[i];
i++;k++;
} else {
arr2[k] = arr[j];
j++;k++;
}
}
while (i <= mid) {
arr2[k] = arr[i];
i++;k++;
}
while (j <= high) {
arr2[k] = arr[j];
j++;k++;
}
//再全部赋给arr
for (k=0,i=low;i <= high ; k++,i++) {
arr[i] = arr2[k];
}
}
/*
对整个表进行一趟归并
当前表中的所有子序列进行归并
通过子序列的长度来获取子序列
*/
void MergePass(NSMutableArray *arr,int length,int n){
int i;
//归并length长的两相邻子序列
for (i=0; i+2*length-1<n; i=i+2*length) {
merge(arr, i, i+length-1, i+2*length-1);
}
//最后一个子序列的长度小于length，需要特殊处理
if (i+length-1<n) {
merge(arr,i,i+length-1,n-1);//归并这两个子表
}
}
/*
对整个表分成多个子序列，初始子序列长度为1，后续每次加倍，之后调用归并函数进行归并
故会进行lgn趟归并
*/
void mergeSort2(NSMutableArray *arr,int n){
int length;
//每次归并的序列端长度从1起始，每次加倍
for (length = 1; length<n; length = 2*length) {//进行lgn趟归并
MergePass(arr, length, n);
}
NSLog(@"mergeSort2:%@",arr);
}
为了更好的理解归并操作，可以看这个算法，该算法使用数组保存子序列，并且在合并时也效率不高，但是简单易懂，可以借此理解分治思想
//归并排序
/*
1、循环两个数组的每个元素，分别添加到接收数组中
2、有三种情况，都没遍历完，遍历完数组1，遍历完数组2
3、都没遍历完情况下，需要比较两个数组对应元素的大小，小的先存入，大的后存入（升序排序）
*/
//合并两个数组
NSArray* mergeArrayFirstList(NSArray *array1 ,NSArray *array2) {
NSMutableArray *resultArray = [NSMutableArray array];
NSInteger firstIndex = 0, secondIndex = 0;
//可以看出一轮只能往接收数组中存入一个元素
while (firstIndex < array1.count && secondIndex < array2.count) {
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
return resultArray.copy;
}
/*
1、拆分数组，拆分的所有数组只有一个元素
2、合并数组，所有的数组两两合并，将合并的数组保存下来再与其他的数组合并，一直到只有一个数组
*/
//注：这里会把拆分的所有数组放到一个数组中，是为了更好的对这些数组进行归并操作
void megerSortAscendingOrderSort(NSMutableArray *ascendingArr)
{
//tempArray数组里存放ascendingArr个数组，每个数组包含一个元素
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSString *num in ascendingArr) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
//开始合并为一个数组
while (tempArray.count != 1) {
NSInteger i = 0;
while (i < tempArray.count - 1) {
//将后两个归并成一个数组，并保存到倒数第二个位置
tempArray[i] = mergeArrayFirstList(tempArray[i], tempArray[i + 1]);
//最后一个元素删掉
[tempArray removeObjectAtIndex:i + 1];
i++;
}
}
NSLog(@"归并升序排序结果：%@", tempArray[0]);
}
算法分析
时间复杂度：需要log(n)轮归并排序，因此复杂度为O(nlogn)
空间复杂度：需要和待排序记录个数相等的存储空间，所以复杂度为O(n)
稳定性：稳定
重要性质
- 适用于数据量大，并且对稳定性有要求的场景
- 对于小规模数据并不好，还不如使用插入排序，只有在大数据量的情况下才有明显的效果
5、各排序算法的比较
整体比较
选择排序和插入排序的比较
- 插入排序不会遍历有序区的元素，而是遍历无序区；选择排序不会遍历无序区的元素，而是遍历有序区的元素
- 插入排序的执行效率与输入元素状态有关，越偏向于有序，效率越高，最高为O(n)；选择排序的效率与输入元素状态无关，不管多少数据都是O(n^2)
- 插入排序适合部分有序的数组，也适合小规模数组；选择排序只能适合小规模数组
- 插入排序是稳定的，因为相对位置不会发生变化；选择排序是不稳定的，因为交换后相同关键字的元素可能会发生变化
- 插入排序花费时间更多在于交换，在插入时，需要将该位置后的其他元素都移动一位；选择排序花费时间更多在于比较，比较后得出最小元素直接进行一次交换就可以
插入排序和希尔排序的比较
- 希尔排序对于任意排序的数组也很高效；插入排序只在部分有序的情况下比较高效
- 希尔排序在插入排序的基础上进行了缩小增量法来实现，进行多轮插入排序，每轮只排序一部分数据，且最后一轮只有一组，这一组为所有数据；插入排序只进行一轮插入排序
- 数组越大，顺序越乱，希尔排序的优势越明显
选择排序和冒泡排序的比较
- 选择排序是选择一个元素之后跟无序区所有元素进行比较，最终进行交换；冒泡排序只有两两比较，比较一次就交换一次
归并排序和快速排序的比较
- 归并排序采用分治思想的递归算法实现；快速排序也采用分治思想的递归算法实现
- 归并排序将一个大数组平均分成两个小数组，小数组再平均分；快速排序通过第一个元素与其他元素比较，较小的作为一个数组放在左边，较大的作为一个数组放在右边
