揭秘高效快速排序：从代码实现到原理剖析

快速排序是一种高效的排序算法，它使用分治法来将一个数组分成两个子数组，然后递归地对这两个子数组进行排序。以下是完整的快速排序实现代码： ```cpp #include <iostream> #include <cstdlib> #include <ctime> using namespace std; const int n = 10; const int min_val = 10; const int max_val = 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_val, max_val); } } 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 pIndex = i; // pIndex是小于基准的元素的索引 for (int k = i; k < j; k++) { if (r[k] <= pivot) { swap(r[k], r[pIndex]); pIndex++; } } swap(r[pIndex], r[j]); // 把基准放到正确的位置 return pIndex; } void quicksort(int r[], int i, int j) { if (i < j) { int pIndex = partition(r, i, j); quicksort(r, i, pIndex - 1); // 递归排序左半部分 quicksort(r, pIndex + 1, j); // 递归排序右半部分 } } int main() { srand(time(0)); int a[n]; set(a, n); cout << "Unsorted array: "; show(a, n); quicksort(a, 0, n - 1); cout << "Sorted array: "; show(a, n); return 0; } ``` 代码解释： 1. getrand函数：生成一个在`min`和`max`之间的随机数。 2. set函数：用随机数填充数组。 3. show函数：打印数组内容。 4. partition函数：选择一个基准（这里选择的是数组的最后一个元素），然后将数组分为两部分，一部分小于等于基准，另一部分大于基准。最后返回基准的位置。 5. quicksort函数：递归地对数组进行快速排序。 6. main函数：初始化随机数种子，生成随机数组，调用快速排序并显示结果。 运行这段代码会输出未排序和已排序的数组。 ######[AI写代码神器 | 710点数解答 | 2024-11-14 10:44:25]