【数据结构】快速排序

1.引入

快速排序的基本思想其实就是交换排序；我们所了解的冒泡排序就是一种交换排序；但是冒泡排序的时间复杂度为O(n^2)，并不实用，而快速排序就是一种非常高效的排序，稳定性也比较不错，时间复杂度为O(n * lng n);

先来看一下冒泡排序，

void Bubble(int* a,int n)
{
    int i, j;
    for(i = 0; i < n - 1; i++)
    {
        for(j = 0; j < n - 1- i; j++)
        {
            if(a[j] > a[j + 1])
            {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

显然 这种交换排序的主要特点就是将值较大的记录向序列的尾部移动，值较小的记录向序列的前部移动；(升序，降序反之)。

先分析单趟的排序；单躺的冒泡排序是将 最大的值放到数组的最后面，之后就不考虑这个最大的数了，而快速排序的单趟是将准备好的 key 值放到 适当的位置（排好序的位置）；

下面先来分析一下快速排序的单趟排序：

用两个参数 left 与 right ，分别从数组的两边出发，right 找比 key 值小的，找到之后停下，left 找比 key 值大的，找到之后也停下，互换两个数的，循环 直到 left == right；停下再将 key 与 left 互换；这样就是一个单趟的排序；将 key 值放到了适当的位置。 

int QuickSort_along(int* a,int left;int right)
{
    int keyi = left;
    while(left < right)
    {
        // R 先走 找小  L再找大(只找大小)
        while ((a[right] >= a[keyi]) && (left < right))
        {
            right--;
        }
        while ((a[left] <= a[keyi]) && (left < right))
        {
            left++;
        }
        if(left < right)
        swap(&a[left],&a[right]);
    }
    swap(&a[left],&a[keyi]);
    return left;
}

排完单趟的快速排序，现在来看整体的；

#include<stdio.h>
QuickSort(int* a,int left,int right)
{
    if(left < right)
    {
        return;
    }
    int keyi = QuickSort_along(a,left,right);
    QuickSort(a,left,keyi - 1);
    QuickSort(a,keyi + 1，right);
}
int main()
{
    int a[] = {10,9,8,7,6,5,4,3,2,1};
    QuickSort(a,0,9);
}

上面的方法其实是有缺陷的，如果当数据恰好是按照降序排的，又恰巧数据很大，这时就会发生递归过深，栈溢出的现象；我们可以有两个优化的方法，

1.三数取中：

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

int QuickSort_along(int* a,int left;int right)
{
    int mid = GetMidIndex(a, left, right);
	swap(&a[mid], &a[left]);
    int keyi = left;
    while(left < right)
    {
        // R 先走 找小  L再找大(只找大小)
        while ((a[right] >= a[keyi]) && (left < right))
        {
            right--;
        }
        while ((a[left] <= a[keyi]) && (left < right))
        {
            left++;
        }
        if(left < right)
        swap(&a[left],&a[right]);
    }
    swap(&a[left],&a[keyi]);
    return left;
}

2.最小区间优化：

我们直到，当快速排序的递归模式和二叉树很像，递归越到深层，函数的调用就越多；而且调用的越深所排的数组就越有序，此时，我们跳出来，不让他进行快排的递归了，我们直接进行插入排序或者其他的排序来解决这一个问题。

void InserSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}
QuickSort(int* a,int left,int right)
{
    if(left < right)
        return;
    int keyi = QuickSort_along(a,left,right);
    if(keyi - left > 8)
        InserSort(a,keyi);
    else
    {
        QuickSort(a,left,keyi - 1);
        QuickSort(a,keyi + 1,right);
    }
}

除了上面的方法还有两种 单排的方法：

1.挖坑法：

int QuickSort_along(int* a, int left, int right)
{
	// 三数取中优化
	int mid = GetMidIndex(a, left, right);
	swap(a[mid], a[left]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		// 先从右边找小 赋值挖坑
		while (a[right] >= key && (left < right))
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;

		// 先从左边找大 赋值挖坑
		while (a[left] <= key && (left < right))
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

2.前后指针法：

int QuickSort_along(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	swap(a[mid], a[left]);
    int keyi = left;
    int prev = left;
    int cur = prev + 1;
    while(cur >= right)
    {
        if(a[cur] < a[keyi] && ++prev != cur)
            swap(&a[cur],&a[prev]);
        cur++;
    }
    return prev;
}

最后还有一个：非递归的快速排序：

利用数据结构的栈非递归快排
其实就是将递归的思想用代码表现出来，利用了栈的后进先出的特性。

void QuickSort_Stack(int* a, int left, int right)
{
	Stack SL;
	StackInit(&SL);
	StackPush(&SL,left);
	StackPush(&SL,right);
	while (!StackEmpty(SL))
	{
		int end = StackFront(SL);
		StackPop(&SL);
		int begin = StackFront(SL);
		StackPop(&SL);
		/*if (begin >= end)
		{
			continue;
		}*/
		int keyi = PartSort2(a, begin, end);
		if (keyi + 1 < end)
		{
			StackPush(&SL, keyi + 1);
			StackPush(&SL, end);
		}
		if (begin < keyi - 1)
		{
			StackPush(&SL, begin);
			StackPush(&SL, keyi - 1);
		}
	}
	StackDestory(&SL);
}