排序算法——关于快速排序的详解

1.基本思想

2.基本原理

2.1划分思想

2.2排序过程

（1）选择基准值

（2）分割过程（Partition）

（3）递归排序

（4）合并过程

2.3具体实例

2.4实现代码

2.5关键要点

3.性能分析

3.1空间效率

3.2时间效率

3.3稳定性

1.基本思想

快速排序（Quick Sort）是一种常用的排序算法，它采用分治法的思想，通过递归地将数据分解成小于基准值和大于基准值的两部分，然后对这两部分进行排序，最终将它们合并起来。

2.基本原理

2.1划分思想

在待排序表L[l...n]中任取一个元素pivot作为枢轴(或称基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L[l...k-1]和L[k+l...n]，使得L[l...k-l]中的所有元素小于pivot；L[k+l...n]中的所有元素大于或等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次划分。

2.2排序过程

（1）选择基准值

从待排序数组中选择一个元素作为基准值。通常选择第一个元素，但也可以选择随机元素或数组中间的元素。

（2）分割过程（Partition）

将数组按照基准值进行分割，将小于等于基准值的元素放在基准值的左侧，大于基准值的元素放在右侧。同时，基准值所在的位置被确定，这个位置之前的元素都小于等于基准值，之后的元素都大于基准值。这一过程可以使用双指针法来实现。

（3）递归排序

对基准值左侧和右侧的子数组分别进行递归排序。即对左侧子数组和右侧子数组分别重复步骤1和步骤2。

（4）合并过程

递归排序完成后，整个数组已经被拆分成若干有序的子数组，只需简单地将这些子数组合并即可得到最终的有序数组。

2.3具体实例

一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍

*来自2024版王道数据结构考研复习指导

设两个指针i和j，初值分别为low和high，取第一个元素49为枢轴赋值到变量pivot。

对算法的最好理解方式是手动地模拟一遍这些算法。

2.4实现代码

void Quicksort(ElemType A[], int low, int high) {
    if (low < high) {
        //递归跳出的条件
        //Partition()就是划分操作，将表A [low…high]划分为满足上述条件的两个子表
        int pivotpos = Partition(A, low, high);
        //划分
        Quicksort(A, low, pivotpos - 1);
        //依次对两个子表进行递归排序
        Quicksort(A, pivotpos + 1, high);
    }
}

int Partition(ElemType A[], int low, int high) {
    //一趟划分
    ElemType 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;
    //返回存放枢轴的最终位置
}