快速排序算法（图文并茂，Java实现）

快速排序是冒泡排序的一种改进，与冒泡排序类似，快速排序是将元素序列中的关键字与指定的元素进行比较，将逆序的两个元素进行交换。

快速排序的基本思想：设待排序的元素序列的个数为 n，分别存放在数组 data[1…n]中，令第一个元素作为枢轴元素，即将 a[1] 作为参考元素，令 pivot=a[1]。初始时，令 i=1、j=n，然后按照以下方法操作：

1) 从序列的 j 位置往前，依次将元素的关键字与枢轴元素比较：

若当前元素的关键字大于或等于枢轴元素的关键字，则将前一个元素的关键字与枢轴元素的关键字比较；
否则将当前元素移动到位置 i，即比较 a[j].key 与 pivot.key，若 a[j].key≥pivot.key，则连续执行 j-- 操作，直到找到一个元素使 a[j].key<pivot.key，则将 a[j] 移动到 a[i] 中，并执行一次 i++ 操作。

2) 从序列的 i 位置开始，依次将该元素的关键字与枢轴元素比较：

若当前元素的关键字小于或等于枢轴元素的关键字，则将后一个元素的关键字与枢轴元素的关键字比较；
否则将当前元素移动到位置 j，即比较 a[i].key 与 pivot.key，若 a[i].key≤pivot.key，则连续执行 i++，直到遇到一个元素使 a[i].key＞pivot.key，则将 a[i]移动到 a[j] 中，并执行一次 j-- 操作。

3) 循环执行步骤 1 和步骤 2 ，直到出现 i≥j，则将元素 pivot 移动到 a[i] 中。此时整个元素序列在位置 i 被划分成两部分，前一部分的元素关键字都等于 pivot.key，后一部分元素的关键字都大于或等于 pivot.key，即可完成一趟快速排序。

如果按照以上方法，在每个部分继续进行以上划分操作，直到每个部分只剩下一个元素，不能继续划分为止，这样整个元素序列就按照关键字非递增排列了。

例如，一组元素序列的关键字为 (37,19,43,22,22,89,26,92) ，根据快速排序算法的思想，第一趟快速排序过程如下图所示。

图 1 第一趟快速排序过程

从图 1 中可以看出，当第一趟快速排序完成之后，整个元素序列被枢轴元素 37 划分为两部分，前一部分元素的关键字都小于 37，后一部分元素的关键字都大于或等于 37。

其实，快速排序的过程就是以枢轴为中心对元素序列进行划分的过程，直到所有的序列被划分为单独的元素，快速排序完毕。

快速排序的全过程如下图所示：

图 2 快速排序的全过程

进行一趟快速排序，即将元素序列进行一次划分的算法描述如下：

public int Partition(int low, int high)
// 对顺序表 L.r[low..high] 的元素进行一趟排序，使枢轴前面的元素关键字小于枢轴元素的关键字，
// 枢轴后面的元素关键字大于或等于枢轴元素的关键字，并返回枢轴位置
{
    int pivotkey = data[low];  // 将表的第一个元素作为枢轴元素
    int t = data[low];
    while (low < high)  // 从表的两端交替地向中间扫描
    {
        while (low < high && data[high] >= pivotkey) // 从表的末端向前扫描
            high--;
        if (low < high)  // 将当前 high 指向的元素保存在 low 位置
        {
            data[low] = data[high];
            low++;
        }
        while (low < high && data[low] <= pivotkey) // 从表的始端向后扫描
            low++;
        if (low < high) // 将当前 low 指向的元素保存在 high 位置
        {
            data[high] = data[low];
            high--;
        }
    }
    data[low] = t;  // 将枢轴元素保存在 low = high 的位置
    return low;  // 返回枢轴所在位置
}

快速排序算法通过多次递归调用一次划分算法，即一趟排序算法，可实现快速排序，其算法描述如下：

public void QuickSort(int low, int high) // 对顺序表 L 进行快速排序
{
    if (low < high) // 如果元素序列的长度大于 1
    {
        int pivot = Partition(low, high); // 将待排序序列 L.r[low..high] 划分为两部分
        QuickSort(low, pivot - 1);  // 对左边的子表进行递归排序，pivot 是枢轴位置
        QuickSort(pivot + 1, high);  // 对右边的子表进行递归排序
    }
}

可以看出，快速排序是一种不稳定的排序算法，其空间复杂度为 O(logn)。

在最好的情况下，每趟排序均将元素序列正好划分为相等的两个子序列，这样快速排序的划分过程就使元素序列构成一棵完全二叉树的结构，分解的次数等于树的深度，即 logn，因此快速排序总的比较次数为：

T(n)≤n+2T(n/2)≤n+2(n/2+2T(n/4))=2n+4T(n/4)≤3n+8T(n/8)≤…≤nlogn+nT(1)

因此，在最好的情况下，时间复杂度为 O(nlogn)。

在最坏的情况下，待排序的元素序列已经是有序序列，则第一趟需要比较 n-1 次，第二趟需要比较 n-2 次，以此类推，共需要比较 n(n-1)/2 次，因此时间复杂度为 O(n^2)。

在平均情况下，快速排序的时间复杂度为 O(nlogn)。

快速排序算法（图文并茂，Java实现）

相关文章