vlambda博客
学习文章列表

数据结构的学习可以分为八个模块：1.绪论，2.线性表，3.栈和队列，4.串，5.树与二叉树，6.图，7.查找，8.排序。

排序部分可分为：

其中交换排序需要掌握：

2

快速排序

快速排序的基本思想是基于分治法的∶在待排序表 L[1..n]中任取一个元素 pivot 作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 L[1...k-1]和 L[k+1...n]，使得 L[1...k-1]中的所有元素小于 pivot，L[k+1...n]中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L(k)上，这个过程称为一趟快速排序(或一次划分)。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针 i和j，初值分别为 low 和high，取第一个元素 49 为枢轴赋值到变量 pivot。

指针j从 high 往前搜索找到第一个小于枢轴的元素27，将 27 交换到i所指位置。

指针 i 从 low往后搜索找到第一个大于枢轴的元素 65，将 65 交换到j所指位置。

指针 j继续往前搜索找到小于枢轴的元素 13，将 13 交换到i所指位置。

指针 i继续往后搜索找到大于枢轴的元素 97，将 97 交换到j所指位置。

指针 j继续往前搜索小于枢轴的元素，直至 i==j。 

此时，指针i(==j)之前的元素均小于49，指针i之后的元素均大于等于49，将 49 放在 i所指位置即其最终位置，经过一趟划分，将原序列分割成了前后两个子序列。

按照同样的方法对各子序列进行快速排序，若待排序列中只有一个元素，显然已有序。

假设划分算法已知，记为 Partition()，返回的是上述的 k，注意到 L(k)已在最终的位置，因此可以先对表进行划分，而后对两个表调用同样的排序操作。因此可以递归地调用快速排序算法进行排序，具体的程序结构如下∶

void QuickSort (int 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);

    }

}

从上面的代码不难看出快速排序算法的关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏。从快速排序算法提出至今，已有许多不同的划分操作版本，但考研所考查的快速排序的划分操作基本以严蔚敏的教材《数据结构》为主。假设每次总以当前表中第一个元素作为枢轴来对表进行划分，则将表中比枢轴大的元素向右移动，将比枢轴小的元素向左移动，使得一趟 Partition ()操作后，表中的元素被枢轴值一分为二。代码如下∶

int Partition(int A[]，int low，int high){     //一趟划分

    int pivot=A[1ow];     //将当前表中第一个元素设为枢轴，对表进行划分 

    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;    //返回存放枢轴的最终位置

}

快速排序算法的性能分析如下∶

空间效率∶ 由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为 O(log₂n);最坏情况下，因为要进行n- 1 次递归调用，所以栈的深度为 O(n);平均情况下，栈的深度为 O(log₂n)。

时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含 n-1 个元素和 0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应干初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 O(n²)。

有很多方法可以提高算法的效率∶ 一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素;或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即 Partition ()可能做到最平衡的划分，得到的两个子问题的大小都不可能大于 n/2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 O(nlog₂n)。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

稳定性∶ 在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。

例如，表L={3，2，2}，经过一趟排序后L= {2，2，3}，最终排序序列也是L= {2，2，3}，显然，2 与2的相对次序已发生了变化。

注∶ 在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴(基准)元素放到其最终的位置上。