目录
前言
快速排序
相遇位置一定比key小的原理（大）：
避免效率降低方法（快排优化）
三数取中（选key优化）
小区间优化
hoare版本快排
挖坑法快排
前后指针快排
非递归快排
归并排序
非递归归并
总结：编辑
前言
本篇讲解上一篇没有讲解的快速排序和归并排序；
上篇排序：常见排序算法-****博客
本期专栏：算法_海盗猫鸥的博客-****博客
个人主页：海盗猫鸥-****博客
这两种排序思想较为复杂，和堆排序、希尔排序，都为效率较高的排序算法；且快排和归并都分为递归和非递归两种实现方法。
快速排序
hoare方法原理解析：升序
图中循环开始时L指向比较区间的最左，R指向比较区间的最右位置
1. 假设确定最左的数为key值
2. 则R--寻找小于key的值；L++寻找大于key的值；找到后交换R和L所指向位置的值
3. 如此循环下去，直到R等于L，循环结束，将key值和相遇位置（一定小于key）的值进行交换，并将key指向相遇位置
4.完成一次循环之后，小于key的值都在此时key位置的左边，大于key的值都在key位置右边
5.将此时的key位置作为分界点，分为左右俩区间进行递归
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//以key为基准
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
//先找小，后找大，能保证begin和end相遇位置的数据一定小于keyi位置的数据
//右边找小
while (begin < end && arr[end] >= arr[keyi])
{
end--;
}
//左边找大
while (begin < end && arr[begin] <= arr[keyi])
{
begin++;
}
Swap(&arr[begin], &arr[end]);
}
//
Swap(&arr[keyi], &arr[begin]);
keyi = begin;
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
相遇位置一定比key小的原理（大）：
升序：
left做key，保证R先走，就能保证相遇位置一定小于key（相对的，right做key时，就要让L先走，保证相遇位置比key大）
降序排列时则相反
因为在上一次交换中，L与R交换值，L所指向的位置就一定已经是小于key的值了，此时到下一个循环，R先再往前走L还没有动，所以当R遇到L时就一定是上一轮交换过来的，小于key的值，所以相遇位置一定小于key；
反之如果先让L先走，那么相遇位置就一定是上一轮交换完成后，大于key的值所在的位置，也就是上一轮R所在位置，一定大于key值
当前版本的快排，当数据本身就有序时，快排的时间复杂度将会退化为N^2；
并且有栈溢出的风险，递归深度太深将导致栈溢出，因为函数栈帧空间较小
当每次的key越接近中间位置时，快排的时间复杂度约为O(N*logN):；
避免效率降低方法（快排优化）
三数取中（选key优化）
想办法使key的值更接近中间，
使用随机值赋值key（可以避免效率降低到O(N^2)，但随机性任然较大）；
三数取中
将排序区间的left，right和位于最中间的数比较；取大小居中的那个数作为key值；但为保证后续排序逻辑不变，要将key值和最左left位置上的值进行交换
小区间优化
假设每次key都比较接近中间位置，那么每次区间分割都可以大致看为二分，则其递归的形式就形似二叉树，效率最高；但当数据个数较少时，使用递归来排序是不太合适的
所以当区间数据个数较少时，我们可以直接使用插入排序
hoare版本快排
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中
int GetMidi(int* arr, int left, int right)
{
//返回三个数中值最小的下标
int midi = (left + right) / 2;
if (arr[left] > arr[midi])
{
if (arr[midi] > arr[right])
return midi;
else if (arr[left] > arr[right])
return right;
else
return left;
}
else//arr[left] < arr[midi]
{
if (arr[midi] < arr[right])
return midi;
else if (arr[left] < arr[right])
return right;
else
return left;
}
}
//hoare
O(N*logN)
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//小区间优化，不再采取递归的方式
if ((right - left + 1) < 10)
{
//传递区间的起始地址arr + left
InsertSort(arr + left, right - left + 1);
}
else
{
//以key为基准
//固定以left为key时，当数组倒序时，将导致时间复杂度退化为O(N^2);
//int keyi = left;
//三数取中
int midi = GetMidi(arr, left, right);
Swap(&arr[left], &arr[midi]);//将要作为key的值交换到最左边
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
//先找小，后找大，能保证begin和end相遇位置的数据一定小于keyi位置的数据
//右边找小
while (begin < end && arr[end] >= arr[keyi])
{
end--;
}
//左边找大
while (begin < end && arr[begin] <= arr[keyi])
{
begin++;
}
Swap(&arr[begin], &arr[end]);
}
//
Swap(&arr[keyi], &arr[begin]);
keyi = begin;
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
}
挖坑法快排
原理解析：（升序）
1. 将最左位置视为初始坑位，并将其值赋值给key存储起来，L指向最左边（此时L所指就是坑位），R指向最右位置；
2. R开始从右往左找小于key的值，找到后，将这个位置的值赋值给坑位，并将这个位置视为新的坑位；
3. 接着L从左往右找大于key的值，找到后，将这个位置的值赋值给坑位，并将这个位置视为新的坑位。
4. 直到L和R相遇（同时指向坑位），将key值赋值给坑位。此时小于key的值就都在坑位前，大于key‘的值都在坑位后
5. 以最后的坑位为分界，左右区间递归
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//将第一个数据视为坑；
int keni = left;
int key = arr[keni];
int begin = left;
int end = right;
while (begin < end)
{
//找到小于key的值，填到坑中
while (begin < end && arr[end] > key)
{
end--;
}
arr[keni] = arr[end];
keni = end;
while (begin < end && arr[begin] < key)
{
begin++;
}
arr[keni] = arr[begin];
keni = begin;
}
//相遇后，将key值赋给坑的位置
arr[keni] = key;
QuickSort(arr, left, keni - 1);
QuickSort(arr, keni + 1, right);
}
前后指针快排
原理解析（升序）：
1. 以最左为key值，prev从排序区间的第一个位置开始，cur=prev+1开始
2. 当cur所指位置值小于key值时，prev++后将prev位置和cur位置的数据交换位置，然后cur++继续寻找下一个符合条件的数据；
3. cur所指位置值大于key时，直接cur++即可；不论cur所指是否满足交换条件，cur始终都要++；
（实际就是让大于key的值都放在prev和cur所指的区间之间，并将这些值通过交换一步步送到数组的右边）；
4. 直到cur超出数组范围，此时prev所指的位置，左边就全是小于key的值，右边就全是大于key的值；
5. 交换prev位置和key位置的数据，将key重新指向prev，本次循环结束
6. 然后以新key位置为分界，左右区间递归
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
//小区间优化
if ((right - left + 1) < 10)
{
//传递区间的起始地址arr + left
InsertSort(arr + left, right - left + 1);
}
else
{
//三数取中（此优化后，逻辑会改变，原理分析处为没有三数取中优化的解析）
int midi = GetMidi(arr, left, right);
Swap(&arr[left], &arr[midi]);//将要作为key的值交换到最左边
int keyi = left;
int prev = left, cur = left + 1;
//prev和cur中间都为大于key的值
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev)
Swap(&arr[prev], &arr[cur]);
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
}
非递归快排
使用栈来模拟递归的区间分解模式；
1. 循环每走一次相当于之前的一次递归；
2. 取栈顶区间，单趟排序，然后右左子区间入栈（栈后进先出）
代码：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//非递归快排
//使用栈模拟递归分区逻辑（DFS深度优先）
//使用队列模拟（BFS广度优先）
void QuickSortNonR(int* arr, int left, int right)
{
//创建栈，存入右左区间
ST st;
STInit(&st);
STPush(&st,right);
STPush(&st, left);
//一次循环就是相当于一次递归
while (!STEmpty(&st))
{
//取区间
//栈先进后出,先出的为区间左边界
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
//排序(前后指针法)
int keyi = begin;
int prev = begin, cur = begin + 1;
//prev和cur中间都为大于key的值
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev)
Swap(&arr[prev], &arr[cur]);
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//存储右左区间
if (keyi + 1 < end)//keyi + 1 < end说明还有两个数以上
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
}
快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序，上述几种在实际使用中效率差别不大
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)（递归损耗）
- 稳定性：不稳定
归并排序
原理解析（升序）：
1. 将数组从中间分为左右两个区间，
2. 如果左右区间不有序，就继续分解左右数组，直到左右区间中都只存在一个数时，左右区间就一定有序（一个单独的数据一定有序）
3. 那么如果左右区间有序，就分别从左右区间的第一个数开始比较，将左右区间中的数按照升序插入到临时数组中，完成后，临时数组中就是一个顺序结构
上文动图只显示了合并的思想，分解的思想过程是由递归过程来实现的
代码：
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
if (begin == end)
return;
//将区间从中间分为左右区间
int midi = (begin + end) / 2;
int begin1 = begin;
int end1 = midi;
int begin2 = midi + 1;
int end2 = end;
//[left,midi][midi+1,right]
_MergeSort(arr, tmp, begin1, end1);
_MergeSort(arr, tmp, begin2, end2);
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])//小的先插入tmp
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
//将没有完成插入的一边全部插入到tmp
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//排序结果
memcpy(arr+ begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MergeSort(int* arr, int n)
{
//假设左右区间都为有序
//取左右区间小的那个数插入新数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail!");
return;
}
//排序核心
_MergeSort(arr, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}
注意：区间划分问题
在进行左右分区时，不能使用[left,midi-1][midi,right]来分区
由于midi是整形相除的结果，所以存在数据丢失的情况，若一个以区间[2,3]为例，midi=2；
则此时再按照midi分区，右区间仍然为[2,3]，程序将陷入无限递归从而崩溃，而如果按照[left,midi][midi+1,right]来区分区间，则右区间为[3,3]，满足递归条件就返回了，不会导致程序出错
非递归归并
思路：
使用循环直接模拟归并合并的过程
理想数组思路图解（数据个数等于gap）
越界问题解析：
参考代码：
//归并排序非递归
void MergeSortNonR(int* arr, int n)
{
//循环模拟
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail!");
return;
}
//两组begin，end分别表示归并的左右两组
int begin1, end1;
int begin2, end2;
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += gap * 2)
{
//i为每次比较的左右两组，最左边的起始位置
begin1 = i;
end1 = i + gap - 1;
begin2 = i + gap;
end2 = i + 2 * gap - 1;
int j = i;
//printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);
if (begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])//=保证稳定性
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
//printf(" ");
while (begin1 <= end1)
tmp[j++] = arr[begin1++];
while (begin2 <= end2)
tmp[j++] = arr[begin2++];
//每归并一组左右区间，就拷贝一次
memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
//memcpy(arr, tmp, sizeof(int) * (n - 1));
gap *= 2;
//printf("\n");
}
free(tmp);
tmp = NULL;
}
归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)（额外开辟空间）
- 稳定性：稳定
总结：
排序的介绍到这里就完结啦~
欢迎大家继续关注我的博客~
