排序算法(2)、经典算法(7):快速排序算法

2017-01-03 07:40:21来源:CSDN作者:qcyfred人点击

概述


快速排序,确实是一种排序算法,归到排序算法类别下。

又因为确实是经典算法,也就归到经典算法类别下了。

时间复杂度,最好为O(n),最差为O(n^2),平均为O(nlog(n))。


在快速排序算法中,使用了分治策略。首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束。
步骤如下:
在序列中选择一个关键元素做为轴;
对序列进行重新排序,将比轴小的元素移到轴的前边,比轴大的元素移动到轴的后面。在进行划分之后,轴便在它最终的位置上;
递归地对两个子序列进行重新排序:含有较小元素的子序列和含有较大元素的子序列。


代码实现


多增加一个数组


快速排序的函数。
void quickSort(int * A, int low, int high) {	// 当low>=high的时候,结束	// 当low<high的时候,继续排序	if (low < high)	{		int midIdx = FindMidIdx(A,low,high); // 排序,并找到中轴元素的下标		quickSort(A,low,midIdx-1); // 对左边的进行排序		quickSort(A,midIdx+1,high); //对右边的进行排序	}}
对于quickSort这个函数需要说明的是,先调用找中轴、排序的函数。把一个长的序列分成两个小的。左边的都比中轴小,右边的都不比中轴小。假设左右两边都是排好了的序列,那么整个序列也排列好了。于是再对左边、右边的序列分别再排。
排序、找中轴元素的下标的函数。
int FindMidIdx(int * A, int low, int high) {	int lowReserve = low; // 保存要对A的一部分排序的范围	// 先开一个临时数组B	int N = high - low + 1; // B的大小	int * B = new int[N];	int j = 0; // 为了填充B,造出来的下标 B里的low	int k = N-1; // B里的high	// 找中轴变量	int pivor = A[low]; // A的low是中轴	low++; // 从第二个开始起,开始找	while (low<=high) // 从左往右扫	{		int temp = A[low];		if (temp<pivor)		{			B[j] = temp;			j++;		} else {			B[k] = temp;			k--;		}		low++;	}	B[j] = pivor;	int midIdx = j + lowReserve; // A中的中间位置 	for (int i = 0;i<N;i++) { 	 	A[lowReserve+i] = B[i]; 	}	delete[] B;	return midIdx;}
还是那句话,用了更多的空间,换了简单的思维。开了一个临时数组B。每次找中轴,都是找的一个数组中第1个元素。从第二个开始扫描,直到末尾。把比较后的结果都放到B里面,最后把中轴变量放入B的“中间”位置,在代码中是用j来记录的。最后,把B中的所有元素又赋值给A对应的部分。需要注意的是,B是从0开始,到这次需要排序的数组的大小-1。而A是原始的数组。大小一直不变。所以用下标访问的时候,访问B的下标和访问A的下标,写法是不同的 。
整个程序是这样的。
#include <iostream>using namespace std;const int global_N = 10;int FindMidIdx(int * A, int low, int high) {	int lowReserve = low; // 保存要对A的一部分排序的范围	int highReserve = high;	// 先开一个临时数组B	int N = high - low + 1; // B的大小	int * B = new int[N];	int j = 0; // 为了填充B,造出来的下标 B里的low	int k = N-1; // B里的high	// 找中轴变量	int pivor = A[low]; // A的low是中轴	low++; // 从第二个开始起,开始找	while (low<=high) // 从左往右扫	{		int temp = A[low];		if (temp<pivor)		{			B[j] = temp;			j++;		} else {			B[k] = temp;			k--;		}		low++;	}	B[j] = pivor;	int midIdx = j + lowReserve; // A中的中间位置 	for (int i = 0;i<N;i++) { 	 	A[lowReserve+i] = B[i]; 	}	delete[] B;	return midIdx;}void quickSort(int * A, int low, int high) {	// 当low>=high的时候,结束	// 当low<high的时候,继续排序	if (low < high)	{		int midIdx = FindMidIdx(A,low,high); // 排序,并找到中轴元素的下标				for (int i = 0;i<global_N;i++)		{			cout<<A[i]<<" ";		}		cout<<"/n";		quickSort(A,low,midIdx-1); // 对左边的进行排序		quickSort(A,midIdx+1,high); //对右边的进行排序	}}int main() {	int A[global_N] = {4,2,66,88,3,1,7,49,1,10};	cout<<"原始数据"<<endl;	for (int i = 0;i<global_N;i++)	{		cout<<A[i]<<" ";	}	cout<<"/n";	cout<<"开始快速排序"<<endl;	quickSort(A,0,global_N-1);	system("pause");	return 0;}
原始数据
4 2 66 88 3 1 7 49 1 10
开始快速排序
2 3 1 1 4 10 49 7 88 66
1 1 2 3 4 10 49 7 88 66
1 1 2 3 4 10 49 7 88 66
1 1 2 3 4 7 10 66 88 49
1 1 2 3 4 7 10 49 66 88

有技巧的排序


如果在findMidIdx里面,不开辟临时数组B,就更有技巧了。假设把A的第一个元素当作中轴变量pivor,就从A的右往左搜索,直到找到比pivor小的,放在low的位置,low++,再从左往右找,直到结束。
int findMidIdx(int A[], int low, int high) {	int pivor = A[low]; // 第一个元素是pivor	while (low < high)	{		// 从右往左找		while(A[high]>=pivor && low<high)		{			high--; // 继续往左走		} 		// 直到找到比pivor小的了,应该放在左边了		A[low] = A[high];		// low++; // 千万不能有这句话!		// 从左往右找		while(A[low]<pivor && low<high)		{			low++;		}		A[high] = A[low];		// high--;	// 也千万不能有这句话!	}	int midIdx = low;	A[midIdx] = pivor;	return midIdx;}
quickSort函数与上面的一样。当在main中对以下这个数组排序时int A[g_N] = {4,2,66,88,3,1,7,49,1,10};
quickSort(A,0,g_N-1);结果1 2 1 3 4 88 7 49 66 10
1 2 1 3 4 88 7 49 66 10
1 1 2 3 4 88 7 49 66 10
1 1 2 3 4 10 7 49 66 88
1 1 2 3 4 7 10 49 66 88
1 1 2 3 4 7 10 49 66 88代码比第一个版本要简洁很多。非常有技巧了。
注意,在赋值之后,low++和high--都是不能写的。如果这样写了以后,可能会跳过一些数据。同时,在while里从右往左或从左往右搜索时,当low>=high,都必须是结束条件。low和high的变换,让while去控制就好了。

选一个更好的pivor


因为pivor选择的好坏,就直接影响到排序的效率。所以希望每次挑选的pivor都是一组数据中在中间位置的数。有一个在一堆数中,找出第K大的元素的算法。递归调用。和findMidIdx的道理差不多。



最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台