快速排序优化：Lomuto分区方案详解

"快速排序的优化版本-pfc 5.0 manual手册版" 快速排序是一种高效的排序算法，由C.A.R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。快速排序的核心在于“分治”策略，即分解、解决和合并。 在快速排序的优化版本中，N. Lomuto提出了一个新的PARTITION程序，这个程序被收录在《算法导论》一书中。原始的Lomuto分区方法的步骤如下： 1. 选取待排序序列的最后一个元素作为主元（pivot），记为x。 2. 初始化一个指针i，设置为p-1，表示小于主元元素的存储位置。 3. 使用一个指针j从p开始，遍历到r-1，检查当前元素A[j]是否小于等于主元x。 4. 如果A[j]小于等于x，将i加1，然后交换A[i]和A[j]的位置，这样将小于主元的元素移动到i之前。 5. 当j遍历完成后，交换A[i+1]和A[r]的位置，将主元放到正确的位置，使得所有小于主元的元素都在它前面。 6. 返回i+1，作为下一次排序的边界。 之后，通过递归调用QUICKSORT函数对左右两个子序列进行排序。如果p<r，则对A[p...q-1]和A[q+1...r]分别进行快速排序。 这个优化的版本相对于原版快速排序的主要改进在于它不再固定使用第一个元素作为主元，而是选择最后一个元素，这样做可以减少最坏情况下的划分不均问题。同时，i和j两个指针从头开始，i向前推进，j向后推进，这种做法有助于提高算法效率，特别是在处理已部分排序的数组时。 快速排序的平均时间复杂度为O(n log n)，但最坏情况下（例如输入数组已完全有序或逆序）时间复杂度会退化到O(n^2)。尽管如此，快速排序仍然是实际应用中最常用的排序算法之一，因为它在大多数情况下表现出良好的性能，并且原地排序和常数空间复杂度的优势使其在内存有限的情况下尤为适用。