手撕七大排序(三)

快速排序（一次排序）

一. 基本思想

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

图形表示如下

 

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

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

并且将key的下标赋值给right

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

并且将key的下标赋值给left

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

当然是left < right 的时候

二. 代码表示

我们这里有代码表示如下

int PartSort1(int* a, int left, int right)
{
	
	//三数取中
	int midi = GetmidNumi(a, left, right);
	if (midi != left)
		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]);
	}
	//left和right相遇后 交换keyi的值和相遇点的值
	Swap(&a[keyi], &a[left]);
	//更新坐标
	keyi = left;
 
	return keyi;
}

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

快速排序（整体排序）

一. 基本思路

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

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

这里我们进行递归

二. 递归思路

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

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

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

所以说有极限条件如下

if (left >= right)
	{
		return;
	}

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

我们来看看我们的数组

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

分别是

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

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

//区间 [begin,keyi-1] keyi [keyi+1,end]
	QuickSort1(a,begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);

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

可以完成

优化

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

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

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

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

答案是有的

那就是三数取中

 

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

然后让这个值和left交换

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

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

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

之后再来写进函数里面

void QuickSort1(int* a, int left,int right)
{
	//返回条件
	if (left >= right)
	{
		return;
	}
	//有序的时候 时间复杂度O(N^2)优化
	//随机选key
	/*int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);*/
 
	//三数取中
	int midi = GetmidNumi(a, left, right);
	if (midi != left)
		Swap(&a[left], &a[midi]);
 
 
	int begin = left; int end = 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]);
	}
	//left和right相遇后 交换keyi的值和相遇点的值
	Swap(&a[keyi], &a[left]);
	//更新坐标
	keyi = left;
	//递归
	//区间 [begin,keyi-1] keyi [keyi+1,end]
	QuickSort1(a,begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}

我们来看看运行结果

可以完美运行

双指针法实现一趟快排 

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

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

一个cur指向最后的元素

类似这样子

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

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

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

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

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

最后结果表示如下

//前后指针法
int PartSort3(int* a, int left, int right)
{
	//三数取中
	int midi = GetmidNumi(a, left, right);
	if (midi != left)
		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[cur], &a[prev]);
		}
		++cur;
	}
 
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
 
	return keyi;
}
 
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//递归
	int keyi = PartSort1(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right - 1);
}

  以上便是本文所有内容，如有错误请各位大佬不吝赐教，感谢留言