快速排序

大忽悠爱学习

发布于 2022-05-05 19:07:50

2570

文章被收录于专栏：c++与qt学习c++与qt学习

快速排序对冒泡排序的改进：

定义：

选取轴值的方法：

再了解快速排序前，先来看一下交换排序的原理

解决方法：

注意：这里的轴值是不断移动的 伪代码：

图解：

每一次while循环如果是正常情况，都会进行两次交换操作，此时第一次大的while循环结束，进入第二次的两次交换操作

问题：获取轴值后，如何对分割得到的两个子序列进行处理？ 解决方法： 对分割得到的两个子序列递归的进行快速排序

如何判断快速排序已经结束

代码

#include<iostream>
using namespace std;
void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}
//交换排序---每一次返回当前键值的在数组中的下标
int swap_sort(int r[],int begin,int end)
{
	//我们设置begin位置的元素为键值
	int i = begin;
	int j = end ;
	//当退出循环时，i==j，i和j都指向当前键值所在下标位置
	while (i < j)
	{
		while (i < j && r[i] <= r[j])
		{
			j--;
		}
		if (i < j)
		{
			swap(r[i],r[j]);//交换完后，r[j]的位置存储的是键值
			i++;//调整i的位置
		}
		while (i<j && r[j]>=r[i])
		{
			i++;
		}
		if (i < j)
		{
			swap(r[i], r[j]);//交换完后，r[i]的位置存储的是键值
			j--;//调整j的位置
		}
	}
	return i;
}
//快速排序:end填入的是数组中最后一个元素的下标
void quick_sort(int r[],int begin, int end)
{
	int pos = 0;//接收当前键值的在数组中下标的位置
	if (begin < end)
	{
		pos = swap_sort(r, begin, end);
		quick_sort(r, begin, pos - 1);
		quick_sort(r, pos + 1, end);
	}
}
int main()
{
	int r[10] = { 5,4,3,6,2,1,8,9,10 };
	quick_sort(r,0,9);
	//打印数组
	for (int i = 0; i < 10; i++)
		cout << r[i] << endl;
	system("pause");
	return 0;
}