快排和归并

前言

快速排序

相遇位置一定比key小的原理（大）：

避免效率降低方法（快排优化）

三数取中（选key优化）

小区间优化

hoare版本快排

挖坑法快排

前后指针快排

非递归快排

归并排序

非递归归并

总结：编辑

前言

本篇讲解上一篇没有讲解的快速排序和归并排序；

上篇排序：常见排序算法-CSDN博客

本期专栏：算法_海盗猫鸥的博客-CSDN博客

个人主页：海盗猫鸥-CSDN博客

这两种排序思想较为复杂，和堆排序、希尔排序，都为效率较高的排序算法；且快排和归并都分为递归和非递归两种实现方法。

快速排序

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;elsereturn left;}else//arr[left] < arr[midi]{if (arr[midi] < arr[right])return midi;else if (arr[left] < arr[right])return right;elsereturn left;}}//hoare
O(N*logN)
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//小区间优化，不再采取递归的方式if ((right - left + 1) < 10){//传递区间的起始地址arr + leftInsertSort(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 + leftInsertSort(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++];}}//将没有完成插入的一边全部插入到tmpwhile (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++];elsetmp[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;
}

归并排序的特性总结：