快速排序算法(数据结构)

本文主要是介绍快速排序算法(数据结构)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

快速排序的基本思想：任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivotkey，即枢轴元素。将所有比枢轴元素小的放在其左边，将所有比它大的放在其右边，形成左右两个子表，然后对左右两个子表再按照前面的算法进行排序(递归)，直到每个子表的元素只剩下一个。

举例说明一下：

arr 为 [39 , 28 , 55 , 87 , 66 , 3 ,17 ,39*]为了区别两个相同元素，将最后一个加上 * 。
初始状态如下图：

定义一枢轴元素pivotkey，初始化为第一个元素的值，即39；
查询左边的元素的变量为left即low，初始值为第一个元素的索引,0;
查询右边的元素的变量为right即hight，初始值为第一个元素的索引,7。
如下图：

演示第一轮排序过程
从右边开始，从右边找到一个比枢轴元素小的，如果没找到right即high一直自减1；

然后把当前left即low所在元素赋值为该值；
这里right即hight所指元素并没有空，只是为了好演示，设置为空（下同）；

然后从左边开始找一个比枢轴元素pivotkey大的元素；如果没找到left一直自增1；

将当前right所指元素设为该值；

然后从右边找到一个比枢轴元素小的，如果没找到right一直自减1；

将当前left所指元素设为该值；

然后从左边开始找一个比枢轴元素pivotkey大的元素；如果没找到left一直自增1；

将当前right所指元素设为该值；

然后从右边找到一个比枢轴元素小的，如果没找到right一直自减1；

这时left和right相遇了，将枢轴元素赋值给当前位置。

第一轮排序动态过程：

然后将数组分成了[17,28,3] 与 [66, 87, 55, 39*]两部分,再对这两部分进行上述环节即可,反反复复,直到只剩下一个元素。

排序全过程

完整代码如下：

#include<bits/stdc++.h> //万能头
using namespace std;
const int Max=100;
//顺序表的定义
typedef struct 
{
	int key;
}ordNode;
typedef struct
{
	ordNode a[Max];
	int len;
}Sqlist;
//对顺序表L中的子表r[low..high]进行一趟排序,返回枢轴位置
int Partition(Sqlist &L,int low,int high)
{
	L.a[0]=L.a[low];  //用子表的第一个记录做枢轴记录
	int pivotkey=L.a[low].key;  //枢轴记录关键字记录到pivotkey中
	while(low<high)
	{
		while(low<high&&L.a[high].key>=pivotkey)
			high--;   
		L.a[low]=L.a[high]; //将比枢轴记录小的记录移到低端
		while(low<high&&L.a[low].key<=pivotkey)
			low++;
		L.a[high]=L.a[low];  //将比枢轴记录大的记录移到高端
	}
	L.a[low]=L.a[0];//枢轴记录到位 
	return low;  //返回枢轴位置 
}
//调用前置初值:low=1, high=L.length
void QSort(Sqlist &L,int low,int high)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(L,low,high);
		QSort(L,low,pivotloc-1);  //递归调用
		QSort(L,pivotloc+1,high);
	}
}
//对顺序表L做快速排序
void QuickSort(Sqlist &L)
{
	QSort(L,1,L.len);
}
int main(){
	Sqlist L;
	printf("请输入待排序数的个数:");
	scanf("%d",&L.len);
	printf("请输入待排序的数:");
	for(int i=1;i<=L.len;i++)
		scanf("%d",&L.a[i]);
	int pivotkey=L.a[1].key;
	QSort(L , L.a[1].key , L.a[L.len].key);
	QuickSort(L);
	printf("请输出排好序的数列:");
	for(int i=1;i<=L.len;i++)
		printf("%d ",L.a[i]);
	return 0;
}

测试用例如下：

请输入待排序数的个数:8
请输入待排序的数:39 28 55 87 66 3 17 39
请输出排好序的数列:3 17 28 39 39 55 66 87

稳定性分析： 

如下面的数组，相同元素用 * 标出[ 3 , 4 , 2, 2* ]
第一次排序为[2* , 2, 3, 4]
第二次为[2* , 2 , 3 , 4]
相对顺序发生了变化，所以是不稳定的。 

 图片讲解参考详解快速排序算法 - code随笔 - 博客园

 希望可以帮到你哦！^_^

这篇关于快速排序算法(数据结构)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！