排序算法(4)之快速排序(2)

 个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

排序算法(4)之快速排序(2)

收录于专栏【数据结构初阶】
本专栏旨在分享学习数据结构学习的一点学习笔记，欢迎大家在评论区交流讨论💌

目录

前置说明

1.快速排序的优化

测试代码

1.hoare版本

2.挖坑法

3.前后指针法

1.1三数取中

1.2小区间优化

优化后的快速排序

2.快速排序的非递归实现 

完整代码:

3.总结

前置说明

大家对快排还不是很了解的可以先去看--排序算法(4)之快速排序(1)-CSDN博客

1.快速排序的优化

上章节我们说到了快排有三个版本,分别是hoare版本,挖坑法和前后指针法,现在我就分别测试一下它们的性能.

测试代码

测试链接--912. 排序数组 - 力扣（LeetCode）

1.hoare版本

代码展示:

void Swap(int* n, int* m)
{int p = *n;*n = *m;*m = p;
}
//hoare版本
void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int begin = left, end = right;while (begin < end){//右边找小while (begin < end && a[end] >= a[keyi]){end--;}//左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//[left,keyi-1] keyi [keyi+1, right]QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}int* sortArray(int* nums, int numsSize, int* returnSize) {(*returnSize) = numsSize;int* array = (int*)malloc(sizeof(int)*(*returnSize));for(int i = 0; i < numsSize; i++){array[i] = nums[i];}QuickSort1(array, 0, numsSize-1);return array;
}

结果展示: 

 发现当数据有序时,会超出时间限制....

2.挖坑法

代码展示:

//挖坑法
void QuickSort2(int* a, int left, int right) {if (left >= right)return;int key = a[left]; // 选择第一个元素作为基准值int low = left, high = right;while (low < high) {// 从右向左找到第一个小于基准值key的元素while (low < high && a[high] >= key)high--;if (low < high) {a[low] = a[high]; // 使用 a[high] 的值填充 a[low] 的坑low++;}// 从左向右找到第一个大于基准值key的元素while (low < high && a[low] <= key)low++;if (low < high) {a[high] = a[low]; // 使用 a[low] 的值填充 a[high] 的坑high--;}}a[low] = key; // 将基准值放入最终的坑中int pivot = low; // 基准值的最终位置QuickSort2(a, left, pivot - 1); // 对左子数组递归排序QuickSort2(a, pivot + 1, right); // 对右子数组递归排序
}int* sortArray(int* nums, int numsSize, int* returnSize) {(*returnSize) = numsSize;int* array = (int*)malloc(sizeof(int)*(*returnSize));for(int i = 0; i < numsSize; i++){array[i] = nums[i];}QuickSort2(array, 0, numsSize-1);return array;
}

结果展示:

 

3.前后指针法

代码展示:

// 前后指针_快速排序
void QuickSort3(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);
}int* sortArray(int* nums, int numsSize, int* returnSize) {(*returnSize) = numsSize;int* array = (int*)malloc(sizeof(int)*(*returnSize));for(int i = 0; i < numsSize; i++){array[i] = nums[i];}QuickSort3(array, 0, numsSize-1);return array;
}

 

结果显然,三个方法都没有通过,快排作为排序界的杠把子,难道就这么拉吗?都跟冒泡和选择排序一个挡位了,所以这里我们需要进一步优化快速排序.

1.1三数取中

以hoare版本为例,key都是取左端点.在有序序列中,原本分区的时间复杂度为O(logN)就会转换成O(N),这就会导致快速排序遇到有序或逆序时,时间复杂度就会变成O(N^2)

示例:

当key为中间值时,满足O(logN)的时间复杂度

当key为最小或最大值时 ,时间复杂度为O(N):

这里还有可能存在栈溢出的风险

 所以快排里面有一个取中的方式,让key不会成为最大数或者时最小数,这里就介绍一下三数取中的方式:

这里的三数是指:left,right,midi((left+right)/2) ,我们需要在这三个数中找出中间值并赋值给key

代码展示:

int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;// left midi rightif (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}else{return left;}}else // a[left] > a[midi]{if (a[midi] > a[right]){return midi;}else if (a[left] < a[right]){return left;}else{return right;}}
}

1.2小区间优化

快速排序类似于二叉树递归的过程,越处于底层的数据会被重复调用多次,所以可以当划分的数列小于10时,可.直接调用其他排序,比如插入排序,直接排好,能减少很大一部分数据的递归调用,

 

代码展示:

	// 小区间优化，不再递归分割排序，减少递归的次数if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}void InsertSort(int* a, int n)
{//  [0, n-1]for (int i = 0; i < n - 1; i++){// [0, n-2]是最后一组// [0,end]有序 end+1位置的值插入[0,end]，保持有序int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

优化后的快速排序

void InsertSort(int* a, int n)
{//  [0, n-1]for (int i = 0; i < n - 1; i++){// [0, n-2]是最后一组// [0,end]有序 end+1位置的值插入[0,end]，保持有序int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}void Swap(int* n, int* m)
{int p = *n;*n = *m;*m = p;
}
//hoare版本
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;// left midi rightif (a[left] == a[midi] && a[left] == a[midi] && a[midi] == a[right])return midi;else if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}else{return left;}}else // a[left] > a[midi]{if (a[midi] > a[right]){return midi;}else if (a[left] < a[right]){return left;}else{return right;}}
}// 避免有序情况下，效率退化
//三数取中
//小区间优化
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 midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){// 右边找小while (begin < end && a[end] >= a[keyi]){--end;}// 左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;// [left, keyi-1] keyi [keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

InsertSort 函数

  • 实现了插入排序算法，将传入的数组 a 按升序排序。
  • 在外部循环中，逐步将数组分为已排序部分和未排序部分。
  • 内部循环通过比较当前元素和已排序部分的元素，找到合适位置插入当前元素，保证数组的有序性。

Swap 函数：

        辅助函数，用于交换两个整数指针所指向的值。

GetMidi 函数：

  • 用于选择三个元素中间值作为快速排序的枢轴（pivot）。
  • 考虑了数组左端、中间和右端三个位置的元素，确保选择合适的枢轴来避免最坏情况下的效率问题。

QuickSort 函数：

  • 实现了快速排序算法。
  • 在大于等于10个元素时，采用快速排序策略，选择枢轴、分割数组、递归排序子数组。
  • 小于10个元素时，采用插入排序优化，减少递归深度，提高效率。

 

2.快速排序的非递归实现 

上面说到过,由于快速排序是递归实现的,在遇到有序或者无序的序列会有栈溢出的风险,所以快速排序的非递归实现是有必要的.

思路: 

利用栈后进先出的特点,模拟快速排序的过程

代码展示:

void QuickSortNonR(int* a, 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 = PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

分析:

数据结构和函数调用：

ST 是一个栈结构，具备以下操作：

  • STInit(&st)：初始化栈 st。
  • STPush(&st, val)：将 val 压入栈 st。
  • STTop(&st)：获取栈顶元素但不弹出。
  • STPop(&st)：弹出栈顶元素。

非递归快速排序实现：

  • 主要逻辑通过栈来维护排序区间的边界。
  • 初始时，将整个数组的左右边界分别压入栈中，表示整个数组需要排序。
  • 进入循环，不断从栈中取出左右边界，执行分区操作（PartSort2 函数），得到分区点 keyi。
  • 根据分区点 keyi，将数组分为 [begin, keyi-1]、keyi、[keyi+1, end] 三部分。
  • 如果左边界小于 keyi - 1，说明左侧还有未排序部分，将其左右边界压入栈中。
  • 如果右边界大于 keyi + 1，同理将其左右边界压入栈中。

循环结束条件：

当栈为空时，说明所有区间已经排序完成，循环结束。

PartSort2 函数：

它的作用是进行数组的分区操作，将数组按照某个基准值分成左右两部分，并返回基准值最终的位置。(可以是hoare,挖坑法,前后指针法)

完整代码:

栈

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);// 取栈顶数据
STDataType STTop(ST* pst);// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);

Stack.c 

#include"Stack.h"// 初始化和销毁
void STInit(ST* pst)
{assert(pst);pst->a = NULL;// top指向栈顶数据的下一个位置pst->top = 0;// top指向栈顶数据//pst->top = -1;pst->capacity = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}// 入栈  出栈
void STPush(ST* pst, STDataType x)
{assert(pst);// 扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}// 20:08继续
// 取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}// 判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}// 获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}

Sort.c

int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;// left midi rightif (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}else{return left;}}else // a[left] > a[midi]{if (a[midi] > a[right]){return midi;}else if (a[left] < a[right]){return left;}else{return right;}}
}// hoare
int PartSort1(int* a, int left, int right)
{// 三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){// 右边找小while (begin < end && a[end] >= a[keyi]){--end;}// 左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin;
}// 前后指针
int PartSort2(int* a, int left, int right)
{// 三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[prev], &a[keyi]);return prev;
}// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
//
//void QuickSort(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort1(a, left, right);
//
//	 [left, keyi-1] keyi [keyi+1, right]
//	QuickSort(a, left, keyi - 1);
//	QuickSort(a, keyi + 1, right);
//}#include"Stack.h"void QuickSortNonR(int* a, 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 = PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

3.总结

非递归与递归快速排序的对比

  • 非递归版本避免了递归调用的额外开销，使用栈来存储分割点，节省了空间。
  • 在处理大规模数据时，递归深度可能导致栈溢出，而非递归版本则能够更好地应对这种情况。

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3249391.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

CTF-Web习题：[BJDCTF2020]ZJCTF，不过如此

CTF-Web习题：[BJDCTF2020]ZJCTF，不过如此

题目链接&#xff1a;[BJDCTF2020]ZJCTF&#xff0c;不过如此 解题思路 访问靶场链接&#xff0c;出现的是一段php源码&#xff0c;接下来做一下代码审阅&#xff0c;发现这是一道涉及文件包含的题 主要PHP代码语义&#xff1a; file_get_contents($text,r); 把$text变量所…
阅读更多...
使用 XPath 定位 HTML 中的 img 标签

使用 XPath 定位 HTML 中的 img 标签

引言 随着互联网内容的日益丰富&#xff0c;网页数据的自动化处理变得愈发重要。图片作为网页中的重要组成部分&#xff0c;其获取和处理在许多应用场景中都显得至关重要。例如&#xff0c;在社交媒体分析、内容聚合平台、数据抓取工具等领域&#xff0c;图片的自动下载和处理…
阅读更多...
浅谈端到端（自动驾驶）

浅谈端到端（自动驾驶）

一、 引言 端到端是近期非常火的话题&#xff0c;尤其在自动驾驶、具身智能等领域。去年UniAD的发布&#xff0c;给大家普及了端到端的网络设计&#xff0c;带动了行业的发展。产业界&#xff0c;特斯拉FSD Beta V12效果惊艳&#xff0c;近期理想也推出了双系统的E2E自动驾驶系…
阅读更多...
使用LVS+NGinx+Netty实现数据接入

使用LVS+NGinx+Netty实现数据接入

数据接入 链接参考文档 LVSKeepalived项目 车辆数据上收&#xff0c;TBox通过TCP协议连接到TSP平台 建立连接后进行数据上传。也可借由该连接实现远程控制等操作。 通过搭建 LV—NGinx—Netty实现高并发数据接入 LVS&#xff1a;四层负载均衡&#xff08;位于内核层&#x…
阅读更多...
Grafana :利用Explore方式实现多条件查询

Grafana :利用Explore方式实现多条件查询

背景 日志统一推送到Grafana上管理。所以&#xff0c;有了在Grafana上进行日志搜索的需求&#xff0c;而进行日志搜索通常需要多条件组合。 解决方案 通过Grafana的Explore的方式实现多条件查询。 直接看操作步骤&#xff1a; 在主页搜索框中输入“Explore” 进入这个界面…
阅读更多...
高精度滚珠导轨：驱动装配线自动化升级！

高精度滚珠导轨：驱动装配线自动化升级！

滚珠导轨是一种先进的运动控制装置&#xff0c;具有高精度、高稳定性和高可靠性等特点&#xff0c;被广泛应用于各个行业&#xff0c;为工业生产带来了巨大的影响。 滚珠导轨技术的广泛应用&#xff0c;尤其是在实现装配流程自动化中&#xff0c;不仅提高了生产效率&#xff0c…
阅读更多...
qt 自定义样式 switch开关，已解决

qt 自定义样式 switch开关，已解决

在日常需求中&#xff0c;需要对功能增加一个开关&#xff0c;因此做了简单封装。结果能正常使用。自定义信号接收&#xff01; 实现 QWidget* switchBtn new CCendSwitchWidget(btn_value);connect(switchBtn, SIGNAL(clicked(bool,QString)), this, SLOT(clickedSlot(bool,…
阅读更多...
41 QOS技术(服务质量)

41 QOS技术(服务质量)

1 QOS 产生背景 对于网络业务&#xff0c;影响服务质量的因素包括传输的带宽、传送的时延、数据的丢包率等。网络资源总是有限的&#xff0c;只要存在抢夺网络资源的情况&#xff0c;就会出现服务质量的要求网络总带宽固定的情况下&#xff0c;如果某类业务占用的带宽越多&am…
阅读更多...
MenuToolButton自绘控件，带下拉框的QToolButton，附源码

MenuToolButton自绘控件，带下拉框的QToolButton，附源码

MenuToolButton自绘控件&#xff0c;带下拉框的QToolButton 效果 下拉样式可自定义 跟随QToolButton的Qt::ToolButtonStyle属性改变图标文字样式 使用示例 正常UI文件创建QToolButton然后提升&#xff0c;或者直接代码创建都可以。 // 创建一个 QList 对象来存储 QPixm…
阅读更多...
Visual Studio Code 实现远程开发

Visual Studio Code 实现远程开发

Background 远程开发是指开发人员在本地计算机上进行编码、调试和测试&#xff0c;但实际的开发环境、代码库或应用程序运行在远程服务器上。远程开发的实现方式多种多样&#xff0c;包括通过SSH连接到远程服务器、使用远程桌面软件、或者利用云开发环境等。这里我们是使用VSCo…
阅读更多...
C学习（数据结构）--＞单链表习题

C学习（数据结构）--＞单链表习题

目录 一、环形链表 题一&#xff1a;环形链表 思路&#xff1a; 思考一&#xff1a;为什么&#xff1f; 思考二&#xff1a;快指针一次走3步、4步、......n步&#xff0c;能否相遇 step1&#xff1a; step2&#xff1a; 代码&#xff1a; 题二&#xff1a; 环形链表 I…
阅读更多...
仅两家！云原生向量数据库 PieCloudVector 全项通过信通院「可信数据库」评测

仅两家！云原生向量数据库 PieCloudVector 全项通过信通院「可信数据库」评测

7月16日&#xff0c;2024 可信数据库发展大会在北京隆重举行。大会以“自主、创新、引领”为主题&#xff0c;近百位数据库领域的专家、学者齐聚一堂&#xff0c;带来高质量的数据库技术洞察与实战经验。 本次可信数据库发展大会中&#xff0c;中国信通院正式公布 2024 年上半年…
阅读更多...
科研绘图系列：R语言热图（heatmap）

科研绘图系列：R语言热图（heatmap）

介绍 热图是一种数据可视化技术，通常用于展示数据的分布情况。它通过颜色的变化来表示数据的大小或密度，使得观察者能够直观地理解数据集中的模式和趋势。以下是热图的一些关键特点和应用场景： 数据分布：热图可以显示数据在不同区域的分布情况，比如在地图上显示不同地区的…
阅读更多...
低代码中间件学习体验分享：业务系统的创新引擎

低代码中间件学习体验分享：业务系统的创新引擎

前言 星云低代码平台介绍 星云低代码中间件主要面向企业IT部门、软件实施部门的低代码开发平台&#xff0c;无需学习开发语言/技术框架&#xff0c;可视化开发PC网页/PC项目/小程序/安卓/IOS原生移动应用&#xff0c;低门槛&#xff0c;高效率。针对企业研发部门人员少&#…
阅读更多...
Vscode+Pyside6开发之虚拟环境配置以及错误解决

Vscode+Pyside6开发之虚拟环境配置以及错误解决

Pyside开发之虚拟环境配置以及错误解决 开发环境一、项目创建以及虚拟环境设置1.创建项目2. 新建py文件，新建虚拟环境3.激活虚拟环境二、项目位置改变pip命令报错1.删除原来的虚拟环境2. 产生包列表文件requirements.txt3.重新创建虚拟环境4.重新安装包文件5.其他错误开发环境…
阅读更多...
大语言模型在病理AI领域中的应用2｜文献速递·24-07-18

大语言模型在病理AI领域中的应用2｜文献速递·24-07-18

小罗碎碎念 本期文献主题&#xff1a;大语言模型在病理AI领域中的应用 本期推文是大模型4病理AI系列的第2期&#xff0c;每一篇文献都使用了ChatGpt&#xff0c;应用场景如下&#xff1a; 直接用ChatGpt生成回答比较多种主流大模型在指定任务中的性能表现比较大模型与专用模型…
阅读更多...
大数据开发之Hadoop

大数据开发之Hadoop

大数据开发之Hadoop Hadoop的发展Hadoop的三个功能组件一、HDFS 分布式文件系统 1、HDFS的基础架构2、HDFS基础操作命令3、HDFS WEB浏览&#xff1a;4、Big Data Tools插件5、使用NFS网关功能将HDFS挂载到本地系统6、HDFS数据存储7、NameNode 元数据8、SecondaryNameNode的作用…
阅读更多...
【CMU博士论文】结构化推理增强大语言模型（Part 0）

【CMU博士论文】结构化推理增强大语言模型（Part 0）

问题 &#xff1a;语言生成和推理领域的快速发展得益于围绕大型语言模型的用户友好库的普及。这些解决方案通常依赖于Seq2Seq范式&#xff0c;将所有问题视为文本到文本的转换。尽管这种方法方便&#xff0c;但在实际部署中存在局限性&#xff1a;处理复杂问题时的脆弱性、缺乏…
阅读更多...
外企跨境传输应该如何做到安全有效的文件管控？

外企跨境传输应该如何做到安全有效的文件管控？

跨境文件传输并非易事&#xff0c;它面临着多重挑战&#xff0c;尤其是数据安全、隐私保护以及法律法规遵守等问题。所以如何做到安全有效的文件管控&#xff0c;却是一个让许多企业头疼的问题。小编今天将说说跨境文件传输面临的主要挑战&#xff0c;并讨论如何选择合适的加密…
阅读更多...
02线性表 - 链表

02线性表 - 链表

这里是只讲干货不讲废话的炽念&#xff0c;这个系列的文章是为了我自己以后复习数据结构而写&#xff0c;所以可能会用一种我自己能够听懂的方式来描述&#xff0c;不会像书本上那么枯燥和无聊&#xff0c;且全系列的代码均是可运行的代码&#xff0c;关键地方会给出注释^_^ 全…
阅读更多...
最新文章

Copyright @ 2022~2023