快速排序

[Ir1d]

https://oi-wiki.org/basic/quick-sort/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[Youngore]

线性找第k大的数，可以把代码给一下吗

[Youngore]

感谢!

[minghu6]

犹豫再三，还是想说建议改善一下 朴素快排的代码

1. C++不也有元组吗，何必单写一个结构，而且还要额外使用一个O(n)的辅助数组（我猜测该实现是由别的语言的实现经过不成熟的转换得来的）
2. 建议朴素算法先用先划分再递归排序的经典算法，这样易于理解

[realKKKah]

我看了一下,那个O(n)的辅助数组应该是为了非递归而用于记录待排序区间的起始点和终止点的?虽然我自己比较懒一般会直接写递归代码(笑)

[minghu6]

补充一句，通过划分找第 k 大的数显然是不稳定的，不同于查找第一个第k大的数，这点需要注意

[sbofgayschool]

@minghu6
犹豫再三，还是想说建议改善一下 朴素快排的代码

1. C++不也有元组吗，何必单写一个结构，而且还要额外使用一个O(n)的辅助数组（我猜测该实现是由别的语言的实现经过不成熟的转换得来的）
2. 建议朴素算法先用先划分再递归排序的经典算法，这样易于理解

那个快排代码为什么写成那样我也不是很清楚😂，可能是有些历史原因吧，应该是直接用了 这里的代码 ……

我个人认为您的建议很合理哈～

[Hope2075]

线性找顺序统计量（也就是第k大）存在最坏O(n)的算法，在算法导论中有，不过意义不大，可以考虑加进来

[Yohager]

@zcqscored0
线性找顺序统计量（也就是第k大）存在最坏O(n)的算法，在算法导论中有，不过意义不大，可以考虑加进来

median-of-medians?

[YJCCity]

最后面好像有一个括号漏了

[yangshuo-1]

三路快排是稳定的对吧，相同的元素相对顺序没有改变

[yangshuo-1]

不稳定

[zhangjialin996]

java递归快速排序：

import java.util.*;

public class  Main {
    public static void main(String... args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = in.nextInt();
        }

        quickSort(arr, 0, N - 1);

        for(int element : arr){
            System.out.print(element + " ");
        }
    }

    public static void quickSort(int[] arr, int start, int end){
        if(start < end) {
            int pivot = partition(arr, start, end);
            quickSort(arr, start, pivot - 1);
            quickSort(arr, pivot + 1, end);
        }
    }

    public static int partition(int[] arr, int start, int end){
        int pivot = arr[start];
        while (start < end) {
            while (start < end && pivot <= arr[end]) --end;
            arr[start] =arr[end];
            while (start < end && arr[start] <= pivot) ++start;
            arr[end] = arr[start];
        }
        arr[end] = pivot;
        return start;
    }
}

[zhangjialin996]

非递归：利用Stack模拟递归过程，Range类用于记录上下界

import java.util.*;

public class  Main {
    public static void main(String... args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = in.nextInt();
        }

        quickSort(arr);

        for(int element : arr){
            System.out.print(element + " ");
        }
    }

    public static void quickSort(int[] arr){
        Stack<Range> stack = new Stack<>();
        stack.push(new Range(0, arr.length - 1));

        while(!stack.isEmpty()){
            Range range = stack.pop();
            int left = range.left;
            int right = range.right;
            if(left >= right) continue;
            int pivot = arr[left];

            while(left < right) {
                while(left < right && arr[right] >= pivot) right--;
                arr[left] = arr[right];
                while(left < right && arr[left] <= pivot) left++;
                arr[right] = arr[left];
            }
            arr[left] = pivot;
            stack.push(new Range(range.left, left - 1));
            stack.push(new Range(left + 1, range.right));
        }
    }
}

class Range {
    int left;
    int right;
    public Range(int left, int right){
        this.left = left;
        this.right = right;
    }
}

[zhangjialin996]

三路快速排序：

package com.jialin.luogu;

import java.util.*;

public class  Main {
    public static void main(String... args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = in.nextInt();
        }
        quickSort(arr,0, arr.length - 1);

        for(int element : arr){
            System.out.print(element + " ");
        }
    }

    public static void quickSort(int[] arr, int left, int right){
        if(left >= right) return ;
        int len = right - left + 1;
        // [0, len)
        int pivot = arr[left + new Random().nextInt(len)];
        int a = left, b = left, k = right;
        while(b <= k){
            if(arr[b] > pivot) {
                int temp = arr[k];
                arr[k--] = arr[b];
                arr[b] = temp;
            }
            else if(arr[b] < pivot) {
                if(a != b){
                    arr[a] = arr[a] ^ arr[b];
                    arr[b] = arr[a] ^ arr[b];
                    arr[a] = arr[a] ^ arr[b];
                }
                a++;
                b++;
            }
//            else if(arr[b] < pivot && a != b) {
//                int temp = arr[a];
//                arr[a]= arr[b];
//                arr[b] = temp;
//                a++;
//                b++;
//            }
            else b++;
        }
        quickSort(arr, left, a - 1);
        quickSort(arr, k + 1, right);
    }
}

[zhangjialin996]

Leetcode 215
寻找第k大的数 => 数组排序后，索引nums.length - k处的元素：

class Solution {
    //  三路快速排序
    public static int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int left = 0, right = nums.length - 1;

        while(true){
            int len = right - left + 1;
            int pivot = nums[left + new Random().nextInt(len)];
            int l = left, r = right, cur = left;

            while(cur <= r){
                if(pivot > nums[cur]) {
                    swap(nums, cur, l);
                    cur++;
                    l++;
                }
                else if(pivot < nums[cur]) {
                    swap(nums, cur, r);
                    r--;
                }
                else cur++;
            }
            System.out.println(Arrays.toString(nums));
            if(k >= l && k <= r) break;
            else if(k > r) {
                left = r + 1;
            }else {
                right = l - 1;
            }
        }
        return nums[k];
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String... args){
        int[] nums = {3,2,1,5,6,4};
        int k = 2;
        System.out.println(findKthLargest(nums, k));
    }
}

[ATION001]

快速排序被卡成 $O(n^2)$ 的情况应该是数组本身已经有序，应该是可以排序前判断数组本身是否有序（仅为个人看法）。

[ATION001]

说错了别喷我，我不是很确定。