快排和归并

news/2024/11/21 11:17:42/

目录

前言

 快速排序

相遇位置一定比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的值更接近中间，

  1. 使用随机值赋值key（可以避免效率降低到O(N^2)，但随机性任然较大）；

  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);}}
}

快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序，上述几种在实际使用中效率差别不大
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)（递归损耗）
  4. 稳定性：不稳定

归并排序

​

原理解析（升序）：

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;
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)（额外开辟空间）
  4. 稳定性：稳定

总结：

排序的介绍到这里就完结啦~

欢迎大家继续关注我的博客~


http://www.ppmy.cn/news/1548736.html

相关文章

生信技能62 - 常用机器学习算法的R语言实现

生信技能62 - 常用机器学习算法的R语言实现

1. 加载R包和数据 # 安装R包， 是否update统一选择不更新n BiocManager::install("caret") BiocManager::install("randomForest") BiocManager::install("gbm") BiocManager::install("kernlab") BiocManager::install("glmnet…
阅读更多...
前端：JavaScript （学习笔记）【1】

前端：JavaScript （学习笔记）【1】

目录​​​​​​​ 一&#xff0c;介绍JavaScript 二&#xff0c;JavaScript的特点 1&#xff0c;脚本语言 2&#xff0c;基于对象的语言 3&#xff0c;事件驱动 4&#xff0c;简单性 5&#xff0c;安全性 6&#xff0c;跨平台性 7&#xff0c;JS 和java的区别 &…
阅读更多...
Android开发实战班 - 现代 UI 开发之 Material Design及自定义主题

Android开发实战班 - 现代 UI 开发之 Material Design及自定义主题

Material Design 是 Google 推出的一套设计语言&#xff0c;旨在为开发者提供统一的视觉和交互设计规范。Material Design 3&#xff08;简称 MD3&#xff09;是 Material Design 的最新版本&#xff0c;引入了更多现代化的设计元素和主题定制功能。本章节将介绍 Material Desi…
阅读更多...
跨平台WPF框架Avalonia教程 十一

跨平台WPF框架Avalonia教程 十一

控件类型 如果您想创建自己的控件&#xff0c;Avalonia中有三个主要的控件类型。首先要做的是选择最适合您使用场景的控件类型。 用户控件(User Controls)​ UserControl是创建控件的最简单方法。这种类型的控件最适合特定于应用程序的“视图”或“页面”。UserControl的创建…
阅读更多...
联邦学习安全聚合算法综述（论文解析）以及如何确定自己研究方向的方法

联邦学习安全聚合算法综述（论文解析）以及如何确定自己研究方向的方法

自己写相关论文的方法&#xff1a; 可以重点看看综述类论文的未来研究方向和引言中前人已经做过的内容 联邦学习安全聚合算法综述 auth:江萍 1 通讯作者 李芯蕊 1 赵晓阳 2 杭永凯 摘要 摘要&#xff1a;随着深度学习技术的发展&#xff0c;人工智能在社会的各个方面有着重要…
阅读更多...
ThreadLocal 和 Caffeine 缓存是两种不同的缓存机制，它们在用途和实现上有明显的区别

ThreadLocal 和 Caffeine 缓存是两种不同的缓存机制，它们在用途和实现上有明显的区别

ThreadLocal 和 Caffeine 缓存是两种不同的缓存机制&#xff0c;它们在用途和实现上有明显的区别&#xff1a; ThreadLocal 缓存&#xff1a; ThreadLocal 提供了线程局部变量的功能&#xff0c;每个线程可以访问自己的局部变量&#xff0c;而不会与其他线程冲突。ThreadLocal …
阅读更多...
Swift从0开始学习 对象和类 day3

Swift从0开始学习 对象和类 day3

类&#xff08;Class&#xff09; 是一种类型或模板&#xff0c;描述了对象的特征和行为。对象&#xff08;Object&#xff09; 是类的实例&#xff0c;实际的实体&#xff0c;拥有自己的数据。 新入门的教学都喜欢用“人”来举例为类&#xff0c;在这里我也用“人”吧 //&…
阅读更多...
go-zero(四) 错误处理（统一响应信息）

go-zero(四) 错误处理（统一响应信息）

go-zero 错误处理&#xff08;统一响应信息&#xff09; 在实现注册逻辑时&#xff0c;尝试重复注册可能会返回 400 状态码&#xff0c;显然不符合正常设计思维。我们希望状态码为 200&#xff0c;并在响应中返回错误信息。 一、使用第三方库 1.下载库 目前 go-zero官方的…
阅读更多...
最新文章

Copyright @ 2022~2023