快速排序（动图详解）（C语言数据结构）

快速排序：

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：

        任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
        快速排序有三个版本，将一一实现。

Hoare版本：

        直接上动图理解：

当前为一遍快排。

再分别以key左右两边进行相同的排序

直到key = right = left。

综上得用递归思想。

代码如下：

void QuickSort(int* a, int begin,int end)
{if (begin >= end)//递归返回条件{return;}int right = end;int left = begin;int key = begin;while (begin < end){//找小while (begin<end && a[end]>=a[key]){end--;}//找大while (begin<end && a[begin]<=a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[key], &a[begin]);k = begin;QuickSort(a,left,key-1);//key左边递归QuickSort(a,key+1,right);//key右边递归
}

递归展开图：

 优化代码：

        通过画递归展开图后，发现如果这个k的取值一直等于left，有缺点，递归的次数较多。

如果能改进就能让效率提高。

        改进思路：

        如果这个递归能像二叉树一样，总共只需要N*log(N)次，就只需要每次这个k取值去一个中间值，不需要去最大也不需要取最小。

        这样的改进方案，称之为三数取中。 

像刚刚，如果要递归的话一次需要递归9次，如果每次取中间的值当k，每次只需要递归3次 。

等左边递归结束式左边空间还是可以继续利用的。                 

 代码如下：

int GetMid(int* a, int begin, int end)
{int mid = (begin+end) / 2;if (a[mid] > a[end]){if (a[mid] < a[begin]){return mid;}else if (a[end] > a[begin]){return end;}elsereturn begin;}else{if (a[mid] > a[begin]){return mid;}else if (a[end] < a[begin]){return end;}elsereturn begin;}
}
void QuickSort(int* a, int begin,int end)
{if (begin >= end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int right = end;int left = begin;int key = begin;while (begin < end){//找小while (begin<end && a[end]>=a[key]){end--;}//找大while (begin<end && a[begin]<=a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[key], &a[begin]);key = begin;QuickSort(a,left,key-1);//key左边递归QuickSort(a,key+1,right);//key右边递归
}

挖坑法版本：

        

代码如下：

void QuickSort2(int* a, int begin, int end)
{if (begin >= end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int left = begin;int right = end;int key = a[left];int hole = left;//第一个为坑while (begin < end){//找小while (begin < end && a[end] >= key){end--;}//找到小的后将数据移到刚刚坑位，并将当前位置作为坑a[hole] = a[end];hole = end;//找大while (begin < end && a[begin] <= key){begin++;}//找到大的后将数据移到刚刚坑位，并将当前位置作为坑a[hole] = a[begin];hole = begin;}a[hole] = key;QuickSort(a, left, hole - 1);//key左边递归QuickSort(a, hole + 1, right);//key右边递归
}

前后指针法：

cur找小，找到以后prev+1后交换cur和prev。

等cur == n-1之后，将a[key]和a[prev]交换，并且将key = prev。 

这个过程保证了prev和cur之间的值是大于key的。

代码如下：

void QuickSort3(int* a, int begin,int end)
{if (begin>=end)//递归返回条件{return;}//三数取中int mid = GetMid(a, begin, end);swap(&a[mid], &a[begin]);int prev = begin;int cur = prev + 1;int key = prev;while (cur<=end-begin){if (a[cur] < a[key]){prev++;if (prev < cur){swap(&a[prev],&a[cur]);}}cur++;}swap(&a[key], &a[prev]);key = prev;QuickSort(a, begin, key - 1);//key左边递归QuickSort(a, key + 1, end);//key右边递归
}