使用C++实现快速排序算法

快速排序基于分治法，平均时间复杂度O(n log n)，在实际应用中广泛使用。其核心思想为：选择基准元素(pivot)，将数组分区为小于和大于基准的两部分，再递归排序子数组。分区采用Lomuto方案，以最右侧元素为基准，通过遍历数组将小于基准的元素移至左侧，最后交换基准至最终位置（i+1处）。 C++实现包含分区函数（partition）和递归排序主函数（quickSort），分区操作在原数组完成，实现原地排序。递归终止条件为子数组长度≤1（left≥right）。时间复杂度平均O(n log n)，最坏O(n²)（如已排序数组选最左/右为基准），可通过随机选基准优化。 关键特性：原地排序，无需额外空间；递归终止条件明确；平均高效，最坏情况可优化。快速排序是面试与开发高频算法，掌握其分区逻辑和递归思想是理解高效排序的关键。