各位朋友我有快速排序问题提问

Question

为啥快排必须记录的是中间值啊

记录中间坐标就不行

这不是一样吗 我记录中间值 直接用中间值比较

记录中间坐标 用arr[mid]找中间值

但是记录中间坐标就排不了序 为什么啊？

Answer 1

快速排序并没有要求记录中间坐标。枢轴可以任意选的，通常也是选待排序段的第一个元素。

下面这段代码，有两种划分方式：partition_2 是将待排段第一个元素作为枢轴，一次划分后返回值为数轴最终位置。
partition是将待排段的最后一个元素作为枢轴。

    // 对A[p..r]进行排序, 小->大
    static void quickSort(vector<int>& A, int p, int r) {
        if (p < r) {
            // 对A[p, r]进行一次划分, 找枢轴位置q
            int q = partition(A, p, r);

            if (p < q)
                quickSort(A, p, q - 1);
            if (q < r)
                quickSort(A, q + 1, r);
        }
    }

    // 对A[p..r]进行一次划分, 枢轴位置q.
    // 满足A[p..q-1] <= A[q] <= A[q+1..r]
    static int partition(vector<int>& A, int p, int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j < r; ++j) {
            if (A[j] <= x) {
                ++i;
                std::swap(A[i], A[j]);
            }
        }

        std::swap(A[i + 1], A[r]);
        return i + 1;
    }

    static int partition_2(vector<int>& A, int p, int r) {
        int pivot = A[p];
        int low = p, high = r;
        while (low < high) {
            while (low < high && A[high] >= pivot) { --high; }
            A[low] = A[high];
            while (low < high && A[low] <= pivot) { ++low; }
            A[high] = A[low];
        }
        A[low] = pivot;
        return low;
    }

完整代码及测试方法见：

base/sort/QuickSort.cpp · fortunely/LeetCode_CPP - Gitee.com https://gitee.com/fortunely/leetcode_cpp/blob/master/base/sort/QuickSort.cpp