P1177 【模板】快速排序（Java）

题目：

输入输出样例

输入

5
4 2 4 5 1

输出

1 2 4 4 5

代码：

package 分治;
//没通过，好像是这个题需要取主元为中间值
import java.util.Scanner;

public class P1177快速排序 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for (int i = 0; i < n; i++) {
            a[i]=sc.nextInt();
        }

        //int[] a={4,2,4,5,1};
        QuickSort(a,0,a.length-1);
        for (int i=0;i<n;i++) {
            System.out.print(a[i]+" ");
        }
    }

    private static void QuickSort(int[] a, int left, int right) {
        if (left>right)
            return;
        int pivot=a[left];
        int low=left,high=right;
        while(low<high){
            //注意顺序
            while(low<high&&a[high]>=pivot) high--;
            while(low<high&&a[low]<=pivot) low++;
            if (low<high){
                int t=a[low];
                a[low]=a[high];
                a[high]=t;
            }
        }
        a[left]=a[low];
        a[low]=pivot;
        QuickSort(a,left,low-1);
        QuickSort(a,low+1,right);
    }


}