9.6.6　快速排序

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

切分过程，如图9-44所示：

图9-44　快速排序的切分过程

取数组中第一个元素作为切分元素V，从数组的左端开始向右扫描直达找到一个大于等于V的元素，再从数组右端向左扫描直到找到一个小于等于V的元素，交换他们的位置。如此继续，保证左指针左侧的元素都小于等于V，右指针右侧的元素都大于等于V。直到两个指针相遇，将V和左子数组最右侧元素交换，返回j

排序过程，如图9-45所示：

图9-45　快速排序排序过程

快速排序的改进：

快速排序切分不平衡时可能会非常低效，如：第一次以最小的元素切分，第二次以第二小的元素切分，如此，每次调用只会移动一个元素，这将使快速排序退化为冒泡排序。所以快速排序前要将数组进行随机排序，打乱其顺序。另外对于小规模数组，可以使用插入排序来提高排序的性能。原因和归并排序时一样。