数据结构——排序算法之快速排序

 

  个人主页：日刷百题

系列专栏：〖C/C++小游戏〗〖Linux〗〖数据结构〗 〖C语言〗

🌎欢迎各位→点赞👍+收藏⭐️+留言📝 ​

​

前言：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
基本思想：
任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

递归实现方式常见有三种，区别于单趟思想，性能差别不大，下面我们看下快排递归实现。

一、快速排序的递归实现

1.1   Hoare排序

1.1.1  单趟目的

 左子序列中所有元素均小于基准值key，右子序列中所有元素均大于基准值key。

1.1.2   动图解析

单趟思路：

（1）首先记录下keyi位置为最左边位置，然后left和right分别从数组两端开始往中间走。
（2）right先开始向中间行动，如果right处的值小于keyi处的值，则停止等待left走。
（3）left开始行动，当left找到比keyi处小的值时，left和right处的值进行交换。
（4）当两个位置相遇时，将相遇位置的值与keyi处的值进行交换。
 

该排序有一个需要注意的点是：必须左边先走找小

因为左边先走，必定相遇时位置对应的值小于keyi位置值，保证最后这俩个位置交换，相遇位置即是keyi位置对应值最终位置。

解析：

（1）右边先走，假设left遇到right,最后相遇情况是right找到了小于keyi位置的值，left没有找到大于keyi位置值，所以相遇位置值小于keyi位置值。

（2）右边先走，假设right遇到left,最后相遇情况是left找到大，right找到小，left与right互换，left位置对应值小于keyi位置值，right继续找小，与left相遇，所以相遇位置值小于keyi位置值。

 1.1.3  代码实现

解析：

该代码将单趟写在子函数中，这样使得整个代码层次更加清晰，也便于理解。可以发现我们对单趟中keyi做了优化，因为keyi的位置，是影响快速排序效率的重大因素。因此我们采用了三数取中的方法解决选keyi不合适的问题。即知道这组无序数列的首和尾后，我们只需要在首，中，尾这三个数据中，选择一个排在中间的数据作为基准值(keyi)，进行快速排序，即可进一步提高快速排序的效率。

后面2种单趟也做这样的优化，后面就不过多介绍。

//Hoare快排
int GetMid(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] > a[end])
	{
		if (a[end] > a[mid])
		{
			return end;
		}
		else
		{
			if (a[begin] > a[mid])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	else//(a[begin]<= a[end])
	{
		if (a[begin] > a[mid])
		{
			return begin;
		}
		else
		{
			if (a[end] > a[mid])
			{
				return mid;
			}
			else
			{
				return end;
			}
		}
	}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Hoare(int* a, int begin, int end)
{
	int mid = GetMid(a,begin, end);
	swap(&a[begin], &a[mid]);
	int keyi = begin;
	int left = begin;
	int right = end;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);


	}
	swap(&a[keyi], &a[left]);
	return left;

}
void  QuickSort_Hoare(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi= _QuickSort_Hoare(a, begin, end);//单趟
	//递归  [begin,keyi-1] keyi,[keyi+1,end]
	QuickSort_Hoare(a, begin, keyi - 1);
	QuickSort_Hoare(a, keyi+1, end);

}

1.2  挖坑法 

1.2.1  单趟目的

 左子序列中所有元素均小于基准值key，右子序列中所有元素均大于基准值key。

1.2.2  动图解析

单趟思路：

（1）将begin处的值放到key中，将其置为坑位(pit)
（2）right找到比key小的值后将值放入坑位，然后将此处置为新的坑。
  (3)  left找到比key大的值后将值放入坑位，然后将此处置为新的坑。
  (4）当left与right相遇的时候，将key放入到坑位中。

 1.2.3  代码实现 

int GetMid(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] > a[end])
	{
		if (a[end] > a[mid])
		{
			return end;
		}
		else
		{
			if (a[begin] > a[mid])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	else//(a[begin]<= a[end])
	{
		if (a[begin] > a[mid])
		{
			return begin;
		}
		else
		{
			if (a[end] > a[mid])
			{
				return mid;
			}
			else
			{
				return end;
			}
		}
	}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pit(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);
	int pit = begin;
	int  key = a[begin];
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while(left < right&& a[left] <= key)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[left] = key;
	return left;

}
void  QuickSort_Pit(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = _QuickSort_Pit(a, begin, end);
	//[begin,keyi-1],keyi,[keyi+1,end]
	QuickSort_Pit(a, begin, keyi - 1);
	QuickSort_Pit(a, keyi + 1, end);

}

1.3 双指针法

1.3.1  单趟目的

 左子序列中所有元素均小于基准值key，右子序列中所有元素均大于基准值key。

1.3.2  动图解析

单趟思路：

(1)cur位于begin+1的位置，prev位于begin位置，keyi先存放begin处的值。
(2)如果cur处的值大于key处的值，cur++.
(3)如果cur处的值小于等于key处的值，cur处的值，则与prev+1处的值进行交换。
(4)当循环结束时，将prev处的值与keyi的值相交换，返回prev

1.3.3  代码实现

int GetMid(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] > a[end])
{
	if (a[end] > a[mid])
	{
		return end;
	}
	else
	{
		if (a[begin] > a[mid])
		{
			return mid;
		}
		else
		{
			return begin;
		}
	}
}
else//(a[begin]<= a[end])
{
	if (a[begin] > a[mid])
	{
		return begin;
	}
	else
	{
		if (a[end] > a[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pointer(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);
	int key = begin;
	int prev= begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] > a[key])
		{
			cur++;
		}
		else
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;

		}
	}
	swap(&a[key], &a[prev]);
	return prev;

}
void  QuickSort_Pointer(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = _QuickSort_Pointer(a, begin, end);
	//[begin,keyi-1],keyi,[keyi+1,end]
	QuickSort_Pointer(a, begin, keyi - 1);
	QuickSort_Pointer(a, keyi + 1, end);

}

二、快速排序的优化

2.1  三数取中法选key

这个方法提升效率比较显著，上面已经排序均用该方法优化。

2.2  递归到小的子区间，使用插入排序

由于快速排序是递归进行的，当递归到最后三层时，此时数组中的值其实已经接近有序，而且这段区间再递归会极大占用栈(函数栈帧开辟的地方)的空间,最后三层的递归次数占总递归次数的百分之90，所以在区间数据量小于10，我们就不进行递归快速排序了，转而使用插入排序。

 

int GetMid(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] > a[end])
{
	if (a[end] > a[mid])
	{
		return end;
	}
	else
	{
		if (a[begin] > a[mid])
		{
			return mid;
		}
		else
		{
			return begin;
		}
	}
}
else//(a[begin]<= a[end])
{
	if (a[begin] > a[mid])
	{
		return begin;
	}
	else
	{
		if (a[end] > a[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pointer(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);
	int key = begin;
	int prev= begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] > a[key])
		{
			cur++;
		}
		else
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;

		}
	}
	swap(&a[key], &a[prev]);
	return prev;

}
void  QuickSort_Pointer(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if(end-begin+1>10)
{
int keyi = _QuickSort_Pointer(a, begin, end);
	//[begin,keyi-1],keyi,[keyi+1,end]
	QuickSort_Pointer(a, begin, keyi - 1);
	QuickSort_Pointer(a, keyi + 1, end);
}
else
{
InsertSort(a + begin, end - begin + 1);
}

}

三、快速排序的非递归实现

递归改为非递归，一般2种方法：

1、递归转化为非递归可以写成循环，比如斐波那契数列

2、递归转化为非递归可以写成栈，比如现在的快排

递归使用的空间是栈空间，所以容易出现栈溢出的情况，我们将快速排序改为非递归版本，这样空间的开辟就在堆上了，这样也就解决了这个问题。

快速排序的非递归与递归思想相同，非递归使用栈来模拟递归的实现，思路如下：

（1）入栈一定要保证先入左再入右。
（2）取出两次栈顶的元素，然后进行单趟排序

（3）将区间分为[left , keyi - 1] ，keyi ，[ keyi +  1 , right ] 进行右、左入栈。若区间不存在或为1个值则不入栈。
（4）循环2、3步骤直到栈为空。
 

代码实现：

int GetMid(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] > a[end])
{
	if (a[end] > a[mid])
	{
		return end;
	}
	else
	{
		if (a[begin] > a[mid])
		{
			return mid;
		}
		else
		{
			return begin;
		}
	}
}
else//(a[begin]<= a[end])
{
	if (a[begin] > a[mid])
	{
		return begin;
	}
	else
	{
		if (a[end] > a[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}
}
void swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}
int  _QuickSort_Pointer(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[begin], &a[mid]);
	int key = begin;
	int prev= begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] > a[key])
		{
			cur++;
		}
		else
		{
			prev++;
			swap(&a[prev], &a[cur]);
			cur++;

		}
	}
	swap(&a[key], &a[prev]);
	return prev;

}

typedef int DateType;
typedef struct Stack
{
    DateType* a;
    int top;
    int capacity;
}Stack;
//初始化和销毁栈
void InitStack(Stack* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void DestoryStack(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//出栈和入栈
void StackPush(Stack* ps, DateType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        DateType* tmp = (DateType*)realloc(ps->a, sizeof(DateType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail:");
            return;
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

//栈的有效个数和栈顶元素
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}
DateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return   ps->a[ps->top - 1];
}
//判空
bool IsEmptyStack(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}
void  QuickSort_Non_r(int* a, int begin, int end)
{
    Stack tmp;
    InitStack(&tmp);
    StackPush(&tmp,end);
    StackPush(&tmp, begin);
    while (!IsEmptyStack(&tmp))
    {
        int left = StackTop(&tmp);
        StackPop(&tmp);
        int right = StackTop(&tmp);
        StackPop(&tmp);


        int keyi = _QuickSort_Pointer(a, left, right);
        if (keyi+1 <right)
        {
            StackPush(&tmp,right);
            StackPush(&tmp,keyi+1);

        }
        if (left < keyi - 1)
        {
            StackPush(&tmp, keyi-1);
            StackPush(&tmp,left);
        }
   }

    DestoryStack(&tmp);



}

 总结：本篇文章总结了快速排序的递归及非递归俩大种方式。

希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，百题一定会认真阅读！

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

弟12章 1 网络编程

弟12章 1 网络编程

文章目录 网络协议概述 p164TCP协议与UDP协议的区别 p165 网络协议概述 p164 ipv4&#xff1a;十进制点分制 ipv6&#xff1a;十六进制冒号分隔 TCP协议与UDP协议的区别 p165 tcp协议的三次握手&#xff1a;
阅读更多...
MySQL单表查询

MySQL单表查询

显示所有职工的基本信息。 mysql8.0 [chap03]>select * from worker; 查询所有职工所属部门的部门号&#xff0c;不显示重复的部门号。 mysql8.0 [chap03]>select distinct(部门号) from worker; 求出所有职工的人数。 mysql8.0 [chap03]>select count(*) from …
阅读更多...
山西电力市场日前价格预测【2024-01-14】

山西电力市场日前价格预测【2024-01-14】

日前价格预测 预测说明&#xff1a; 如上图所示&#xff0c;预测明日&#xff08;2024-01-14&#xff09;山西电力市场全天平均日前电价为415.13元/MWh。其中&#xff0c;最高日前电价为851.84元/MWh&#xff0c;预计出现在18:15。最低日前电价为198.87元/MWh&#xff0c;预计…
阅读更多...
04.neuvector进程策略生成与管控实现

04.neuvector进程策略生成与管控实现

原文链接&#xff0c;欢迎大家关注我的github 一、进程学习管控的实现方式 策略学习实现&#xff1a; 进程的学习与告警主要依据通过netlink socket实时获取进程启动和退出的事件: 1.创建netLink socket&#xff1b; 2.通过创建netlink的fd对进程的事件进行捕获与更新&#x…
阅读更多...
“超人练习法”系列08：ZPD 理论

“超人练习法”系列08：ZPD 理论

01 先认识一个靓仔 看过 Lev Vygotsky 这个人的书吗&#xff1f;他是一位熟练心理学家&#xff0c;对人们习得技能的方式非常感兴趣&#xff0c;但他 37 岁的时候就因肺炎英年早逝了。 他认为社会环境对学习有关键性的作用&#xff0c;认为社会因素与个人因素的整合促成了学习…
阅读更多...
计算机网络 —— 数据链路层

计算机网络 —— 数据链路层

数据链路层 3.1 数据链路层概述 数据链路层把网络层交下来的数据构成帧发送到链路上&#xff0c;以及把收到的帧数据取出并上交给网络层。链路层属于计算机网络的底层。数据链路层使用的信道主要由以下两种类型&#xff1a; 点对点通信。广播通信。 数据链路和帧 链路&…
阅读更多...
UniRepLKNet实战：使用 UniRepLKNet实现图像分类任务（二）

UniRepLKNet实战：使用 UniRepLKNet实现图像分类任务（二）

文章目录 训练部分导入项目使用的库设置随机因子设置全局参数图像预处理与增强读取数据设置Loss设置模型设置优化器和学习率调整策略设置混合精度&#xff0c;DP多卡&#xff0c;EMA定义训练和验证函数训练函数验证函数调用训练和验证方法 运行以及结果查看测试完整的代码 在上…
阅读更多...
LV.13 D10 Linux内核移植 学习笔记

LV.13 D10 Linux内核移植 学习笔记

一、Linux内核概述 1.1 内核与操作系统 内核 内核是一个操作系统的核心&#xff0c;提供了操作系统最基本的功能&#xff0c;是操作系统工作的基础&#xff0c;决定着整个系统的性能和稳定性 操作系统 操作系统是在内核的基础上添加了各种工具集、桌面管理器、库、…
阅读更多...
基于Java SSM框架实现企业车辆管理系统项目【项目源码】计算机毕业设计

基于Java SSM框架实现企业车辆管理系统项目【项目源码】计算机毕业设计

基于java的SSM框架实现企业车辆管理系统演示 JSP技术 JSP技术本身是一种脚本语言&#xff0c;但它的功能是十分强大的&#xff0c;因为它可以使用所有的JAVA类。当它与JavaBeans 类进行结合时&#xff0c;它可以使显示逻辑和内容分开&#xff0c;这就极大的方便了运动员的需求…
阅读更多...
关于html导出word总结一

关于html导出word总结一

总结 测试结果不理想&#xff0c;html-to-docx 和 html-docx-js 最终导出的结果 都 差强人意&#xff0c;效果可以见末尾的附图 环境 "electron": "24.3.0" 依赖库 html-docx-js html-docx-js - npm html-to-docx html-to-docx - npm file-saver…
阅读更多...
如何将重复方法封装为Aop切面并结合注解使用

如何将重复方法封装为Aop切面并结合注解使用

首先要导入依赖 <dependency><groupId>org.aspectj</groupId><artifactId>aspectjweaver</artifactId> </dependency> 编写注解 package com.yg.domain.note;import java.lang.annotation.ElementType; import java.lang.annotation.Rete…
阅读更多...
PyCharm连接服务器 - 2

PyCharm连接服务器 - 2

文章目录 PyCharm连接服务器-21.如何连接服务器&#xff1f;2.如何在终端窗口打开SSH连接&#xff1f;3.Terminal终端出现中文乱码的解决办法&#xff1f;4.如何查看远程服务器的树目录结构&#xff1f;5.如何配置代码同步&#xff1f;6.如何为项目配置远程服务器中的python解释…
阅读更多...
前端 TS 语法继承 多态 修饰符 readonly 抽象类 ts 基本写法 可选 剩余参数 函数重载 接口 类（3）

前端 TS 语法继承 多态 修饰符 readonly 抽象类 ts 基本写法 可选 剩余参数 函数重载 接口 类（3）

继承 继承之间的叫法 A类继承了B类&#xff0c;那么A类叫做子类&#xff0c;B类叫成基类 子类 ---》派生类 基类 ---》超类&#xff08;父类&#xff09; // 继承之间的叫法 // A类继承了B类&#xff0c;那么A类叫做子类&#xff0c;B类叫成基类 // 子类 ---》派生类 // 基类 …
阅读更多...
【C++ 程序设计入门基础】- 第4节-函数

【C++ 程序设计入门基础】- 第4节-函数

1、函数 函数是对实现某一功能的代码的模块化封装。 函数的定义&#xff1a; 标准函数&#xff1a; 输入 n 对整数的 a、b &#xff0c;输出它们的和。 #include <iostream> #include <windows.h> using namespace std;int add(int a,int b);//函数原型声明int…
阅读更多...
ppt怎么录屏录音并且导出？好用录屏软件推荐

ppt怎么录屏录音并且导出？好用录屏软件推荐

ppt已经成为了日常工作与学习中必不可少的工具&#xff0c;而ppt屏幕录制功能&#xff0c;可以方便用户将他人的演讲或视频中的内容记录下来&#xff0c;以便进一步学习与研究。录制ppt演示并将其导出为视频文件&#xff0c;可以帮助我们进行分享&#xff0c;但是很多人不知道p…
阅读更多...
uniapp 制作 wgt 包（用于 app 的热更新）

uniapp 制作 wgt 包（用于 app 的热更新）

升级版本号 修改 manifest.json 的配置&#xff0c;应用版本名称和应用版本号 必须高于上一版的值。 制作 wgt 包 发布 wgt 包 打开 uni-admin 项目的升级中心 上传后会自动生成下载链接 app 的静默热更新 发布新版后&#xff0c;用户打开app&#xff0c;后台会自动下载 wgt…
阅读更多...
【NR技术】RRC状态转移以及RRC重建立过程

【NR技术】RRC状态转移以及RRC重建立过程

1 概述 本文介绍NR RRC状态转移的过程以及RRC重建立相关的过程。 2 RRC状态转移 2.1 RRC connected 态到 RRC inactive转移 RRC connected到RRC inactive state状态转换&#xff0c;gNB由gNB- cu和gNB- du (s)组成的场景下&#xff0c;如图1所示 图1 RRC connected to RRC …
阅读更多...
odoo17基础培训1-odoo开发基础知识准备以及odoo17开发环境安装

odoo17基础培训1-odoo开发基础知识准备以及odoo17开发环境安装

odoo17基础培训 一、odoo开发基础知识准备以及odoo17开发环境安装 1、odoo是什么&#xff1f; 当我介绍客户使用odoo系统作为业务管理平台时&#xff0c;有时会被问到Odoo是什么&#xff1f; 简单点&#xff0c;可以这么说&#xff1a; Odoo是一套完整的系统&#xff0c;是…
阅读更多...
强化学习（一）简介

强化学习（一）简介

强化学习这一概念在历史上来源于行为心理学&#xff0c;来描述生物为了趋利避害而改变自己行为的学习过程。人类学习的过程其实就是为达到某种目的不断地与环境进行互动试错&#xff0c;比如婴儿学习走路。强化学习算法探索了一种从交互中学习的计算方法。 1、强化学习 强化学…
阅读更多...
ftp安装与配置 云服务器 CentOS7

ftp安装与配置 云服务器 CentOS7

1、FTP的安装 #安装 yum install -y vsftpd#设置开机启动 systemctl enable vsftpd.service#启动 systemctl start vsftpd.service#停止 systemctl stop vsftpd.service#查看状态 systemctl status vsftpd.service 2、配置FTP #修改前先进行备份文件 cp /etc/vsftpd/vsftpd…
阅读更多...
最新文章

Copyright @ 2022~2023