快速排序怎么实现的？

Question

如题所述

Answer 1

设待排序序列为{L.r[1]，L.r[2]，…，L.r[n])，首先任意选取一个记录(通常选择第一个记录L.r[1])作为支点(pivot)，然后按照下述原则排列其余记录：将所有关键字比L.r[1]．key小的记录都安排在它的位置之前，将所有关键字比L.r[1].key大的记录都安排在它的位置之后。可以发现，在安置的过程中，L.r[1]的确切位置将被最终确定。设该支点(pivot)最后确定的位置为i，则将序列分割为左右两部分。这个过程称为一趟快速排序。

设待排序序列用数组e[low..high]保存。设置两个指针low和high，分别指向数组的开始位置和终止位置。设支点记录为e[low]，并将之暂存于t。

首先，从high的位置向前搜索，找到第一个小于t的记录，将这个记录和e[low]的值交换；然后，从low所指向的位置向后搜索，找到第一个值大于t的记录，将这个记录和e[high]的值交换。重复以上步骤，直到low=high。完成一趟排序，low(或者high)指向的位置就是第一个元素的确切位置(从两边向中间“夹挤”)。

第一趟完成后，确定了第一个元素的确切位置，同时生成了两个子序列，然后再对这两个序列使用同样的办法，最终实现整个序列的有序。

扩展资料：

快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序。