快速排序(三种方法实现)

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

1. 快速排序

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

<1>hoare法(左右指针法)

(1)画图理解
取最左边key为基准值,用right指针找比key值小的元素,用left指针找比key位置大的元素,将两位置值进行交换,最后,将key值放在二者相遇位置上,就可保证key左边都是比key小的值,右边都是比key大的值,然后进行递归即可实现,从相遇点分割成两部分,在分别对左右两部分重复上述排序。
快速排序(三种方法实现)

(2) 代码思路

//-----------------------快排-------------------/
int HoareSort(int* a, int begain, int end)
{
	int key = begain;
	int left = begain, right = end;
	while (left < right)
	{
		//右边找比key小的值
		while (left < right && a[right] >= a[key])
			right--;
		//左边找比key大的值
		while (left < right && a[left] <= a[key])
			left++;
		swap(&a[right], &a[left]);
	}
	int meeti = left;
	swap(&a[meeti], &a[key]);
	return meeti;
}
void QuickSort(int* a, int begain, int end)
{
	//递归返回条件如果该区间只有一个值或没有值则返回
	if (begain >= end)
		return;
	int meeti = HoareSort(a, begain, end);
	QuickSort(a, begain, meeti - 1);
	QuickSort(a, meeti + 1, end);
}

<2>挖坑法

(1)画图理解
思路:取最左边或最右边值做key,右边形成一个坑,定义两个指针left、right指向头和尾。右边找小值放到左边坑中右边形成新坑,左边找大值放到右边左边形成新坑,将key放到相遇位置。这时key左边值均小于key,右边值均大于key。
快速排序(三种方法实现)
(2) 代码思路

//挖坑法
int DigHoleSort(int* a, int begain, int end)
{
	int key = a[begain];
	int left = begain, right = end;
	while (left < right)
	{
		//右边找小值
		while (left < right && a[right] >= key)
			right--;
		//放到左边坑位中,右边形成新的坑
		a[left] = a[right];
		
		//左边找大值
		while (left < right && a[left] <= key)
			left++;
		//放到右边坑位中,左边形成新的坑
		a[right] = a[left];
	}
	int meeti = left;
	a[meeti] = key;
	return left;
}
void QuickSort(int* a, int begain, int end)
{
	if (begain >= end)
		return;
	//int meeti = HoareSort(a, begain, end);
	int meeti = DigHoleSort(a, begain, end);
	QuickSort(a, begain, meeti - 1);
	QuickSort(a, meeti + 1, end);
}

<3>前后指针法

(1)画图理解
定义两指针一前一后,cur指针找比key小的值,和prev指针前一个值进行交换,直至结束。将prev位置值与key位置值进行交换,此时key位置值,左边比key位置值小,右边比key位置值大,在进行分治就可以了。
快速排序(三种方法实现)
(2) 代码思路

int PBIndexSort(int* a, int begain, int end)
{
	int key = begain;
	//定义两个指针,一前一后
	int prev = begain, cur = begain + 1;
	while (cur <= end)
	{
		//如果cur位置值比key小则与perv前一个值进行交换
		if (a[cur] < a[key] && ++prev != cur)
		{
			swap( &a[cur], &a[prev] );
		}
		cur++;
	}
	//将key放在prev位置
	swap(&a[prev], &a[begain]);
	return prev;
}
void QuickSort(int* a, int begain, int end)
{
	if (begain >= end)
		return;
	//int meeti = HoareSort(a, begain, end);
	//int meeti = DigHoleSort(a, begain, end);
	int meeti = PBIndexSort(a, begain, end);
	QuickSort(a, begain, meeti - 1);
	QuickSort(a, meeti + 1, end);
}

总结
三种方法最终目的都是为了让,key放到它应该排序的位置同时,key左边的值都比key小,key右边的值都比key大,然后进行分治就可以了。

<4>快速排序优化

(1)三数取中法取key
理想情况下我们每回选的key位置值都近似为数组中位数,这样每回递归都为二分。但当数据出现极端情况时,会使我们的快速排序效率大打折扣例如
快速排序(三种方法实现)
优化代码
以hoare法为例

//三数取中法
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] < a[right])
			return right;
		else
			return left;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
}
//hoare法(左右指针法)
int HoareSort(int* a, int begain, int end)
{
	int mid = GetMidIndex(a, begain, end);
	swap(&a[mid], &a[begain]);
	
	//这里我们仍然取key为最左边的数,只不过最左边的值变了
	int key = begain;
	int left = begain, right = end;
	while (left < right)
	{
		//右边找比key小的值
		while (left < right && a[right] >= a[key])
			right--;
		//左边找比key大的值
		while (left < right && a[left] <= a[key])
			left++;
		swap(&a[right], &a[left]);
	}
	int meeti = left;
	swap(&a[meeti], &a[key]);
	return meeti;
}

(2)小区间优化法
小区间优化法实际上就是减少递归的深度,以此来提升效率代码如下:

void QuickSort(int* a, int begain, int end)
{
	if (begain >= end)
		return;
 
	//小区间优化法 当数据量比较大的时候可以通过调整参数(20),来减小递归次数,提高性能
	if ((end - begain) > 20)
	{
		int meeti = HoareSort(a, begain, end);
		QuickSort(a, begain, meeti - 1);
		QuickSort(a, meeti + 1, end);
	}
	else
	{
		//数量比较少的时候用直接插入来排序
		InsertSort(a + begain, end - begain + 1);
	}
 
}

<5>非递归实现

利用栈来存储区间下标,代码如下:要注意先数组头,后入数组尾。出栈时栈顶的数据为数组尾,在出才为头位置下标。代码如下:

void QuickSortNonR(int* a, int begain,  int end)
{
	Stack st;
	StackInit(&st);
	//入栈
	StackPush(&st, begain);
	StackPush(&st, end);
	while (!StackEmpty(&st))
	{
		//出栈
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		//单趟排序
		int mid = HoareSort(a, left, right);
		if (left < mid - 1)
		{
			StackPush(&st, left);
			StackPush(&st, mid - 1);
		}
		if (mid + 1 < right)
		{
			StackPush(&st, mid + 1);
			StackPush(&st, right);
		}
	}
	StackDestory(&st);
}

2.特性

1、快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
2、时间复杂度:O(N*logN)文章来源地址https://www.toymoban.com/news/detail-443182.html

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

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

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

相关文章

  • Java 七大排序之快速排序(三种方法包含优化方法)

    任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。 1)  挖坑法 划分完之后,再左右递归。

    2024年02月09日
    浏览(39)
  • 【Leetcode刷题(数据结构)】:三路划分与三数随机取中的思想实现快速排序的再优化

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

    2024年02月08日
    浏览(46)
  • 【快速排序算法思想及其应用】

    本文主要介绍Java中快速排序(Quick Sort)算法的基本原理、实现方式以及使用场景。快速排序是一种高效的排序算法,通过选取一个基准元素并将待排序序列划分为小于基准元素和大于基准元素的两部分来实现排序。本文将深入剖析快速排序的思想及其在实际应用中的价值。

    2024年02月07日
    浏览(45)
  • 快速排序思想

    快速排序是指通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列。 代码实现:

    2024年02月07日
    浏览(39)
  • 快速排序的基本思想(图文详解)

    快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各

    2024年02月01日
    浏览(34)
  • 【数据结构初阶】十、快速排序(比较排序)讲解和实现(三种递归快排版本 + 非递归快排版本 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】九、排序的讲解和实现(直接插入 希尔 直接选择 堆 冒泡 -- C语言)

    2024年02月08日
    浏览(45)
  • 插入,选择,堆,快速排序算法思想与复杂度

    目录 插入排序 思想 算法步骤 代码 复杂度 选择排序 思想 算法步骤 代码 复杂度 堆排序  思想 算法步骤 代码 复杂度  快速排序  思想 算法步骤 代码 复杂度 稳定性 插入排序是一种简单直观的排序算法。它的工作原理是将数组分为 已排序 和 未排序 两部分,然后依次将未

    2024年02月15日
    浏览(37)
  • 排序算法 - 快速排序(4种方法实现)

    本篇文章的源代码在这,需要自取:Gitee 快速排序是一种常见的排序算法,其基本原理是分治和递归。它的基本思路是,在数组中选择一个元素作为基准值,然后将数组中小于基准值的元素移动到它的左边,大于基准值的元素移动到它的右边。然后对左右两个子数组递归地重

    2024年02月04日
    浏览(36)
  • 排序算法:快速排序(三种排序方式、递归和非递归)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关排序算法的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 目录 前言: 1.快速排

    2024年02月09日
    浏览(38)
  • 快速排序三种思路详解!

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

    2024年02月11日
    浏览(31)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包