C++实现快速排序算法详解

“这是一个C++实现的排序算法程序，包含了冒泡排序、选择排序、插入排序和快速排序。其中，快速排序部分的代码被详细展示。” 快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。其基本思想是采用分治法（Divide and Conquer）：选择一个基准值，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 在这个C++程序中，`quicksort()`函数是快速排序的主要实现部分。它接受两个参数，`p`表示起始索引，`r`表示结束索引。首先检查`p < r`，如果条件满足，说明需要对数组的一部分进行排序。`partition()`函数负责划分数组，返回基准值的正确位置，使得基准值左边的元素都小于基准值，右边的元素都大于基准值。`quicksort()`函数随后对基准值左右两边的子数组进行递归调用，直至所有元素排序完成。 `partition()`函数通过两个指针`i`和`j`进行操作，`i`从左向右移动，`j`从右向左移动，直到找到小于或等于基准值的元素（`num[j] <= x`）和大于或等于基准值的元素（`num[i] >= x`），然后交换这两个元素。这个过程称为“分区操作”。当`i`和`j`相遇时，此时的`num[j]`就是基准值的正确位置，交换`num[j]`和`num[p]`，并将`j`的值作为分区后的位置返回。 此外，程序还包括了`setnumber()`函数用于输入N个整数，`putnumber()`函数用于输出数组元素，以及用户交互逻辑，让用户可以多次运行排序操作。 在实际应用中，快速排序的平均时间复杂度为O(n log n)，最坏情况（如已排序数组）为O(n^2)，但这种情况较为罕见。由于快速排序在大部分情况下表现出良好的性能，并且原地排序（不需要额外的存储空间），因此在很多场景下被广泛使用。