c++

c++快速排序的方法是什么

小亿
87
2024-03-04 15:17:26
栏目: 编程语言

快速排序是一种常用的排序算法,其基本思想是通过递归地将数组分成两个子数组,然后对这两个子数组分别进行排序。具体步骤如下:

  1. 选择一个基准值,可以是数组中的任意一个元素。
  2. 将数组分成两部分,使得左边的元素都小于基准值,右边的元素都大于基准值。
  3. 递归地对左边和右边的子数组进行排序。
  4. 合并左右子数组,得到最终的有序数组。

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);

上述代码中,我们首先选择数组的第一个元素作为基准值,然后根据基准值将数组分成两部分。接着递归地对左右子数组进行排序,最终得到一个有序的数组。

0
看了该问题的人还看了