排序之快速排序

快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer）。在这个C++代码示例中，快速排序的实现被清晰地展示出来。下面将详细解释代码中的关键部分。 我们看到一个名为`partition`的函数，它是快速排序的核心。这个函数的作用是将数组分为两部分，一部分的元素都小于或等于一个基准值（pivot），另一部分的元素都大于基准值。函数接受三个参数：数组`arr`、起始下标`low`和结束下标`high`。 ```cpp int partition(int arr[], int low, int high) ``` 在`partition`函数内部，初始化两个指针`i`和`j`，分别指向数组的起始和结束。`pivot`变量用来存储当前数组的第一个元素。然后，使用两个`while`循环来移动指针并调整数组元素的位置，使得`i`左侧的元素都小于或等于`pivot`，而`j`右侧的元素都大于`pivot`。当`i`和`j`相遇时，`pivot`会放在正确的位置，返回`pivot`的新位置`i`。 接下来，我们有`quick_sort`函数，这是一个递归函数，用于执行快速排序。它接受同样的三个参数，并根据`partition`函数的结果，对数组的左半部分和右半部分进行递归调用。 ```cpp void quick_sort(int arr[], int low, int high) ``` 在`main`函数中，用户被要求输入10个数字，这些数字被存储在`arr`和`arr2`两个数组中。`arr2`数组会被排序，而`arr`数组保持原始顺序，这样可以对比排序前后的效果。`quick_sort`函数被调用以对`arr2`进行排序，之后打印出排序后的结果。 快速排序的时间复杂度在平均情况下为O(n log n)，最坏情况下（输入数组已经完全有序或逆序）为O(n^2)。但这种情况在实际应用中很少出现，因为快速排序通常在随机化选择基准值时表现良好。此外，由于快速排序是原地排序且只需要常数级别的额外空间，所以它是内存效率高的排序算法之一。在C++中，快速排序是常用的选择，尤其对于大数据集，它通常比其他内置的排序函数更快。