用c加加写一个快速排序

分治法是一种常见的算法策略，它将大问题分解成较小的、相似的子问题，并递归地解决它们，最后合并结果。快速排序是一种基于分治思想的高效排序算法，它的基本步骤包括选择基准元素、分区操作以及递归地对左右两部分进行排序。 以下是使用 C++ 实现的简单版本的快速排序代码： ```cpp #include <iostream> using namespace std; void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition(int arr[], int low, int high) { int pivot = arr[high]; // 通常选择最后一个元素作为基准 int i = (low - 1); // Index of smaller element for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); // Move pivot to its correct position return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); // Before pi quickSort(arr, pi + 1, high); // After pi } } int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); cout << "Sorted array: \n"; for (int i=0; i < n; i++) cout << arr[i] << " "; return 0; } ``` 在这个例子中，`quickSort()` 函数负责递归调用，而 `partition()` 函数则完成了分区和基准元素交换的过程。运行这个程序会得到一个已排序的数组。

为了使用快速排序的思想求解给定无序序列a中的前k个最大元素，我们可以采取一种称为“快速选择”（QuickSelect）的变体，它基于快速排序的思想，但只对查找目标进行划分，而不是整个数组。以下是基本的步骤： 1. **选择枢轴**： 首先随机选择一个元素作为枢轴（pivot），这有助于平均情况下的性能。 2. **划分**： 利用枢轴将数组分为两个部分，一部分包含所有小于等于枢轴的元素，另一部分包含所有大于枢轴的元素。因为我们在找第k大元素，所以我们关心的是大于枢轴的部分。 3. **检查位置**： 如果枢轴右侧的元素个数大于等于k，那么我们就在这个分区里继续查找第k大元素。如果小于k，那么我们需要在左分区的剩余部分查找第(k-pivot_right_size)大元素，这里的pivot_right_size是右侧元素的数量。 4. **递归**： 根据上一步的结果，重复上述过程，直至找到第k大元素或确定其不在当前分区。 以下是简单的C++代码实现： ```cpp #include <vector> #include <cstdlib> // 对于random_shuffle using namespace std; int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } int quickSelectKthLargest(vector<int>& a, int k, int low, int high) { if (low == high) return a[low]; int pivot_index = partition(a, low, high); if (pivot_index == k - 1) return a[pivot_index]; else if (pivot_index > k - 1) return quickSelectKthLargest(a, k, low, pivot_index - 1); else return quickSelectKthLargest(a, k, pivot_index + 1, high); } vector<int> findTopK(vector<int>& a, int k) { vector<int> result(k); random_shuffle(a.begin(), a.end()); // 防止最坏情况（序列已经有序） for (int i = 0; i < k; i++) result[i] = quickSelectKthLargest(a, i + 1, 0, a.size() - 1); return result; } int main() { vector<int> a = {9, 2, 5, 1, 6, 7}; int k = 3; vector<int> top_k = findTopK(a, k); cout << "前" << k << "个最大的元素是："; for (int num : top_k) cout << num << " "; return 0; } ```