数据结构与算法:快速排序

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


快速排序

荷兰国旗问题

想要理解快速排序,就先理解这个问题:

数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
[LeetCode75.颜色分类]

荷兰国旗是由红白蓝三色组成的:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
现在将其颜色打乱
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
然后根据一定的算法,将其复原为红白蓝三色,这就叫做荷兰国旗问题。

在LeetCode的题目中,其将荷兰国旗的三个颜色用0,1,2来表达,也就是说我们要把大于1的放到1的右边,小于1的放到1的左边,这就是解决这个问题的基本思路。

快排的基本思路也是如此:在一趟排序中,将一个值作为key值,然后将大于这个key值的数放到右边,小于key的放到key的左边。

比如这样个数组
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
假设我们将第一个值作为key值,那么高于这个红线的值都要到右边作为大于区,低于这个红线的值都要到左边作为小于区,然后再把key放到大于区和小于区的中间。

比如这样:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言

然后再把key值插入到中间:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
这样左边的值都小于key,右边的值都大于key。

那么这要如何实现呢?我们先看到最古早的快速排序–霍尔版本


霍尔版本

我们的目的是:把大于key的值放到右边,小于key的值放到左边。

此时霍尔想到,安排两个变量leftright左边的变量left往右寻找大于这个key的值右边的变量right往左寻找小于这个key的值一旦left和right都找了值,交换left与right的值
示例:
一开始选定第一个值作为key值:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
然后i变量往右移动,直到找到一个值大于key:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
接着right往左移动,找到一个值小于key:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
交换两个值:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
循环以上步骤:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
当我们完成这个过程后,数组状态如下:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言

红色区域是小于区,绿色区域是大于区
接下来就是要把key放到小于区大于区的中间,这个过程,只需要将key与小于区的最后一个元素交换位置即可

数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
这样我们就完成了一趟排序。

一趟排序的代码如下:

	int left = 0, right = n;
	int keyi = 0;

	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[left], &a[keyi]);

以下是对代码的解释:

  1. 初始化变量leftright,分别表示数组的左右边界。left初始为0,right初始为n,其中n表示数组长度。
  2. 初始化变量keyi,表示选取的基准元素的下标,初始为0。
  3. 进入循环,循环条件是left < right,即左边界小于右边界。
  4. 第一个while循环:从右边开始向左遍历数组a,寻找第一个小于基准元素a[keyi]的元素。循环条件是left < right并且a[right]大于等于a[keyi],如果满足条件,说明当前元素不是要找的元素,则right减1,寻找下一个元素。
  5. 第二个while循环:从左边开始向右遍历数组a,寻找第一个大于基准元素a[keyi]的元素。循环条件是left < right并且a[left]小于等于a[keyi],如果满足条件,说明当前元素不是要找的元素,则left加1,寻找下一个元素。
  6. 当两个while循环结束后,说明找到了需要交换的两个元素。调用Swap函数,将a[left]a[right]交换位置。
  7. 继续下一轮循环,直到left >= right。
  8. 当循环结束,交换a[left]a[keyi],即把key值和小于区的最后一个元素交换位置,让key到达正确位置。

图示:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
这个过程中,left左侧的值(紫色)都小于keyright右侧的值(绿色)都大于key,当相遇时,两者分别就维护了一段大于区和一段小于区,直接将key插入即可。

那么这一趟排序有什么用呢?虽然最后没有把整个数组变成有序,但是我们的key值找到了正确的位置
也就是说,经过这一趟排序,key的位置此后都不会改变了,key的位置就是完全有序状态下的位置。

这是为什么?
不妨想想一个完全有序的数组,取其中某一个值出来,不就是左边的所有值都小于等于这个元素,右边所有值大于等于这个元素吗?

那么我们要如何进行接下来的步骤,让整个数组有序?
答案是递归。
经过这一趟排序,我们将数组拆分为了三个区域:[小于区]:[key]:[大于区]

接下来我们不断将小于区和大于区拆分出来执行这个过程:

1.选key
2.筛选新的小于区和大于区

数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
当快速排序递归到底层时,每个子数组只含有一个元素或没有元素,这些子数组都可以看作是有序的。由于每次递归都确保了基准元素的左右两个部分分别有序,最终整个数组就会有序。

我们看一看快速排序的主体部分:

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
		
	//单趟排序
	
	QuickSort(a, begin, keyi - 1);//递归小于区间
	QuickSort(a, keyi + 1, end);//递归大于区间
}

函数QuickSort接受一个整型数组a以及两个整数beginend作为参数,表示对数组的子区间[begin, end]进行排序。如果begin >= end,即子区间为空或只有一个元素,那么不需要排序,直接返回。

在每次递归调用中,函数将主区间分为两个子区间:小于key的区间和大于key的区间。通过递归调用自身,对两个子区间进行排序。

通过递归调用QuickSort(a, begin, keyi - 1),对小于关键字的区间进行排序。递归调用QuickSort(a, keyi + 1, end)对大于关键字的区间进行排序。

经过多次递归调用后,整个数组将被划分为若干个有序的子区间,最后合并起来得到整体有序的数组。

完整代码:

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

//单趟排序开始---------------------------------------
	int left = begin, right = end;
	int keyi = begin;

	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[left], &a[keyi]);
//单趟排序结束---------------------------------------

	keyi = left;
	QuickSort(a, begin, keyi - 1);//递归小于区间
	QuickSort(a, keyi + 1, end);//递归大于区间
}

其中,我们将单趟排序称为PartSort,递归主体就是快排主体,我们会如下拆分代码:

int PartSort(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyi = begin;

	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[left], &a[keyi]);
	keyi = left;

	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
		
	int keyi = PartSort(a, begin, end);
	
	QuickSort(a, begin, keyi - 1);//递归小于区间
	QuickSort(a, keyi + 1, end);//递归大于区间
}

总效果图:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言

至此,我就为大家解释完了快排的基本思想,但是快排至此还不是完全体,后人对快排做了非常多的优化,使得快排性能一步一步提高。


递归优化

小区间优化

快速排序是基于递归的排序,其递归是会向左右区间递归,那么就会形成一个二叉树的结构。而二叉树的最后一层的节点占比可以高达50%。

假设满二叉树的深度为h,那么最后一层的节点数目为2(h-1)个,而满二叉树的总节点数目为2h - 1个。

因此,最后一层占所有节点的百分比为: (2(h-1))/(2h - 1) * 100%
当递归层数足够深,这个式子就可以看为: (2(h-1))/(2h ) * 100% = 50%

而当快速排序递归到最后一层,区间内只有一两个数字需要排序了,此时再递归是没必要的。我们可以选用其它的排序来进行最后几个数字的排序,这样可以大量节省递归的消耗,提高性能。

在此,我们可以利用beginend的差值来控制递归,当其差值小于一定值时,我们改用插入排序来收尾。因为快速排序到了最后几层,递归出来的小数组已经十分接近有序,而插入排序对有序数组的适应性较好,所以这里选用插入排序。

代码如下:

void QuickSort(int* a, int begin, int end) 
{
	int THRESHOLD = 10; // 设定阈值为10 
	if (begin >= end) 
	 return; 
	 
	if (end - begin + 1 <= THRESHOLD)
	{
		InsertSort(a, begin, end);// 使用插入排序对小区间进行排序
	}
	else
	{
		int keyi = PartSort(a, begin, end);
		QuickSort(a, begin, keyi - 1); // 递归小于区间
		QuickSort(a, keyi + 1, end); // 递归大于区间
	}
}

此处我们将阈值设为了10,也就是当递归划分数组的长度小于10时,就进行插入排序,这个阈值可以减少大约3-4层递归,最后一层递归就已经50%了,三四层递归可以节省80-90%的递归次数。

这个优化看似效率很高,但是其实现在的递归消耗并不高,哪怕节省了80-90%的递归次数,也许优化效果并没有那么好。


PartSort优化

三数取中

我们目前的快速排序仍然有一个缺点:对已经有序的数组适应性非常差

比如这样一个数组:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
我们对其进行快速排序,由于其已经有序,而我们每次选取key值又选的是第一个值,这就会导致一趟PartSort下来,小于区间为0,大于区间为n-1,接着我们递归到大于区间,不断循环上述过程:数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
那么这样对于一个n个数字的数组,我们就需要递归n层。这样实在太浪费资源了。
我们是否有办法,减少在有序情况或者接近有序的情况的递归层数?

于是三数取中出现了,三数取中是指,每次选取key值时:

1.先挑出最左侧下标值,最右侧下标值以及中间下标值(依据下标选出三个值)
2.选取三个值中的中间值

那么为什么三数取中可以减少递归的层数?

我们看一个实例:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
我先为大家解释此图:
每一层是一一层递归,红色值是本次递归的key值,蓝色是大于区,绿色是小于区。下一层递归是,蓝色区和绿色区分别递归,并重新筛选key值。

在选取第一个值作为key的图中,由于一直没有小于区出现,一次每层递归只能排序一次,而右侧由于选择了中间值作为key值,会尽可能保证大于区和小于区都存在,下一层递归就能处理更多的数据。

这样我们左侧递归了9层,而右侧只递归了4层。这就是三数取中带来的效率优化。一般来说,取第一个值最多需要递归n层,而三数取中一般为logn层。

我们先选一个三数取中的函数:

//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	//选begin end midi 的中位数
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else 
	{
		if (a[end] < a[midi])
			return midi;
		else if (a[end] > a[begin])
			return begin;
		else
			return end;
	}
}

这个函数就是实现三数取中:

1.先挑出最左侧下标值,最右侧下标值以及中间下标值(依据下标选出三个值)
2.选取三个值中的中间值

那么取出了中间值,要如何让快排将其作为key值?
我们先前的快排是把第一个值的位置作为key,如果取中间值作为key,那么这个值碍在中间,会不会影响left和right的移动判断?
所以我们选出中间数后,先将其与第一个值交换,把中间值放到第一个位置,防止它碍在中间。

代码如下:

//霍尔三数取中快排
int PartSort1(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);//将取出的中间值放在首位做key

	int left = begin, right = end;
	int keyi = begin;

	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[left], &a[keyi]);
	keyi = left;

	return keyi;
}

挖坑法

挖坑法是对霍尔版本的优化,霍尔版本中我们利用了left与right分别找大找小,然后将left与right的值进行交换。到了最后再把key和小于区的最后一个值交换。

挖坑法的思路是:

  1. 一开始将key值的位置空出来作为坑位
  2. 右边right找小,找到后直接放到key的位置(坑位),然后将此位置作为坑位
  3. 左边left找大,找到后放到坑位(刚刚右边空出来的位置),然后将此位置作为坑位
  4. 循环2,3步骤,直到leftright相遇
  5. 相遇后,将key值放到相遇点

图解如下:

数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言

代码如下:

// 快速排序挖坑法
int PartSort2(int* a, int begin, int end)
{
	//三数取中
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int key = a[begin];
	int hole = begin;

	while (begin < end)
	{
		//右边找小,填到右左边的坑
		while (begin < end && a[end] >= key)
		{
			end--;
		}

		a[hole] = a[end];//填坑
		hole = end;//换坑

		//左边找大,填到右边的坑
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}

		a[hole] = a[begin];//填坑
		hole = begin;//换坑
	}

	a[hole] = key;
	return hole;
}

代码解析如下:

  1. 首先,通过调用GetMidi函数,找到数组a中的三个元素(起始索引begin、终止索引end以及中间索引midi)的中值,并将中值与起始索引的元素交换位置。这样做是为了通过将中值作为基准值,降低快速排序的时间复杂度。

  1. 定义变量key为基准值,hole为开始时的坑的位置(即起始索引begin)。

  1. 进入一个循环,循环条件是开始索引小于结束索引。

  1. 在循环中,先从右向左扫描数组,找到第一个小于基准值的元素,将其填入坑中(即将a[end]赋值给a[hole]),然后将坑的位置更新为已填入元素的位置。

  1. 再从左向右扫描数组,找到第一个大于基准值的元素,将其填入右边的坑中(即将a[begin]赋值给a[hole]),然后将坑的位置更新为已填入元素的位置。

  1. 重复步骤4和步骤5,直到开始索引不小于结束索引为止。

  1. 将基准值填入最后一个坑中,此时基准值左边的元素都小于它,右边的元素都大于它。

  1. 返回基准值的索引。

前后指针法

回顾一下霍尔法以及挖坑法的基本思路,其用left与right来拓展小于区和大于区,最后将key放在了中间。
像这样:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言
这个过程中,right右边的是大于的区域,left左边的是小于的区域。
当我们同时确定了大于的区域和小于的区域,再把key值插入。

那么我们一定要同时维护大于区和小于区吗
不妨想一想,我们只维护一段小于区,把所有小于等于key的值都放进小于区,剩下的值不就是大于key的值了吗?
也就是说我们可以只维护一段区域,剩下的区域会自动生成,这就是前后指针法的思路。

先看代码,后解析。
代码如下:

// 快速排序前后指针法 
int PartSort3(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int prev = begin;
	int cur = prev + 1;

	int keyi = begin;

	while (cur <= end)
	{
		if (a[cur] < a[keyi])//避免自己和自己交换
			Swap(&a[++prev], &a[cur]);

		cur++;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}

思路:

使用一个prev指针维护一段小于区,用cur指针在数组中查找小于key的值,找到后放进小于区,并且++prev,意味着小于区扩展了一位。最后把key放到小于区的后面,此时大于区已经自动生成在了key的右侧

代码详解:

首先,通过调用GetMidi函数获取中间元素的下标midi,然后将中间元素与起始元素交换位置,将中间元素作为基准元素。


接下来,定义两个指针prevcurprev指向基准元素的位置,cur指向prev的下一个位置。
然后,定义一个keyi变量来保存基准元素的位置。


进入循环,在循环内部首先判断cur所指向的元素是否小于基准元素,并且判断prevcur是否相等,避免自己和自己交换。如果满足条件,则将prev指向的元素与cur指向的元素交换位置,prev向后移动一位(此时相当于小于区扩大了一位)。


循环结束后,将prev所指向的元素与基准元素交换位置,将基准元素放在正确的位置上,然后返回基准元素的位置keyi

这样就完成了一次快速排序的分割操作。

示意图如下:
数据结构与算法:快速排序,数据结构,算法,排序算法,快速排序,C语言

要注意,由于前两次交换,prev和cur还没有拉开差距,也就是说没有发现比key大的值,所以是自己和自己交换。


非递归法

那么也没有不递归的快速排序法呢?
也是有的,我们在递归排序时利用的思路是,每次递归key左侧的小于区以及右侧的大于区,把这个区域进行一次PartSort。

也就是说我们要想办法把下一次需要单趟排序的范围存储下来
这里可以用到一个栈结构,每次单趟排序,把排序的区间从栈中取出来,排序完后根据key划分区域,再把需要排序的子区域入栈。

代码如下:
此处不对栈这个结构的实现做详解,受C语言限制,这个栈需要手撕。

// 快速排序 非递归实现
void QuickSortNonR(int* a, int begin, int end)
{
	Stack s;
	StackInit(&s);//初始化栈
	StackPush(&s, end);//入栈数组尾部
	StackPush(&s, begin);//入栈数组头部

	while (!StackEmpty(&s))
	{
		//取出栈顶的左右元素,作为本次排序的范围
		int left = StackTop(&s);
		StackPop(&s);
		int right = StackTop(&s);
		StackPop(&s);

		int keyi = PartSort(a, left, right);//一趟排序
		if (left < keyi - 1)//将本次排序的子区间入栈
		{
			StackPush(&s, keyi - 1);
			StackPush(&s, left);
		}

		if (keyi + 1 < right)//将本次排序的子区间入栈
		{
			StackPush(&s, right);
			StackPush(&s, keyi + 1);
		}
	}
	StackDestroy(&s);//销毁栈
}

下面是对代码的详细解释:文章来源地址https://www.toymoban.com/news/detail-791568.html

  1. 定义了一个函数QuickSortNonR,参数为待排序数组a的起始位置begin和结束位置end

  1. 初始化一个栈s,用于保存待排序区间。调用StackInit函数初始化栈。

  1. 将数组的起始位置和结束位置分别入栈。即StackPush(&s, end)StackPush(&s, begin)

  1. 进入循环,判断栈是否为空。如果栈不为空,则继续执行排序操作;否则结束排序。

  1. 在循环内部,首先从栈顶取出左右边界,即leftright。分别将它们出栈。

  1. 调用PartSort函数进行一趟排序,将数组a中left到right之间的元素按照某个基准值进行划分,返回基准值的下标。

  1. 如果左边区间的起始位置left小于基准值的下标keyi-1,则将该区间入栈。即StackPush(&s, keyi-1)StackPush(&s, left)

  1. 如果右边区间的结束位置keyi+1小于right,则将该区间入栈。即StackPush(&s, right)StackPush(&s, keyi+1)

  1. 回到步骤5,继续下一次排序操作。

  1. 当栈为空时,表示所有的子区间都已经排序完成,结束循环。

  1. 调用StackDestroy函数销毁栈s,释放内存。

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

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

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

相关文章

  • 数据结构与算法之快速排序

    快速排序 (Quick Sort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数

    2024年02月10日
    浏览(43)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(54)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(55)
  • 【数据结构】—从冒泡排序丝滑过度快速排序(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波:靴の花火—ヨルシカ            

    2024年02月08日
    浏览(39)
  • 【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现 好了废话不多说,开

    2024年02月08日
    浏览(46)
  • 【数据结构与算法】快速排序的三种实现方法

      目录 一.基本思想 二.Hoare法 动态演示 三.挖坑法 动态演示 四.前后指针法 动态演示 五.快速排序优化 随机下标交换法 三路取中法 六.快速排序的特性 任取待排序元素序列中的某元素作为 基准值 ,按照该排序码将待排序集合 分割成两子序列 , 左子序列中所有元素均小于基

    2023年04月09日
    浏览(65)
  • 【数据结构与算法】快速排序的非递归实现方法

      目录 一.前言 二.非递归实现 如果数据量过大的话,不断递归就会出现 栈溢出 的现象,这个时候你的代码是没问题的,但就是跑不起来,这个时候就要 把递归改成非递归 。 一般有两种改法: 1.直接改,利用循环等; 2.借助栈的辅助。 而快速排序的非递归实现方法就需要

    2023年04月17日
    浏览(55)
  • 【数据结构】详解七大排序算法(直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序)

    1、基本思想    把待排序的数按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所以的记录插入完为止,得到一个新的有序序列。    实际中我们玩扑克牌时,就用到了插入排序的思想 基本步骤:    当插入第i个元素时,前面的arr[0]、arr[2]…arr

    2024年02月04日
    浏览(76)
  • 数据结构——排序算法(C语言)

    本篇将详细讲一下以下排序算法: 直接插入排序 希尔排序 选择排序 快速排序 归并排序 计数排序 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某写的大小,按照递增或递减0排列起来的操作。 稳定性的概念 假定在待排序的记录序列中,存在多个

    2024年02月08日
    浏览(66)
  • 数据结构和算法——快速排序(算法概述、选主元、子集划分、小规模数据的处理、算法实现)

    目录 算法概述 图示 伪代码 选主元 子集划分 小规模数据的处理 算法实现 快速排序和归并排序有一些相似,都是用到了分而治之的思想:   通过初步的认识,我们能够知道快速排序算法最好的情况应该是: 每次都正好中分 ,即每次选主元都为元素的中位数的位置。 最好情

    2024年02月15日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包