快速排序算法-核心思想是分治法

快排的核心思想是分治法，我们选择一个基准值，然后将数组分为小于基准值和大于基准值的两部分，再递归地对这两部分进行排序。

void quickSort(int arr[], int left, int right) {
if (left >= right) return; // 递归终止条件

// 选择基准值，这里简单地选择最左边的元素
int pivot = arr[left];

// 分区过程
int i = left, j = right;
while (i < j) {
// 从右向左找第一个小于基准的数
while (i < j && arr[j] >= pivot) j–;
// 从左向右找第一个大于基准的数
while (i < j && arr[i] <= pivot) i++;
// 交换这两个数
if (i < j) {
std::swap(arr[i], arr[j]);
}
}
// 将基准值放到正确的位置
std::swap(arr[left], arr[i]);

// 递归排序左右两部分
quickSort(arr, left, i – 1);
quickSort(arr, i + 1, right);
}

这个实现中，我选择了最左边的元素作为基准值，然后通过双指针法进行分区。当然，这种选择基准值的方式在最坏情况下（如已排序数组）会导致O(n²)的时间复杂度。

为了优化，我们可以使用随机选择基准值或三数取中法：

int median3(int arr[], int left, int right) {
int mid = left + (right – left) / 2;
// 三数取中
if (arr[left] > arr[mid]) std::swap(arr[left], arr[mid]);
if (arr[left] > arr[right]) std::swap(arr[left], arr[right]);
if (arr[mid] > arr[right]) std::swap(arr[mid], arr[right]);

// 将基准值放到left+1位置
std::swap(arr[mid], arr[left + 1]);
return arr[left + 1];
}

快排的平均时间复杂度是O(nlogn)，最坏情况是O(n²)，但通过优化基准值选择，可以降低最坏情况发生的概率。空间复杂度主要是递归调用栈的深度，平均为O(logn)，最坏为O(n)。