当前位置：网站首页>快速排序的三种实现方式

如果给我们一个数组，要求是让我们对这个数组进行排序，但是同时又要求时间复杂度尽可能的小。这个时候冒泡排序（时间复杂度 O（n^2））显然是指望不上了，而这里有一个公认的快速排序的方法，最初是由Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1.Hoare版本

首先说一下大概思想：

第一步：

首先找一个数作为key值（通常为数组最左边的数，这里其实选择哪个是无所谓的，微调一下后面的代码就行），作用就是在一趟排序后将所在的数组分为两部分：数组的左边是小于key的值，数组的右边是大于key的值，界限就是key。（实际代码中其实是保存key这个数的下标，方便最后的交换）

第二步：

在一趟排序中从数组的右边开始逐一向左查找，找比key小的数，然后再从数组的左边开始从逐一向右查找，找比key大的数，完成上述操作后交换找到的两个数。然后再判断整个数组是否被遍历完，即最后交换的两个数的下标是否相同或错位。没有遍历完的话继续重复上述交换操作，直到遍历完结束。最后将key与最后遍历结束的位置的数交换位置。

此时的这一趟操作就会完成对数组关于key值左右大小的分割。

第三步：

对上趟排序后key值左右的两个数组再次进行找key值并进行划分，也就是所谓的函数递归了。直到递归到不能再割分为止。这时的数组就被排好序了。

Hoare图解：

最后会发现全都变为区间为一的数组了，此时的整个数组也有序了。

Hoare代码：

（递归版本）

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

int PartSort1(int* a, int left, int right) //函数返回key的下标
{
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	else
	{
		int keyi = PartSort1(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

2.挖坑法：

第一步：

首先找一个坑位，把坑位里的值保存到key里，这时的坑位里的值可以被覆盖。

第二步：

从数组的右边开始向左逐一遍历，找比key小的数，然后把这个值放在坑位里面，把坑位更新成刚刚找到的数的位置。接着从左开始向右逐一遍历，找比key大的数，然后把这个数放在坑位里面，把坑位更新成刚刚找到的数的位置。重复上述操作，直到把数组遍历一遍。最后把key放在最后的坑位里面。

第三步：

以key为界限，把数组分为左右两个数组，接着重复第一步和第二步，直到无法再拆分为止。

挖坑法图解：

挖坑法代码：

（递归版本）


int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int pit = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[left] = key;
	return left;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	else
	{
		int keyi = PartSort2(a, left, right);
		QuickSort(a, left, keyi - 1);          //左数组
		QuickSort(a, keyi + 1, right);         //右数组
	}
}

3.前后指针版本

第一步：

初始时，prev指针指向序列开头，cur指针指向prev的下一个位置。keyi指针指向序列开头。

第二步：

cur指针找比key小的值，找到的话就与prev下一个位置的数交换位置。找的过程中如果是找的数比key大，cur指针往后继续查找，prev保持不动。cur完成一遍遍历后，把key和prev指针指向的数交换。

第三步：

以key值为界限，把数组分为左右两个数组，然后重复第一步和第二步。

前后指针版本图解：

前后指针法代码：

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

int GetMidIndex(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
			return midi;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[left] < a[right])
			return left;
		else if (a[midi] > a[right])
			return midi;
		else
			return right;
	}
}

int PartSort3(int* a, int left, int right)
{
    //优化，下面会讲
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);


	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && a[cur] != a[++prev])
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	else
	{
		int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

优化：

我们先来看看怎么计算这种算法的时间复杂度

时间复杂度：

最好情况：

每次的key值都是数组的中值！

最坏情况：

每次的key值都是最大或最小值！

那么我们要尽量避免最坏的情况出现。

这里可以控制key值得选取，假如我们在排序之前随机选取三个数，取三个数中得中值作为key值，就可以一定程度上避免最坏情况的发生！再结合之前写的代码，把找到的中值与最左边的数交换一下，就能在不改变之前代码的基础上完成优化了！

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//取三个数中中间位置的数
int GetMidIndex(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
			return midi;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[left] < a[right])
			return left;
		else if (a[midi] > a[right])
			return midi;
		else
			return right;
	}
}