正文

定义

       快速排序是另一种基于分治技术的重要排序算法。与我们上一篇所讲的合并排序不一样。合并排序是按照元素在数组中的位置对它们进行划分，快速排序按照元素的值对它们进行划分。划分是对给定数组中的元素的重新排列，使得一个数组A[i]，有s下标，A[s]左边的元素都小于等于A[s]，而所有A[s]右边的元素都大于等于A[s]。

A[0]...A[s-1],A[s],A[s+1]...A[i-1]

       显然，在对数组建立了一个划分以后，A[s]已经位于它在有序数组中的最终位置，接下来我们可以继续对A[s]前和A[s]后的子数组分别进行排序(例如，使用同样的方法)。注意，它与合并排序的不同之处在于:在合并排序算法中，将问题划分成两个子问题是很快的，算法的主要工作在于合并子问题的解;而在快速排序中，算法的主要工作在于划分阶段，而不需要再去合并子问题的解了。

伪代码

       伪代码实现

Quicksort(A[ l..r ])
//用Quicksort对子数组排序
//输入：数组A[0..n-1]中的子数组A[ l..r ]，由左右下标 l 和 r 定义
//输出：非降序排列的子数组A[ l..r ]
if l < r
        s <-Partition (A[1..r])//s是分裂位置
        Quicksort( A[ l.. (s - 1)])
        Quicksort(A[(s +1)..r ])

算法解析

       对于快速排序，有数组A[0..n-1]，子数组A[e..r]，我们要选择一个中轴，接下来会根据该元素的值来划分子数组。选择中轴有许多不同的策略，当我们分析该算法的效率时，我们会回到这个话题。现在，我们只使用最简单的策略——选择子数组的第一个元素，即p=A[0]。

       然后 我们将分别从子数组的两端进行扫描，并且将扫描到的元素与中轴相比较。从左到右的扫描(下面用指针i表示)从第二个元素开始。因为我们希望小于中轴的元素位于子数组的左半部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才会停止。从右到左的扫描(下面用指针j表示)从最后一个元素开始。因为我们希望大于中轴的元素位于子数组的右半部分，扫描会忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止。(为什么当遇到与中轴元素相等的元素时值得停止扫描?因为当遇到有很多相同元素的数组时，这个方法可以将数组分得更加平均，从而使算法运行得更快。如果我们遇到相等元素时继续扫描，对于一个具有n个相同元素的数组来说，划分后得到的两个子数组的长度可能分别是n~1和0，从而在扫描了整个数组后只将问题的规模减1。)

       两次扫描全部停止以后，取决于扫描的指针是否相交，会发生3种不同的情况。1、如果扫描指针i和 j不相交，也就是说i<j，我们简单地交换A[i]和A[j]，再分别对i加1，对j减1，然后继续开始扫描；2、如果扫描指针相交，也就是说i> j，把中轴和A[j]交换以后，我们得到了该数组的一个划分；3、最后，如果扫描指针停下来时指向的是同一个元素，也就是说i= j，被指向元素的值一定等于p。(为什么?)因此，我们建立了该数组的一个划分，分裂点的位置s =i= j。

       我们可以把第三种情况和指针相交的情况(i> j )结合起来，只要i≥j，就交换中轴和A[j]的位置

时间效率分析

       在开始讨论快速排序的效率以前，我们应该要注意;如果扫描指针交叉了，建立划分之前所执行的键值比较次数是n+1;如果它们相等，则是n。如果所有的分裂点位于相应子数组的中点，这就是最优的情况。在最优情况下，键值比较的次数Cbes(n)满足下面的递推式:

当n>1时，

       根据主定理，；对于n=2*的情况求得 。

       在最差的情况下，所有的分裂点都趋于极端:两个子数组有一个为空，而另一个子数组仅仅比被划分的数组少一个元素。具体来说，这种令人遗憾的情况会发生在升序的数组上，也就是说，输入的数组已经被排过序了!的确，如果 A[0..n –1]是严格递增的数组，并且我们将A[0]作为中轴，从左到右的扫描会停在A[1]上，而从右到左的扫描会一直处理到A[0]为止，导致分裂点出现在0这个位置。

       所以，在进行了n+1次比较之后建立了划分，并且将A[0]和它本身进行了交换以后，快速排序算法还会对严格递增的数组A[1..n-1]进行排序。对规模减小了的严格递增数组的排序会一直继续到最后一个子数组A[n-2..n-1]。这种情况下，键值比较的总次数应该等于:

源码

#include <stdio.h>
// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 分区函数
int partition(int arr[], int low, int high) {
    // 选取最后一个元素作为基准值
    int pivot = arr[high];
    // i指向小于基准值的最后一个元素
    int i = (low - 1);
    // 遍历数组，将小于基准值的元素放到左边，大于基准值的元素放到右边
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    // 将基准值放到中间
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 将数组分为两部分，左边的元素都小于右边的元素
        int pi = partition(arr, low, high);
        // 递归排序左边的部分
        quickSort(arr, low, pi - 1);
        // 递归排序右边的部分
        quickSort(arr, pi + 1, high);
    }
}
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}