快速排序是一种常用的排序算法,其基本思想是通过递归地将数组分成两个子数组,然后对这两个子数组分别进行排序。具体步骤如下:
- 选择一个基准值,可以是数组中的任意一个元素。
- 将数组分成两部分,使得左边的元素都小于基准值,右边的元素都大于基准值。
- 递归地对左边和右边的子数组进行排序。
- 合并左右子数组,得到最终的有序数组。
C++实现快速排序的代码示例如下:
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int i = low, j = high, pivot = arr[low];
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
}
// 使用方法
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
quickSort(arr, 0, arr.size() - 1);
上述代码中,我们首先选择数组的第一个元素作为基准值,然后根据基准值将数组分成两部分。接着递归地对左右子数组进行排序,最终得到一个有序的数组。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 55@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/911838.html