快速掌握 C++ 快速排序：含代码详解与实现

好的，让我们来完成这个快速排序的实现。快速排序是一种高效的排序算法，采用分治策略来对一个数组进行排序。以下是完整的代码： ```cpp #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; const int n = 10; const int min = 10; const int max = 99; int getrand(int min, int max) { return (rand() % (max - min + 1) + min); } void set(int r[], int n) { for (int i = 0; i < n; i++) r[i] = getrand(min, max); } void show(int r[], int n) { for (int i = 0; i < n; i++) cout << r[i] << " "; cout << endl; } int partition(int r[], int i, int j) { int pivot = r[j]; // 选择最后一个元素作为基准 int k = i - 1; for (int l = i; l < j; l++) { if (r[l] <= pivot) { k++; swap(r[k], r[l]); } } swap(r[k + 1], r[j]); return k + 1; } void quicksort(int r[], int i, int j) { if (i < j) { int p = partition(r, i, j); quicksort(r, i, p - 1); quicksort(r, p + 1, j); } } int main() { srand(time(0)); int a[n]; set(a, n); cout << "原始数组: "; show(a, n); quicksort(a, 0, n - 1); cout << "排序后的数组: "; show(a, n); return 0; } ``` 代码解释 1. 生成随机数： ```cpp int getrand(int min, int max) { return (rand() % (max - min + 1) + min); } ``` 这个函数生成一个在 `min` 和 `max` 之间的随机整数。 2. 初始化数组： ```cpp void set(int r[], int n) { for (int i = 0; i < n; i++) r[i] = getrand(min, max); } ``` 这个函数用随机数填充数组 `r`。 3. 显示数组： ```cpp void show(int r[], int n) { for (int i = 0; i < n; i++) cout << r[i] << " "; cout << endl; } ``` 这个函数输出数组 `r` 的内容。 4. 划分函数： ```cpp int partition(int r[], int i, int j) { int pivot = r[j]; // 选择最后一个元素作为基准 int k = i - 1; for (int l = i; l < j; l++) { if (r[l] <= pivot) { k++; swap(r[k], r[l]); } } swap(r[k + 1], r[j]); return k + 1; } ``` 这个函数将数组分成两部分，一部分小于或等于基准，另一部分大于基准，并返回基准的位置。 5. 快速排序函数： ```cpp void quicksort(int r[], int i, int j) { if (i < j) { int p = partition(r, i, j); quicksort(r, i, p - 1); quicksort(r, p + 1, j); } } ``` 这个函数递归地对数组进行排序。 6. 主函数： ```cpp int main() { srand(time(0)); int a[n]; set(a, n); cout << "原始数组: "; show(a, n); quicksort(a, 0, n - 1); cout << "排序后的数组: "; show(a, n); return 0; } ``` 主函数初始化数组，显示原始数组，调用快速排序函数，然后显示排序后的数组。 希望这对你有帮助！如果有任何问题，请随时提问。 ######[AI写代码神器 | 951点数解答 | 2024-11-14 10:46:29]