概述
快速排序代码
首先是划分算法，假设每次都以第一个元素作为枢轴值，进行一趟划分：
int Partition(int A[], int low, int high)
{
int pivot = A[low];
while (low < high)
{
while (low < high && A[high] >= pivot)
--high;
A[low] = A[high]; //将比枢轴值小的元素移到左边
while (low < high && A[low] <= pivot)
++low;
A[high] = A[low]; //将比枢轴值小的元素移到右边
}
A[low] = pivot;
//将枢轴值元素置于最终位置
return low;
}第一个while循环里的代码还可以采用如下形式：
while (low < high && A[high] >= pivot)
--high;
while (low < high && A[low] <= pivot)
++low;
if(low < high)
{
swap(A[low],A[high])
++low;
--high;
}|
递归调用快速排序算法的划分操作，如下：
|
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void
QuickSort(
int
A[],
int
low,
int
high)
{
if
(low < high)
//递归跳出条件
{
//Partition就是上面的划分操作
int
pivot = Partition(A,low,high);
//划分
QuickSort(A,low,pivot-1);
//左半部分递归
QuickSort(A, pivot + 1, high);
//右半部分递归
}
}
|
由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息。因为要进行n-1次递归调用，所以栈的深度O(n);平均情况下，栈的深度为O(logn)。
时间效率：
快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。快速排序的最坏情况发生在划分时两个区域分别包含n-1和0个元素时，这种最大程度的不对称性多发生在每一层递归上，亦即对应于初始排序表基本有序或基本逆序时，就得到最坏的情况下的复杂度，为O(n^2)。
在快速排序中，并不产生有序子序列，但每一趟排序后都将一个元素置于最终位置。
快速排序优化成最坏O(NlogN)：
采用media-of-three选择枢轴值可以比较好的避免划分恶化的情况，另外因为快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化。其中第二次递归可以用迭代代替。（如果可以结合其他的排序方法的话，还可以结合堆排序，很多库中的排序算法都是混合排序的，根据数据的情况和规模大小采用不同的排序方法，并把它们组合起来。比如STL中的sort排序算法，结合了插入排序、快速排序、堆排序）
快速排序的非递归实现：
其实就是手动利用栈来存储每次分块快排的起始点，栈非空时循环获取中轴入栈
最后
以上就是傻傻蜜粉为你收集整理的快速排序实现（递归+非递归） 快速排序代码的全部内容，希望文章能够帮你解决快速排序实现（递归+非递归） 快速排序代码所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
