【八大经典排序算法】快速排序

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


【八大经典排序算法】快速排序,数据结构学习分享,排序算法,算法,数据结构,c语言,c++


一、概述

说到快速排序就不得不提到它的创始人 hoare了。在20世纪50年代,计算机科学家们开始研究如何对数据进行排序,以提高计算机程序的效率。当时,常用的排序算法包括冒泡排序、插入排序和选择排序等。

然而,这些算法的效率都相对较低,特别是在处理大量数据时。于是,人们开始寻找更快速的排序算法。Tony Hoare 在研究中发现了一种基于分治思想的排序方法,即快速排序。

二、思路实现

快速排序的思想是任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

代码如下:

// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	// 按照基准值对数组的 [left, right)区间中的元素进行划分
	int keyi = PartSort(a, begin, end);
	//分成[begin,keyi-1] keyi [keyi+1,end]
	
	 // 递归排[left, div)
	QuickSort(a, begin, keyi - 1);
	 // 递归排[div+1, right)
	QuickSort(a, keyi + 1, end);
}

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,接下来只需分析如何按照基准值来对区间中数据进行划分的方式即可。
待排序集合分割时,将区间按照基准值划分为左右两半部分的常见方式有以下3种。

2.1 hoare版本

思路

  1. 选择一个基准元素(key),可以是最左边也可以是最右边。
  2. 定义两个指针,一个指向数组的第一个元素(左指针),一个指向数组的最后一个元素(右指针)。(需要注意的是:若选择最左边的数据作为key,则需要right先走;若选择最右边的数据作为key,则需要left先走
  3. 移动左指针,直到找到一个大于等于基准元素(key)的元素;移动右指针,直到找到一个小于等于基准元素(key)的元素。之后交换交换左右指针所指向的元素。然后不断重复上述步骤直到左指针大于右指针
  4. 最后将基准元素与右指针所指向的元素交换位置,此时基准元素位于正确的位置。此时左边元素>=key,右边元素<=key。

Tips:博主在这里解释一下为什么“若选择最左边的数据作为key,则需要right先走;若选择最右边的数据作为key,则需要left先走”,后续其他方法同理。
① :左边作key,右边先走,保证了相遇位置的值小于key或就是key的位置。
②:右边作key,左边先走,保证了相遇位置的值大于key或就是key的位置。

以①为例,L和R相遇无非就两种情况:L遇R,R遇L。
情况一:L遇R。在R停下来后,L还在走。由于R先走,R停下来的位置一定小于Key。相遇位置为R停下来的位置,一定比key小。
情况二:R遇L。再相遇的这一轮,L就不动了,R在移动。相遇位置即为L的位置。而L的位置就是key的位置 or 已经交换过一些轮次了,此时相遇位置一定比key小。

【动画演示】:
【八大经典排序算法】快速排序,数据结构学习分享,排序算法,算法,数据结构,c语言,c++
代码如下:

 //[left, right]--采用左闭右闭
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//找到右边比key小的数
		while (left < right && a[right] <= a[keyi])
		{
			right--;
		}

		//找到左边比key大的数
		while (left < right && a[left] >= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

2.2 挖坑法

思路

  1. .选出一个数据(一般是最左边或是最右边的)存放在key变量中,同时该数据位置形成一个坑。
  2. 还是左右指针left和right,left从左向右走,right从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)
  3. 移动右指针找到第一个比key小的数并填到坑位,此时右指针所在位置变成新的坑。然后移动左指针找到第一个比key大的数并填到坑位,此时左指针所在位置变成新的坑。然后和hoare版本一样,不断重复上述步骤即可

【动画演示】:
【八大经典排序算法】快速排序,数据结构学习分享,排序算法,算法,数据结构,c语言,c++
代码如下:

//挖坑法
int PartSort(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//找到右边比key小的值
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;

		//左边比key大的值
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

2.3 前后指针版本

思路

  1. 选出一个key,一般是最左边或是最右边的。
  2. 起始时,prev指针指向序列开头,cur指针指向prev+1。
  3. 若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。

【动画演示】:
【八大经典排序算法】快速排序,数据结构学习分享,排序算法,算法,数据结构,c语言,c++
代码如下:

//前后指针法
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

三、优化

虽然已经可以解决问题了,但还有一个问题:
当选取的key每次都是中位数时,效率最好,时间复杂度为O(N*logN);但当数组有序时变成最坏,时间复杂度变为O(N^2)!
对于上述情况,这里有两种优化方式:

  1. 三数取中法选key
  2. 递归到小的子区间时,可以考虑使用插入排序

3.1 三数取中

这里博主给出一直最简单的方法:

int GetMidIndix(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[mid] > a[right])
			return right;
		else
			return left;
	}
	else//a[left]>=a[mid]
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[mid] < a[right])
			return right;
		else
			return left;
	}
}

3.1.1 最终代码

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int GetMidIndix(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[mid] > a[right])
			return right;
		else
			return left;
	}
	else//a[left]>=a[mid]
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[mid] < a[right])
			return right;
		else
			return left;
	}
}

// hoare
// [left, right]
//int PartSort(int* a, int left, int right)
//{
//	int midi = GetMidIndix(a, left, right);
//	Swap(&a[left], &a[midi]);
//
//	int keyi = left;
//	while (left < right)
//	{
//		//找到右边比key小的数
//		while (left < right && a[right] <= a[keyi])
//		{
//			right--;
//		}
//
//		//找到左边比key大的数
//		while (left < right && a[left] >= a[keyi])
//		{
//			left++;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[keyi], &a[left]);
//	return left;
//}


//挖坑法
//int PartSort(int* a, int left, int right)
//{
//	int midi = GetMidIndix(a, left, right);
//	Swap(&a[left], &a[midi]);
//
//	int key = a[left];
//	int hole = left;
//	while (left < right)
//	{
//		//找到右边比key小的值
//		while (left < right && a[right] >= key)
//		{
//			right--;
//		}
//		a[hole] = a[right];
//		hole = right;
//
//		//左边比key大的值
//		while (left < right && a[left] <= key)
//		{
//			left++;
//		}
//		a[hole] = a[left];
//		hole = left;
//	}
//	a[hole] = key;
//	return hole;
//}


//前后指针法
int PartSort(int* a, int left, int right)
{
	int midi = GetMidIndix(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort(a, begin, end);
	//分成[begin,keyi-1] keyi [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

3.1.2 快速排序的特性总结

  1. 时间复杂度:O(N*logN)

【八大经典排序算法】快速排序,数据结构学习分享,排序算法,算法,数据结构,c语言,c++

  1. 空间复杂度:O(logN)
  2. 稳定性:不稳定

四、非递归实现快排

思路:

  1. 定义一个栈,然后将待排序的数组的起始索引和结束索引入栈。
  2. 通过前面将的三种分割区间的方法将数组的起始索引和结束索引之间的元素分成两部分,左边部分小于等于基准元素,右边部分大于等于基准元素。
  3. 由于非递归实现时,我们是通过从栈中两两取出维护待排序数组的下标,所以接下来就是如果左边部分的长度大于1,则将左边部分的起始索引和结束索引入栈;如果右边部分的长度大于1,则将右边部分的起始索引和结束索引入栈。最后循环此操作,直到栈为空。

代码如下:

//前后指针法
int PartSort(int* a, int left, int right)
{
	int midi = GetMidIndix(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

//快排非递归
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);

		int right = STTop(&st);
		STPop(&st);

		int keyi = PartSort(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		if (keyi + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}

		if (keyi - 1 > left)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
	}

	STDestroy(&st);
}

【八大经典排序算法】快速排序,数据结构学习分享,排序算法,算法,数据结构,c语言,c++
【八大经典排序算法】快速排序,数据结构学习分享,排序算法,算法,数据结构,c语言,c++文章来源地址https://www.toymoban.com/news/detail-724135.html

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

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

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

相关文章

  • 【数据结构】八大排序算法

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

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

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

    2023年04月21日
    浏览(39)
  • 【数据结构与算法】八大排序

    初看这些概念可能一脸懵,但是没有关系,等下面学完几种排序之后在来看这些概念非常容易理解。 排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的

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

    排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 下面是常见的排序算法: 直接插入排序是一种简单的插入排序法,其基本思想是: 把待排序的元素按其值的大小逐个插入到一个已经排好序的有序序列中,直到所有的

    2023年04月14日
    浏览(59)
  • 【数据结构】八大排序之简单选择排序算法

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 目录 一.简单选择排序简介及思路 二.简单选择排序的代码实现 三.简单选择排序的优化 四.简单选择排序的时间复杂度分析 结语 简单选择排序算法(Simple Selection Sort) 是一种简单直观的 选择排序算

    2024年02月01日
    浏览(77)
  • 【数据结构】--八大排序算法【完整版】

    本文主要讲解代码及代码思路,涵盖八大排序的全面知识点 ———————————————— 目录 一、直接插入排序 二、希尔排序(直接插入排序的改良版) 三、选择排序(直接选择排序) 四、堆排序 五、冒泡排序 六、快速排序 1、 左右指针法 2、挖坑法: 3、前后指针

    2024年02月16日
    浏览(43)
  • 【数据结构】 常见的八大排序算法

    排序有 内部排序和外部排序 ,内部排序是数据记录在内存中进行排序,这里八大排序就是内部排序,指直接插入,希尔,选择,堆排,冒泡,快排,归并,计数。 下面让我们来共同学习这八大排序吧!🤗🤗🤗 什么是外部排序: 外排序是数据量较大,内存放不下,数据放到外

    2024年02月12日
    浏览(106)
  • 【八大经典排序算法】快速排序

    说到快速排序就不得不提到它的创始人 hoare了。在20世纪50年代,计算机科学家们开始研究如何对数据进行排序,以提高计算机程序的效率。当时,常用的排序算法包括冒泡排序、插入排序和选择排序等。 然而,这些算法的效率都相对较低,特别是在处理大量数据时。于是,

    2024年02月07日
    浏览(47)
  • 第五章 数据结构与算法——八大排序

    目录 一、排序的概念及其运用 二、八大排序的原理及其实现(升序为例) (一)、直接插入排序 (二)、希尔排序(也叫缩小增量排序)(重要) 1.原理: 2.该排序一般分为两个步骤: 3.预排序过程: 4.预排序的意义(升序为例): 5.希尔排序的特点: 6.希尔排序代码实现

    2024年02月19日
    浏览(49)
  • 数据结构__<八大排序> __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序(C语言实现)

    目录 插入排序  希尔排序 选择排序 堆排序 冒泡排序 快速排序 hoare法 挖坑法 前后指针法 快排特性总结 三数取中优化 小区间优化 快排非递归 归并排序 归并排序非递归 计数排序 总结 OJ测试 1、元素集合越接近有序,直接插入排序算法的时间效率越高 2、时间复杂度:O(N^2

    2023年04月09日
    浏览(81)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包