三种快速排序算法的实现(递归算法、非递归算法、三路划分快速排序)

时间:2022-03-28 04:12:49

快速排序的三个步骤:

1、分解:将数组A[l...r]划分成两个(可能空)子数组A[l...p-1]和A[p+1...r],使得A[l...p-1]中的每个元素都小于等于A(p),而且,小于等于A[p+1...r]中的元素。下标p也在这个划分过程中计算。

2、解决:通过递归调用快速排序,对数组A[l...p-1]和A[p+1...r]排序。

3、合并:因为两个子数组时就地排序,将它们的合并并不需要操作,整个数组A[l..r]已经排序。


1.快速排序的基础实现:

QUICKSORT(A, l, r)

if l < r

   then q = PARTION(A, l, r)

        QUICKSORT(A, l, p-1)

        QUICKSORT(A, p+1, r)

两路PARTION算法主要思想:

move from left to find an element that is not less

move from right to find an element that is not greater

stop if pointers have crossed

exchange


实现代码:

int partition(double* a, int left, int right)
{
	double x = a[right];
	int i = left-1, j = right;
	for (;;)
	{
		while(a[++i] < x) { }
		while(a[--j] > x) { if(j==left) break;}
		if(i < j) 
			swap(a[i], a[j]);
		else break;
	}
	swap(a[i],a[right]);
	return i;
}

void quickSort1(double* a, int left, int right)
{
	if (left<right)
	{
		int p = partition(a, left, right);

		quickSort1(a, left, p-1);
		quickSort1(a, p+1, right);
	}
}


2.非递归算法:其实就是手动利用栈来存储每次分块快排的起始点,栈非空时循环获取中轴入栈。

实现代码:

void quickSort2(double* a, int left, int right)
{
	stack<int> t;
	if(left<right)
	{
		int p = partition(a, left, right);

		if (p-1>left)
		{
			t.push(left);
			t.push(p-1);
		}
		if (p+1<right)
		{
			t.push(p+1);
			t.push(right);
		}

		while(!t.empty())
		{
			int r = t.top();
			t.pop();
			int l = t.top();
			t.pop();

			p = partition(a, l, r);

			if (p-1>l)
			{
				t.push(l);
				t.push(p-1);
			}
			if (p+1<r)
			{
				t.push(p+1);
				t.push(r);
			}

		}
	}
}

3.三路划分快速排序算法:

三种快速排序算法的实现(递归算法、非递归算法、三路划分快速排序)

实现代码:

void quickSort3Way(double a[], int left, int right)
{
	if(left < right)
	{
		double x = a[right];
		int i = left-1, j = right, p = left-1, q = right;
		for (;;)
		{
			while (a[++i] < x) {}
			while (a[--j] > x) {if(j==left) break;}
			if(i < j)
			{
				swap(a[i], a[j]);
				if (a[i] == x) {p++; swap(a[p], a[i]);}
				if (a[j] == x) {q--; swap(a[q], a[j]);}
			}
			else break;
		}
		swap(a[i], a[right]); j = i-1; i=i+1;
		for (int k=left; k<=p; k++, j--) swap(a[k], a[j]);
		for (int k=right-1; k>=q; k--, i++) swap(a[i], a[k]);

		quickSort3Way(a, left, j);
		quickSort3Way(a, i, right);
	}
}

4.测试代码:

#include <iostream>
#include <stack>
#include <ctime>
using namespace std;

// 产生(a,b)范围内的num个随机数
double* CreateRand(double a, double b, int num)
{
	double *c;
	c = new double[num];
	srand((unsigned int)time(NULL));
	for (int i=0; i<num; i++)
		c[i] = (b-a)*(double)rand()/RAND_MAX + a;
	return c;
}

// 两路划分,获取中轴,轴左边数小于轴,轴右边数大于轴
double partition(double* a, int left, int right)
{
	...
}

// 1.递归快速排序,利用两路划分
void quickSort1(double* a, int left, int right)
{
	...
}

// 2.非递归快速排序,手动利用栈来存储每次分块快排的起始点,栈非空时循环获取中轴入栈
void quickSort2(double* a, int left, int right)
{
	...
}

// 3.利用三路划分实现递归快速排序
void quickSort3Way(double a[], int left, int right)
{
	...
}

void main()
{
	double *a, *b, *c;
	int k=10000000;
	time_t start,end;

	a = CreateRand(0,1,k);
	b = CreateRand(0,1,k);
	c = CreateRand(0,1,k);

	start = clock();
	quickSort1(a,0,k-1);
	end = clock();
	cout<<"1.recursive "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"<<endl;

	start = clock();
	quickSort2(b,0,k-1);
	end = clock();
	cout<<"2.non-recursive "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"<<endl;

	start = clock();
	quickSort3Way(c,0,k-1);
	end = clock();
	cout<<"3.3 way "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"<<endl;

	cout<<endl;
	system("pause");
}

result:

1.recursive 1.951 seconds

2.non-recursive 2.224 seconds

3.3 way 1.677 seconds

结果可以看出非递归算法由于需要手动进行算法过程中的变量保存,执行效率低于递归算法;3路划分算法利用少量多余的交换减少了快排的复杂度,执行效率高于传统2路快排算法。