目录
秃头侠们好呀，今天咱们来聊聊
排序
本章重点
1.排序的概念及其运用
2.常见排序算法的实现
3.排序算法复杂度及稳定性分析
排序的概念及其运用
排序的概念
排序
：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性
：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序
：数据元素全部放在内存中的排序。
外部排序
：外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
排序运用
还有的等等太多地方都要使用到排序了
常见的排序算法
常见排序算法的实现
插入排序
基本思想：
把待排序的记录按其关键码值的大小逐个
插入到一个已经排好序的有序序列
中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
直接插入排序
代码实现：
void InsertSort(int* a, int n)
{
assert(a);
for (int i = 0; i < n - 1; i++)
{
int end = i;
int x = a[end + 1];
while (end>=0)
{
if (a[end] > x)
{
a[end+1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = x;
}
}
直接插入排序的特性
1、时间复杂度：O(N^2)
最坏O(N^2)— 逆序
最好O(N)—有序或接近有序
2、空间复杂度O(1)
3、稳定性：稳定
4、元素集合越接近有序，直接插入排序算法的时间效率越高
希尔排序
希尔排序法又称
缩小增量法
，是对直接插入排序思想上的优化
基本思想：
将n个待排序的元素序列，取一个小于n的整数m作为间隔，将全部的n个元素分为m个子序列，所有距离为m的元素放在同一个子序列中，在每个子序列中分别进行直接插入排序；然后，缩小间隔m，比如取m=m/2，重复划分子序列和排序；直到m==1为止（即将所有元素放在同一个序列中排序）。
希尔的想法其实就是：
1、分组预排序，想让数组接近有序，让小数（大数）快速到前面，大数（小数）快速到后面。
2、最后因为数组已经接近有序，再进行一次直接插入排序
代码实现：
void ShellSort(int* a, int n)
{
int gap = n;
while (gap>1)
{
gap /= 2;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int x = a[end + gap];
while (end>=0)
{
if (a[end] > a[end + gap])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
希尔排序的特性
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好多书中给出的希尔排序的时间复杂度都不固定。
-
时间复杂度（总结下来一般有这几种，N
logN以2为底，N
logN以3为底，约等于N^1.3) - 稳定性：不稳
选择排序
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始（末尾）位置，直到全部待排序的数据元素排完 。
直接选择排序
在元素集合选出最小的数（或最大的数），放开头（或者末尾），然后，再找次小的（或次大的）。。。
我们这里为了更高效一点，我们直接一次选两个数，最大和最小，把最小的放开头，最大的放最后。
代码实现：
void SelectSort(int* a, int n)
{
assert(a);
int begin = 0;
int end = n - 1;
while (begin<end)
{
int min = begin;
int max = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[min])
min = i;
if (a[i] > a[max])
max = i;
}
Swap(&a[begin], &a[min]);
if (begin == max) //begin==max时，最大值被换走了，修正一下max的位置
max = min;
Swap(&a[end], &a[max]);
begin++;
end--;
}
}
直接选择排序的特性
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
-
时间复杂度：O(N^2)
最好最坏都是O(N^2) - 整体而言最差的排序，因为无论什么情况下都是O(N^2)
- 稳定性：不稳定
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
需要注意的是排升序要建大堆，排降序建小堆
。
代码实现：
void AdjustDown(int* a, int n, int parent)
{
assert(a);
int child = parent*2 + 1;
while (child<n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child = child + 1;
}
if (a[child] > a[parent])
{
Swap(&a[child] , &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
for (int end = n - 1; end > 0; end--)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
}
}
堆排序的特性
- 堆排序使用堆来选数，效率就高了很多
-
时间复杂度：O(N
logN)
最好最坏都是O(N
logN) - 空间复杂度：O(1)
- 稳定性：不稳定
具体
堆排序问题详解
交换排序
基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序
第一个数和第二个数比较，第一个大于第二的话交换，然后看第二个和第三个的比较，一趟下来把最大的数放到最后面了，然后不管最后的数，再看前N-1个数。
代码实现：
void BubbleSort(int* a, int n)
{
assert(a);
int flag = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
flag = 1;
Swap(&a[j], &a[j + 1]);
}
}
if (flag == 0)
break;
}
}
冒泡排序的特性
-
时间复杂度：O(N^2)
最好是O(N)—有序
最坏是O(N^2) - 空间复杂度：O(1)
- 稳定性：稳定
快速排序
快速排序是Hoare于1962年提出的一种
二叉树结构
的交换排序方法，
基本思想
：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
我们首先来学快排的
递归
先看一下快排递归的框架
// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int*a, int left, int right)
{
if(left>=right)
return;
// 按照基准值对数组的 [left, right]区间中的元素进行划分
int keyi = partion(a, left, right);
// 划分成功后以keyi为边界形成了左右两部分 [left, keyi-1] 和 [keyi+1, right]
// 递归排[left, keyi-1]
QuickSort(a, left, keyi-1);
// 递归排[keyi+1, right]
QuickSort(a, keyi+1, right);
}
上述为快速排序递归实现的主框架，发现与
二叉树前序遍历
规则非常像，现在我们只需要完成partion部分的选key就可以了，这里介绍3种方法。
hoare版本
hoare的基本思想：
1、取最左边的做key，最左边的为L指针，右边的为R指针
2、L指针往后走，找比key大的数，R往前走，找比key小的数，找到之后将其交换
3、当L和R相遇时，让key位置数和相遇处交换，此时key左边都是小于key的，key右边都是大于key的
4、此时key的位置就是这个值该待的位置
5、之后再递归key左边的区间和key右边的区间
注意一点
：
选左边的值做key，右边先走
选右边的值做key，左边先走
至于为什么家人们可以带进去试一试就知道了
代码实现：
int Partion1(int* a, int left, int right)
{
assert(a);
int keyi = left;
while (left<right)
{
while (left < right && a[left] <= a[keyi])
left++;
while (left < right && a[right] >= a[keyi])
right--;
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
讨论一下存在的问题同时也是对快排的优化
那么怎么解决快排面对有序序列的问题？
那就是
三数取中
就是拿最左边的数，最右边的数和中间数，三者比较选出不是最大也不是最小的那个作为key，这样就解决了上述问题。
代码实现：
int GetMidIndex(int* a, int left, int right)
{
int mid = left + ((right - left) >> 1);//取中间值，这样写是怕大于int的最大值溢出
if (a[left] > a[mid])
{
if (a[right] > a[left])
return left;
else if (a[mid] > a[right])
return mid;
else
return right;
}
else
{
if (a[left] > a[right])
return left;
else if (a[right] > a[mid])
return mid;
else
return right;
}
}
挖坑法
挖坑法的基本思想
1、将最左边的值作为key，并且将该位置作为一个坑位
2、也是有两个指针L和R，R先向前走，找比key小的值，放到坑位，然后自己成为坑位
3、之后L向后走，找比key大的值，放到刚才的坑位，然后自己变成坑位
4、最后L和R相遇时，把最开始的key值放到相遇处的坑位
5、至此就把key放到它排好序该在的位置了
代码实现：
void Partion2(int* a, int left, int right)
{
assert(a);
int key = a[left];
int pivot = left;
while (left<right)
{
//右边找小，放到左边的坑位
while (left<right && a[right]>=key)
right--;
a[pivot] = a[right];
pivot = right;
//左边找大，放到右边的坑位
while (left < right && a[left] <= key)
left--;
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
双指针法（推荐）
最后一种方法是双指针法，也是最推荐的一种方法
双指针法的基本思想
1、选取最左边的作为key值
2、双指针prev和cur
3、cur往后找比key小的值
4、当找到之后，让prev++然后交换数值
5、等于cur找小往左边扔，prev把大的数往右边扔
6、当cur结束的时候，将key和prev交换
7、至此就让key到了它排好序该在的位置了
代码实现：
void Partion3(int* a, int left, int right)
{
assert(a);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur<=right)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
还有一个地方可以优化
那就是
小区间优化
现在我们已经知道快排是一种二叉树结构的交换排序法，
二叉树是递归的，
而且二叉树的最后1，2层的递归次数几乎是整个二叉树递归的次数了，
所以当递归到最后几层小区间时，我们可以不再让其使用快速排序，不让他再递归了，
而是使用插入排序
所以最终我们的快排代码实现：
int Partion3(int* a, int left, int right)
{
assert(a);
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur<=right)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int left,int right)
{
if (left >= right)
return;
if (right - left + 1 < 10)
InsertSort(a + left, right - left + 1);
else
{
int keyi = Partion3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1,right);
}
}
说完了快排的递归实现，我们知道递归函数是在栈上开辟空间的，但栈的空间很小，如果递归深度太深，很有可能造成栈溢出
（栈溢出的原因有二：递归深度太深；没有写返回出口条件）
递归相比循环，性能较差，因为之前讲过了，递归就意味着要开辟和释放很多次函数栈帧，而每次的函数栈帧的开辟和释放都是对时间和空间的消耗。只不过随着科技进步，现在的编译器的优化已经很好了（比如VS上的release版本就对函数栈帧优化了很多），所以现在的递归和循环性能差不了多少了。
快排的非递归
快排的非递归运用的是数据结构中的
栈结构
运用栈结构的后进先出，栈是malloc出来的了，所以是在堆上开辟的，优势就很明显了：
堆比栈空间大的多。
代码实现：
void QuickSortNonR(int* a, int left, int right)
{
assert(a);
ST st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin= StackTop(&st);
StackPop(&st);
int keyi = Partion3(a, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, keyi+1);
StackPush(&st, end);
}
if (begin < keyi - 1)
{
StackPush(&st, begin);
StackPush(&st, keyi-1);
}
}
}
快速排序的特性
1、快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2、时间复杂度：O(N*logN)
3、空间复杂度：O(logN)
4、稳定性：不稳定
5、快排的非递归遍历可以使用
栈
模拟二叉树的
前序遍历
来实现，也可以用
队列
模拟二叉树的
层序遍历
来实现。
6、快排的非递归没有本质上提高时间效率，时间复杂度没变，但因为没有递归，所以可以减少栈空间的开销
7、快排是基于
分治法
的一个排序算法
归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用
分治法
（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并的递归代码实现：
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
return;
int mid = (left + right) / 2;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid+1,right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
while (begin1<=end1&&begin2<=end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1<=end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
for (int j = left; j <= right; j++)
{
a[j] = tmp[j];
}
}
void MergeSort(int* a, int n)
{
assert(a);
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
归并的非递归代码实现：
void MergeSortNonR(int* a, int n)
{
assert(a);
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap<n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//核心思想：end1，begin2，end2都可能越界，
//end1,begin2都不需要修正
if (end1 >= n || begin2 >= n)
{
break;
}
//当end2越界则需要修正end2
if (end2 >= n)
{
end2 = n - 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
for (int j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
归并的非递归难点在于
边界控制
（即当数组元素数量不是2的次方数的时候）
归并排序的特性
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
-
归并排序是一种
二分
排序算法，每次都需要给N个元素排序，排序的过程需要logN，即树的高度次，所以时间复杂度：O(N
logN)
最好最坏都是O(N
logN) - 空间复杂度：O(N)
- 稳定性：稳定
计数排序（非比较排序）
基本思想：
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
这个排序的思想很巧妙：
找到这个数组里最大的数N，然后开一个N＋1的数组，下标是从0到N，然后统计这个数组里各数出现的次数，把相应的次数计数到刚才开的数组，最后再根据这个计数的数组，把数组排序。
但如果是1000，1001，1002，1200，1500这样的数列，再直接开1501个空间的话，前1000个都浪费了，所以我们优化一下，开MAX-MIN+1个空间，计数的时候，计数原元素-MIN，最后写回去的时候再加上MIN就可以了。
代码实现：
void CountSort(int* a, int n)
{
assert(a);
int max = a[0], min = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(count, 0, sizeof(int) * range);
//统计次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//根据次数排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
count = NULL;
}
计数排序的特性
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限，比如浮点数
- 可以处理负数
- 时间复杂度：O(MAX(N,range))
- 空间复杂度：O(range)
- 稳定性：不稳定
说一下稳定性存在的意义吧
稳定性：
数组中相同值在排序以后相对位置是否变化，不变就是稳定，变了就是不稳
应用：
比如考试成绩，如果两个人一样，则需要看谁先交卷，先交卷的排名在前，所以就得保证顺序的先后，这种就得用稳定排序了。
内外排序
内部排序
：数据元素全部放在内存中的排序。
外部排序
：外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
举例：
现在让你对10亿个整数排序，但我们只有1G内存，怎么排序呢？
1、首先，10亿个整数大约占4G内存，所以不能用一般的排序，因为他们都需要写到内存上才能排序。
2、我们把4G文件分为4份，四个小文件，每个文件1G；
把1G小文件的数据加载到内存，用快排，排序完再写回文件，依次把4个小文件都给排有序；
3、然后我们用文件之间的读写，用归并的方法，把两个1G的归并成一个2G的，两个2G的归并成一个4G的，则这10亿个整数就排序好了
感谢阅读，我们下期再见
如有错 欢迎提出一起交流