八大排序——快速排序

这篇具有很好参考价值的文章主要介绍了八大排序——快速排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

八大排序——快速排序,数据结构,八大排序
Hello,大家好,今天分享的八大排序里的快速排序,所谓快速排序是一个叫霍尔的人发明,有很多人可能会觉得为什么不叫霍尔排序,其中原因就是因为它快,快速则体现了它的特点,今天我们就来讲一下快速排序,现在开始我们的学习吧。

快速排序

1.基本思想
通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
实现逻辑

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

① 从数列中挑出一个元素,称为 “基准”(pivot),
② 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
③ 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

我们来看一下它的图是怎么实现的

八大排序——快速排序,数据结构,八大排序
首先我们给定它一个数组,并且定义左边为left,右边为right,然后我们的有个中间值,中间值这里我们就叫它为k,定义这个k是从left开始,当然我们也可以从right开始,等一下会来讲原因,现在我们只要看懂它的图就行
八大排序——快速排序,数据结构,八大排序
因为是从左边开始,所以要从右边先走,原因是我们这样才能确定left和right相遇的时候的值一定比k的值小,这里再详细展开讲解一下,我们的left和right相遇有两种可能,一种是left和right相遇,这个时候相遇是怎样的呢,因为right先走,遇到比k小的时候停下来,然后left又开始走,除非遇到比l大的值才会停下,否则就继续,但是我们还有一个结束条件那就是left要小于right,所以如果left没有找到比k大的值,他们就会相遇,那这样的话,因为我们right找到小的值了,所以最后k肯定比right所指向的值要大,还有一个就是我们right遇到left,那同样的道理,说明我们的right没有找到比k大的值,所以相遇之后也是一样的道理,结论就是相遇的值一定比k指向的值小。那我们再继续来看图

八大排序——快速排序,数据结构,八大排序
这个时候我们的right找到比k小的值,然后才开始动left,那我们现在开始动left

八大排序——快速排序,数据结构,八大排序
left也找到了,那现在就是交换它们的,这里我们用一个swap函数就可以了,因为后面还需要用到swap这个函数的,交换之后变成这样的
八大排序——快速排序,数据结构,八大排序
可以看到先在我们已经开始交换,我们找值需要一个两个while,外面还需要一个大while控制

那我们现在可以继续开始动right了
八大排序——快速排序,数据结构,八大排序
这下又找到了
开始动left

八大排序——快速排序,数据结构,八大排序
那现在我们需要交换他们
八大排序——快速排序,数据结构,八大排序
现在我们也交换好了,现在right在走一步就会爆炸(小编是小黑子,实锤了),这个时候循环就应该结束

八大排序——快速排序,数据结构,八大排序
我们需要做的就是在循环外面再进行k和left的交换

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
	int k = left;
	while (left < right)
	{
		while ( a[right] > a[k])
		{
			right--;
		}
		while ( a[left] < a[k])
		{
			left++;
		}
		
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[k]);
	return left;
}

这里其实会有问题,有两个问题,一个是会存在越界,一个就是会出现死循环,先讲一下死循环的例子,比如我们再第一次找left和right的值,这两个值的大小是相等的,那他们进行交换之后,left和right的值就不会变了,因为循环他们进不去了,所以要加一个等于的条件就行了,还有就是越界,我们之前讲过越界就像查酒驾一样,是有随机性的,为什么会越界,是因为right可能一直找不到小的值,然后就会比left还小,所以我们只需要加上一个条件就行了
看看代码

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
	int k = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[k])
		{
			right--;
		}
		while (left < right && a[left] <= a[k])
		{
			left++;
		}
		
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[k]);
	return left;
}

现在就是这只是我们走了一遍并不能实现将他们变成有序数列,所以这里我们就可以用递归进行遍历,怎么进行遍历,为什么能进行遍历呢,我们来分析

八大排序——快速排序,数据结构,八大排序
会这样分成左边和右边,然后再左边和右边再进行我们上面的操作,那是不是和二叉树很 相似的,所以我们递归实现一下,这里不过多的讲解,等我更新二叉树的文章后,大家可能看起来就明白了

void QuickSort(int* a, int begin,int end)
{	
	if (begin >= end)
		return;
	int ret = PartSort(a, begin, end);
	QuickSort(a, begin, ret - 1);
	QuickSort(a, ret + 1, end);
}

完整代码加测试代码

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
int PartSort(int* a,int left, int right)
{
	int k = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[k])
		{
			right--;
		}
		while (left < right && a[left] <= a[k])
		{
			left++;
		}
		
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[k]);
	return left;
}

void QuickSort(int* a, int begin,int end)
{	
	if (begin >= end)
		return;
	int ret = PartSort(a, begin, end);
	QuickSort(a, begin, ret - 1);
	QuickSort(a, ret + 1, end);
}

#include<stdio.h>
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,10,8 };
	QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

八大排序——快速排序,数据结构,八大排序
反正最后排序成功了,这个挡住了一部分结果,我换个大的
八大排序——快速排序,数据结构,八大排序
好好好,今天的学习就到这吧,拜拜。。。。文章来源地址https://www.toymoban.com/news/detail-703522.html

到了这里,关于八大排序——快速排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构--八大排序】之堆排序

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 口诀:排降序,建小

    2024年02月08日
    浏览(46)
  • 【数据结构】八大排序算法

    目录 一、直接插入排序 二、希尔排序 三、选择排序  3.1、简单选择排序  3.2、快速选择排序(Top K问题) 四、堆排序 五、冒泡排序 六、快速排序   1、递归版本      1.1 hoare 法      1.2 挖坑法      1.3 前后指针法   2、非递归版本   3、快速排序的优化      3.1 三数取中

    2024年02月09日
    浏览(90)
  • 【数据结构】八大排序(一)

    目录 前言: 直接插入排序 直接插入排序代码实现 直接插入排序特性总结 希尔排序 希尔排序代码实现 希尔排序特性总结 直接选择排序 直接选择排序代码实现 直接选择排序特性总结 堆排序 堆的向下调整算法 建堆 堆排序代码实现 堆排序特性总结 排序即使得一串记录,按照

    2024年02月03日
    浏览(37)
  • 【数据结构】八大排序(一)

    😛作者:日出等日落 📘 专栏:数据结构         珍惜自己的时间,利用好每一份每一秒。做事不放过没一个细节,小心谨慎,细致,能够做到这些,还有什么是不可能的呢? 目录 ​编辑 ✔排序的概念: ✔排序的应用: ✔常见的排序算法: ✔常见排序算法的实现: ✔插入

    2024年02月03日
    浏览(59)
  • 数据结构--八大排序

    插入排序的思想跟摸牌很相似,从我们摸到第二张牌的开始,依次将摸到到牌依次有序的插入到手中,最后手牌变成了有序。 有了大致的思路,接下来就要细分插入排序的细节。 首先考虑某一趟的插入排序。为什么先考虑某一趟呢?因为当需要解决的问题比较复杂时先将问

    2024年02月02日
    浏览(44)
  • 【数据结构】八大排序(二)

    😛作者:日出等日落 📘 专栏:数据结构 在最黑暗的那段人生,是我自己把自己拉出深渊。没有那个人,我就做那个人。                                                                                                                                     

    2024年02月03日
    浏览(35)
  • (数据结构)八大排序算法

       排序 (Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个 数据元素 (或记录)的任意序列,重新排列成一个有序的序列。 介绍 :将待排的数,和有序的数比较,直到一个合适的位置,然后进行插入。 示图 : 将待排数4,与有序数对比,然后插入到

    2023年04月21日
    浏览(44)
  • 【数据结构】八大排序 (三)

    目录 前言: 快速排序 快速排序非递归实现 快速排序特性总结 归并排序 归并排序的代码实现 归并排序的特性总结 计数排序 计数排序的代码实现 计数排序的特性总结 前文快速排序采用了递归实现,而递归会开辟函数栈帧,递归的深度越深,占用栈区的空间就越大, 栈区的

    2024年02月01日
    浏览(45)
  • 【数据结构】八大排序详解

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🐌 个人主页:蜗牛牛啊 🔥 系列专栏:🛹数据结构、🛴C++ 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与

    2024年02月13日
    浏览(38)
  • 「数据结构」八大排序1

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :初阶数据结构 🎇 欢迎点赞收藏加关注哦! 插排就是将一个元素插入一个有序序列中合适的位置,分为 直接插入排序 和 希尔排序 流程如下: ①保存待插入的值:假设某一趟中有序序列最后一个元素下标为end,先 保存(end+1)位置的

    2024年02月03日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包