本文主要是介绍快速排序（动图详解）（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右边递归
}这篇关于快速排序（动图详解）（C语言数据结构）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
