快速排序算法实现与比较：普通VS随机

"这篇文档是关于中国科学技术大学《算法导论》课程实验一的内容，主要讲解快速排序算法的实现，包括普通快速排序和随机快速排序。实验的目标是实现这两种快速排序算法，并通过比较它们在处理相同数据时的时间差异来验证理论上的效率优势。" 快速排序是一种高效的排序算法，由C.A.R. Hoare在1960年提出。它的基本思想是采用分治策略，通过选择一个基准值，将待排序的数据分为两部分：一部分所有元素小于基准，另一部分所有元素大于基准。然后对这两部分再进行同样的操作，直到所有元素都在其最终位置上。 实验中，普通快速排序选择数组的最后一个元素作为基准，而随机快速排序则是随机选取数组中的一个元素作为基准。以下是两种快速排序的算法流程： 1. 普通快速排序： - 选取数组末尾的元素作为基准值key。 - 初始化两个指针i和j，i指向数组起始位置，j指向数组末尾。 - 从j开始向前搜索，找到第一个小于key的元素，将其与i位置的元素交换。 - 从i开始向后搜索，找到第一个大于key的元素，将其与j位置的元素交换。 - 重复以上步骤，直到i等于j，完成一趟排序。 2. 随机快速排序： - 随机选择数组中的一个元素作为基准值key。 - 同样使用i和j作为双向指针，但搜索方向不变。 - 通过随机选择基准，可以降低最坏情况发生的概率，从而提高平均性能。 实验数据输入为用户指定的元素个数n，系统会随机生成n个整数进行排序。输出是排序后的序列和排序所用时间。实验结果表明，随机快速排序在处理相同数据时，确实比普通快速排序有更短的运行时间。例如，在处理10000个随机生成的数字时，随机快排比普通快排快了约2200us。 实验代码部分没有完全展示，但可以看出是使用C++编写，调用了名为`QUICKSORT`的函数进行排序操作。完整的代码应包括快速排序的实现，以及时间测量功能，以便记录排序耗时。 快速排序的平均时间复杂度为O(n log n)，但在最坏情况下（如输入已经完全有序或逆序）会退化到O(n^2)。通过随机选择基准，可以显著减少这种情况的发生，从而提高算法的实际效率。随机快速排序在实践中通常比其他O(n log n)的排序算法表现更好，因为它避免了因特定输入导致的性能下降。