排序算法：快速排序(递归)

文章目录

• • 一、创始人托尼·霍尔的快速排序
  • 二、挖坑法
  • 三、前后指针法

所属专栏:C++初阶
引言：这里所说的快速排序有三种，第一种是霍尔大佬自创的，还有一种叫做挖坑法，另外一种叫前后指针法

一、创始人托尼·霍尔的快速排序

1.这里我们先把中间值定位数组中的首元素的值，设为key变量，大于key的放右边，小于key的放左边
2.定义left为从数组0下标开始找大于key的数，如果小于key，left就向前走一步，定义right从数组下标为n-1的位置，从右向左找小于key的数，从最右边的数开始，如果大于key，right就向后走一步
3.这里我们还要判断谁先和谁相遇（也就是谁走到相等的位置，而那个人是停止的)
如果left先走，那么left与right相遇的地方就是left走遇到right(相遇的地方的值是大于key的)
如果right先走，那么left与right相遇的地方就是right走遇到left(相遇的地方的值是小于key的)

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* p1,int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
int QuickSort(int left,int right,int* a)
{
	int keyi = left;
	int end = right;
	//判断谁先走的问题，我们把大于a[keyi]的放左边
	//小于a[keyi]的放右边，等于的话就不管
	//这里要判断谁先走的问题
	//如果left先走，那么left与right相遇的地方就是left走遇到right
	//如果right先走，那么left与right相遇的地方就是right走遇到left
	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]);
	return left;
}

void TestSort(int* a, int begin,int end)
{
	if (begin >= end)//当只有一个数时，不用排序，直接返回
		return;
	//霍尔大佬的排序
	int keyi = QuickSort(begin, end ,a);
	
	TestSort(a, begin,keyi-1);
	TestSort(a, keyi+1,end);
}
int main()
{
	int a[] = {6,1,2,7,9,3,4,5,10,8};
	TestSort(a, 0, sizeof(a) / sizeof(int) - 1);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	printf("%d ", a[i]);
	return 0;
}

这里的排序就像是二叉树的遍历，大家可以参考前面的代码
排序区间【begin，keyi-1】keyi 【keyi+1,end】（keyi为中间值，已经排好序了）

二、挖坑法

步骤如下：
1.这里的挖坑（从a[left]开始是第一个坑，然后right寻找小于key（a[left]）的值，找到了这个坑就跑到a[right]去了，同时要交换一下下标hole=right）
2.然后就从left开始找大于key的值，找到了那么就是第二个坑，hole就跳到了left的位置，hole=left
3.以此类推，直到left=right的时候，此时的坑就在left=right的地方，然后a[hole]=key（此时的key就是中间值不需要排了）

int QuickSort(int left,int right,int* a)
{
	int key = a[left];
	int end = right;
	int hole = left;
	while (left < right)
	{
		//右边找小
		while(left < right && a[right] >= key)
			right--;
		a[hole] = a[right];
		hole = right;
		//左边找大
		while(left < right && a[left] <key)
			left++;
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return left;
}

三、前后指针法

步骤如下：
1.首先定义一个前指针prev，和一个后指针cur
2.然后cur先向前走，如果大于key，那么继续向前走，prev，不向前走，如果小于key，那么prev和cur同时向前走（总的来说cur一直是向前走的，prev只在cur位置小于key才向前走的）
3.以此类推，直到cur>end就不走了

int QuickSort3(int left, int right, int* a)
{
	int key = a[left];
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] <= key && ++prev != cur)
			Swap(&a[prev],&a[cur]);
		cur++;
	}
	//最后这里的a[prev]一定是一个小于key的值，
	//所以需要和key这个中间值换一下，以达到key已经排好序
	Swap(&a[prev], &a[left]);
	return prev;
}