快速排序排序方法演示及算法分析（附代码和实例）

基本思想：

• 任取一个元素（比如第一个）为中心，称为枢轴（pivot）
• 所有比它小的元素一律前放，比它大的元素后放，形成左右两个子表
• 对各子表重新选择中心元素并以此规则调整
• 直到每个子表的元素只剩一个

算法

void QSort(SqList &L, int low, int high){if(low<high){pivotloc = Partition(L,low, high);//将L.r[]一分为二，pivotloc为枢轴元素排好序的位置QSort(L, low, pivotloc-1);//对左子表递归排序QSort(L, pivotloc+1, high);//对右子表递归排序}
}

int Partition(SqList &L, int low, int high){L.r[0]=L.r[low];pivotkey = L.r[low].key;while(low<high){while(low<high && L.r[high.key]>=pivotkey)--high;L.r[low]=L.r[high];while(low<high && L.r[low.key]<=pivotkey)++low;L.r[high] = L.r[low];}L.r[low]=L.r[0];return low;
}

示例
对于序列49 38 65 97 76 13 27，进行快速排序，步骤如下：
以第一个元素49作为枢轴，即pivotkey=49，进行第一轮排序，最后一个元素开始，将序列中大于49的元素放在右边，小于49的元素放在左边

27<49，将27放在左侧 i 所指的位置上，i++
38<49，38放在左侧i的位置上（已处在合适的位置），i++
65>49，将65放在右侧 j 所指的位置上，j--
13<49，将13放在左侧 i 所指的位置上，i++
以此类推，直到 i=j，用枢轴pivotkey替换此时的 i 和 j 的位置
第一轮排序过程如下

第一轮排序后，由于左右子序列元素个数均大于1，继续对左右子序列排序

对左子序列排序
选第一个元素为枢轴
排序过程如下

经过一趟快排之后，左右子序列的元素个数均为1，左子序列排序结束

对右子序列排序
选第一个元素为枢轴
排序过程如下:

经过一趟快排之后，左右子序列的元素个数均为1，右子序列排序结束

排序结束，生成的有序序列为13 27 38 49 65 76 97

时间复杂度

O($nlo{g}_{2}n$)

• QSort():Q($lo{g}_{2}n$)
• Partition()：O(n)

就平均计算时间而言，快速排序是所有内排序方法中最好的一个

空间复杂度

快速排序不是原地排序

由于程序使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度

• 平均情况下，需要O(logn)的空间
• 最坏情况下，需要O(n)的空间

稳定性

快速排序是一种不稳定的排序方法