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

时间:2024-03-18 21:19:47

文章目录

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

在这里插入图片描述
所属专栏: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;
}

在这里插入图片描述