手撕七大排序 三

快速排序（一次排序）

一. 基本思想

当然这里也是目前为止我们能够接触到的最快的算法

图形表示如下

我们将最左边的值称为 “KEY 值”

这里我们从右边开始 依次往左遍历 如果找到小于KEY下标数 就交换它们的值

并且将key的下标赋值给right

之后我们从左边开始 依次往右遍历 如果找到大于KEY下标的数 就交换它们的值

并且将key的下标赋值给left

我们想想看 什么时候结束呢？

当然是left < right 的时候

二. 代码表示

我们这里有代码表示如下

int quicksort1(int* arr, int left, int right)
{
	// assert(arr)
	assert(arr);

	// 设置左右两个小人 
	int keyi = left;

	int tmp = 0;
	

	while (left<right)
	{
		// 右边的士兵先开始走 直到遇到小于key值 我们交换它们的位置以及下标
		while (left<right  && arr[right] >= arr[keyi])
		{
			right--;
		}

		tmp = arr[right];
		arr[right] = arr[keyi];
		arr[keyi] = tmp;
		keyi = right;


		// 右边的士兵走完了 然后左边的士兵开始走
		while (left < right && arr[left]<=arr[keyi])
		{
			left  ;
		}

		tmp = arr[left];
		arr[left] = arr[keyi];
		arr[keyi] = tmp;
		keyi = left;
	}


	return keyi;

}

我们来看看结果是什么样子的

快速排序（整体排序）

一. 基本思路

既然我们每次可以将整个数组可以分成两个部分

我们可以将数组的左边和右边继续进行快速排序

这里我们进行递归

二. 递归思路

既然我们已经决定了要进行递归了

那么我们想想看极限条件是什么？

是不是要左值大于等于右值的时候 只剩下一个值了 是不是肯定有序了

所以说有极限条件如下

	// assert
	assert(arr);

	// 考虑边界条件 
	if (left>=right)
	{
		return;
	}

那么我们接下来就可以考虑左右两边怎么排了

我们来看看我们的数组

是不是从左到右分成三个部分

分别是

left~keyi-1；
keyi；
keyi 1~right；

所以说我们就可以有以下代码

	quicksort(arr, 0, keyi - 1);
	quicksort(arr, keyi   1,right);

之后我们来试试 整体排序的效果咋样

可以完成

优化

我们假设 排序的数组就是一个有序的

	quicksort(arr, 0, keyi - 1);
	quicksort(arr, keyi   1,right);

那么我们这里左边就排完了 开始排右边

像这样子

那这样是不是我们的算法就变得很复杂了啊

到这里的时间复杂度就变成了O（N^2）

那么针对有序数组的这个问题 我们能不能做出一个优化呢？

答案是有的

那就是三数取中

我们找到最左边 左右边 还有中间三个数中的中间值

然后让这个值和left交换

之后再进行排序 是不是就能变成很优了啊

那么我们这里再来写个函数 三数取中

int GetMinIndex(int* arr, int left, int right)
{
	// assert
	assert(arr);
	int mid = (left   right) / 2;
	// 返回其中的中间值
	if (arr[left]>=arr[right])
	{
		if (arr[right]>=arr[mid])
		{
			return mid;
		}
		else if (arr[mid] >= arr[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else  // arr[right] > arr[left]
	{
		if (arr[left]>arr[mid])
		{
			return left;
		}
		else if (arr[mid] > arr[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}



}

之后再来写进函数里面

void quicksort(int* arr, int left, int right)
{
	// assert
	assert(arr);

	// 三数取中
	int mid = GetMinIndex(arr, left, right);
	int tmp = 0;

	// 改变key值 
	tmp = arr[left];
	arr[left] = arr[mid];
	arr[mid] = tmp;


	// 考虑边界条件 
	if (left>=right)
	{
		return;
	}

	// 如果不满足边界条件开始排序了
	int keyi = quicksort1(arr, left, right);


	// 开始排序数组的左边和右边
	
	quicksort(arr, 0, keyi - 1);
	quicksort(arr, keyi   1,right);

}

我们来看看运行结果

可以完美运行

双指针法实现一趟快排

我们这里首先设置两个指针

一个pre 指向第一个元素 也就是key值

一个cur指向最后的元素

类似这样子

比如说 cur走到了2 然后2小于key值

这个时候pre就得 然后交换cur和pre指向的值

当cur走到7 9 下面的时候就直接 不做任何操作

如果说cur的坐标大于 数组的元素-1的时候结束循环

这个时候我们再将prev和key值交换一下就可以了

最后结果表示如下

快排的非递归实现

这个时候就要用到我们的数据结构 栈了

我们首先先将我们需要排序的数组左右下标传递进去

之后我们开始进行一个循环操作

如果栈不为空 我们就执行这个循环

首先我们以这个数组的左边为例

通过第一趟排序 可以将整个数组分为三个部分

我们将中值设置为div

那么左边就是

left~ div-1

右边就是

div 1~right

那么到这里我们的终止条件就很好判断了

left<div-1

div 1<right

那么这里我们先将 0 ~ 9 出栈

之后将它分割的两边

6~9

0~4 依次进栈

如图

再之后我们将0~4进行出栈

判断有没有达到边界条件再进行压栈

整体代码表示如下

不吝赐教 在评论区或者私信指正 博主一定及时修正

那么大家下期再见咯

这篇好文章是转载于：学新通技术网