目录
- 快速排序算法实现
- 快速排序实现
- `Partition` 函数
- `QuickSort` 函数
- `main` 函数
- 代码汇总
- 代码解释
- Partition 函数：
- QuickSort 函数：
- main 函数：
- 小结：
快速排序算法实现
快速排序（QuickSort）是一种高效的排序算法，采用分治法策略。它的核心思想是通过一个称为“枢轴”（pivot）的元素将数组分成两个子数组，使得左子数组中的所有元素都小于枢轴，而右子数组中的所有元素都大于枢轴，然后递归地对这两个子数组进行排序。以下是快速排序的 C++ 实现及其详细解释。
快速排序实现
Partition 函数
Partition 函数的作用是将数组分区，并返回枢轴元素的位置。下面是 Partition 函数的实现：
int Partition(int a[], int low, int high){int pivot = a[low]; // 将第一个元素作为 pivotwhile (low < high){while (low < high && a[high] >= pivot) --high;a[low] = a[high]; // 将小于 pivot 的元素移到低端 // 这里不能为了下一步位移，因为会导致a[high] = a[low]被错误填充 while (low < high && a[low] <= pivot) ++low;a[high] = a[low]; // 将大于 pivot 的元素移到高端} a[low] = pivot; // 将 pivot 放到最终的位置return low;
}
QuickSort 函数
QuickSort 函数是递归实现的排序函数，它在 Partition 函数的帮助下对数组进行排序：
void QuickSort(int a[], int low, int high){if (low < high){// 分治int pivotpos = Partition(a, low, high);QuickSort(a, low, pivotpos - 1); // 左半段排序QuickSort(a, pivotpos + 1, high); // 右半段排序}
}
main 函数
main 函数用于测试 QuickSort 算法：
int main() {int a[10] = {5, 3, 7, 8, 4, 2, 10, 9, 1, 6};QuickSort(a, 0, 9);// 输出排序后的数组for (int i = 0; i <= 9; i++){ cout << a[i] << ' '; }cout << endl;return 0;
}
运行结果
当你运行上述代码时，它会对数组进行快速排序，并输出排序后的结果：
1 2 3 4 5 6 7 8 9 10
代码汇总
#include<iostream> using namespace std; int Partition(int a[], int low, int high){int pivot = a[low]; // 将第一个元素作为 pivotwhile (low < high){while (low < high && a[high] >= pivot) --high;a[low] = a[high]; // 将小于 pivot 的元素移到低端 // 这里不能为了下一步位移，因为会导致a[high] = a[low]被错误填充 while (low < high && a[low] <= pivot) ++low;a[high] = a[low]; // 将大于 pivot 的元素移到高端} a[low] = pivot; // 将 pivot 放到最终的位置return low;
}void QuickSort(int a[], int low, int high){if (low < high){// 分治 int pivotpos = Partition(a, low, high);QuickSort(a, low, pivotpos - 1); // 左半段排序 QuickSort(a, pivotpos + 1, high); // 右半段排序}
}int main() {int a[10] = {5, 3, 7, 8, 4, 2, 10, 9, 1, 6};QuickSort(a, 0, 9);// 输出排序后的数组 for (int i = 0; i <= 9; i++){ cout << a[i] << ' '; }cout << endl;return 0;
}
代码解释
Partition 函数：
选择数组的第一个元素作为枢轴元素。
使用两个指针 low 和 high 从数组的两端向中间移动，寻找不满足条件的元素并交换。
最终将枢轴元素放置在正确的位置，并返回这个位置的索引。
QuickSort 函数：
递归地对分区后的左右子数组进行排序。
基于 Partition 函数返回的枢轴位置进行递归调用。
main 函数：
初始化一个待排序的数组，调用 QuickSort 函数进行排序。
输出排序后的结果。
小结：
关注我给大家分享更多有趣的知识，以下是个人公众号，提供 ||竞赛资料|| ||课程资料||
添加我的公众号即可：