数据结构——lesson11排序之快速排序

03-31 1066阅读

💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

💥个人主页：大耳朵土土垚的博客

💥 所属专栏：数据结构学习笔记、排序算法合集

💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

前面我们学习过五种排序——直接插入排序、希尔排序、直接选择排序、堆排序和冒泡排序，今天我们就来学习交换排序的第二种——快速排序。

1.快速排序（递归版）

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值key，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复（这里使用递归来重复，非递归版本将在后续讲解）该过程，直到所有元素都排列在相应位置上为止。

那怎么实现左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值呢？

下面将介绍三个方法实现，分别是Hoare版本实现、挖坑法和前后指针法；

1.1Hoare版本实现

①选定一个基准值key（假设每次都为最左边的数），定义左右下标left，right；

②right先走从右往左找到小于key的值停在那里；

③左边再开始从左往右走直到停在大于key的值上，然后交换左右两个值；

④接着右边继续往左走继续找小于key的值，找到后左边往右走找大于key的值；

⑤直到左右left和right相遇，也就是left = right，此时该位置的值一定小于key（等学完Hoare后再来分析），再将该值与key交换即可；

🥳🥳这样key左边都是小于它的，右边都是大于它的，在整个序列中的位置就确定好了，接下来我们按照上述方法分别实现key左边的序列和右边的序列有序即可；

图示如下：

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	if (left >= right)//如果left一开始就小于right就不需要继续往下了
		return 0;
	int keyi = left;
	int key = a[left];
	while (left  key)
			{
				Swap(&a[left], &a[right]);
				break;
			}
			left++;
		}
		right--;
	}
	//当left=right时此时一定a[left] = right)//递归结束条件
		return;
	int keyi = PartSort1(a, left, right);
	QuickSort(a, left, keyi-1);//递归左右序列
	QuickSort(a, keyi+1, right);
}

结果如下：

这里注意第二层while循环时也要讲条件left int tmp = 0; tmp = *a; *a = *b; *b = tmp; } int hole = left; int key = a[hole]; while (left

注意✨✨：

①这里嵌套的while循环中也要写条件——left= key，a[left] right跳出循环；

（3）结束循环后prev的位置就是key合适的位置，交换两个位置的值并返回该位置的下标；

（4）然后再利用递归来实现完整序列的排序即可🥳🥳

图示如下：

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int key = a[left];
	int cur = left+1;
	int prev = left;
	while (cur 
	//如果a[cur]
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[left]);
	return prev;
}
//递归实现
void QuickSort(int* a, int left, int right)
{
	if (left = right)//递归结束条件
		return;
	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi-1);//递归调用左边
	QuickSort(a, keyi+1, right);//递归调用右边
}

	//定义和初始化栈
	Stack ST;
	StackInit(&ST);
	//将整个序列入栈
	StackPush(&ST, right);
	StackPush(&ST, left);
	//当栈不为空时
	while (!StackEmpty(&ST))
	{
	//取栈顶的两个元素作为左右下标
		int left = StackTop(&ST);
		StackPop(&ST);
		int right = StackTop(&ST);
		StackPop(&ST);
		//利用前面讲过的三种方法任意一种来对取出的左右下标组成的序列排序
		int keyi = PartSort1(a, left, right);
		//如果能够分割左右序列就让它们入栈
		if (keyi + 1  a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

获得中间值的下标后直接与最左边的数交换即可（以Hoare版本为例）：

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	if (left >= right)//如果left一开始就小于right就不需要继续往下了
		return 0;
	int midi = GetMidIndex(a,left,right);
	//与left的值交换即可，其他不变
	Swap(&a[left],&a[midi]);
	int keyi = left;
	int key = a[left];
	while (left  key)
			{
				Swap(&a[left], &a[right]);
				break;
			}
			left++;
		}
		right--;
	}
	//当left=right时此时一定a[left] = right)//递归结束条件
		return;
	int keyi = PartSort1(a, left, right);
	QuickSort(a, left, keyi-1);//递归左右序列
	QuickSort(a, keyi+1, right);
}

其他两种方法和上述一致🥳🥳🥳