快速排序的优化

1.在极端情况下的优化

在上一篇文章中，我们提到了一个时间复杂度：

最优时间复杂度：O（nlogn）-- 每次找到的都是中间值

最坏时间复杂度：O（n^2）-- 有序数组或者接近有序

在这看来，快速排序的时间复杂度还无法确定，所以我们会对代码进一步优化。

2.三数取中法

思维如下：

取三个数，分别为 begin ， mid ， end 代表数组的首元素，中间元素，和末尾元素。将他们对应的值进行比较，取三数中间大小的为keyi，然后加入快速排序的函数中，再细微调整。

代码如下，使用简单的if-else 判断，就可以得到中间值下标mid

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

逻辑很简单，可以自己尝试一下哟

---

3.快速排序非递归

之前的代码：

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

使用过递归实现的，所以所需要的空间是在栈上面进行的。但是栈的空间很小，在达到一定程度的深度调用就会引起爆栈。所以，我们接下来是想让程序最好能在堆上运行（堆的大小单位为G），而栈的话一般只有64KB，所以啦，我们接下来学习的非递归版很有用处哟：

//快速排序非递归版
void QuickSortNon(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);
 
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
 
		int right = StackTop(&st);
		StackPop(&st);
 
		int keyi = PartSort3(a, left, right);
 
		if ( keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
 
		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
 
	}
 
	StackDestroy(&st);
}

在这里需要和栈结合起来，通过栈的特点来达到，我们可以达到类似于递归过程的非递归的方法。