排序：快速排序算法分析

1.交换排序

基于“交换”的排序︰
根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

快速排序属于交换排序的大类。

2.快速排序的算法思想

1.算法实现:

1. 在待排序表$L[\mathrm{1...}n]$中任取一个元素pivot作为枢轴(或基准，通常取首元素)，
2. 通过一趟排序将待排序表划分为独立的两部分$L[\mathrm{1..}k-1]$和$L[k+\mathrm{1..}n]$，
3. 使得$L[\mathrm{1...}K-1]$中的所有元素小于pivot，
4. $L[k+\mathrm{1...}n]$中的所有元素大于等于pivot,
5. 则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。
6. 然后分别递归地对两个子表重复上述过程，
7. 直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

2.每一次划分之后的操作

• 更小的元素都交换到左边更大的元素都交换到右边.
• 用第一个元素把待排序序列“划分”为两个部分：左边更小，右边更大。该元素的最终位置已确定。

3.快速排序的代码实现

示意图：

代码：

//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[], int low, int high) {
    int pivot = A[low];//第一个元素作为枢轴
    while (low < high) {//用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;//返回存放枢轴的最终位置
}

//快速排序
void QuickSort(int A[], int low, int high) {
    if (low < high) {//递归跳出的条件
        int pivotpos = Partition(A, low, high); //划分
        QuickSort(A, low, pivotpos - 1);//划分左子表
        QuickSort(A, pivotpos + 1, high); //划分右子表
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.快速排序的算法效率分析

算法表现主要取决于递归深度，若每次“划分”越均匀，则递归深度越低。“划分”越不均匀，递归深度越深。

快速排序的过程就是遍历含n个结点的二叉树的过程。
即递归的层数为树的高度：最小高度=$[lo{g}_{2}n]+1$，最大高度= n

1.时间复杂度

每一层的QuickSort只需要处理剩余的待排序元素，时间复杂度不超过O(n)。

时间复杂度=$O(n\ast 递归层数)$

• 最好时间复杂度=$O(nlo{g}_{2}n)$
• 最坏时间复杂度=$O(n^2)$
• 平均时间复杂度：$O(nlo{g}_{2}n)$

2.空间复杂度

最好空间复杂度=$O(lo{g}_{2}n)$

最坏空间复杂度=$O(n)$

3.最坏的情况：

• 若初始序列有序或逆序，则快速排序的性能最差(因为每次选择的都是最靠边的元素)
• 若每一次选中的“枢轴”（基准数）将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低

4.比较好的情况

若每一次选中的“枢轴”将待排序序列划分为均匀的两个部分，
则递归深度最小，算法效率最高。

5.快速排序算法优化思路:

尽量选择可以把数据中分的枢轴元素。

• ①选头、中、尾三个位置的元素，取中间值作为枢轴元素;
• ②随机选一个元素作为枢轴元素

快速排序是所有内部排序算法中，平均性能最优的排序算法。

5.稳定性

不稳定。