P1177【模板】快速排序(JAVA语言)

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main{
    static Scanner in=new Scanner(System.in);
    static int n=in.nextInt();
    static long[] a=new long[n+5];
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int i=0,j=n-1;
        for(int t=0;t<n;t++){
            a[t]=in.nextInt();
        }
    //	daluan();		
    //	QuickSort(i,j);
        sort(i,j);
        for(int t=0;t<n;t++){
            System.out.print(a[t]+" ");
        }
    }

    private static void daluan() {
        // TODO Auto-generated method stub
        List<Integer> lst = new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            lst.add(Integer.valueOf(String.valueOf(a[i])));
        }
         
//        System.out.println(lst);
         
        Collections.shuffle(lst);
         for(int i=0;i<n;i++){
        	 a[i]=lst.get(i);
         }

    }

    private static void QuickSort(int start,int end) //start为待排序起点，end为待排序终点
    {
        if(start>=end)return;//如果待排序只有一个元素，直接return
        int i=start;
        int j=end;
        long k=a[start];
        while(i<j)
        {
            while(a[j]>=k&&i<j)
            {
                j--;
            }
            swap(i,j);
            k=a[j];
            
            while(a[i]<=k&&i<j)
            {
                i++;
            }
            swap(i,j);
            k=a[i];
        }
        QuickSort(start,i-1);
        QuickSort(j+1,end);
    }

    static void sort(int left,int right){
        int l=left;
        int r=right;
        long pivot=a[(left+right)/2];//找中间值
        long temp=0;
        while(l<r){
        while(a[l]<pivot) l++;
        while(a[r]>pivot) r--;
        if(l>=r) break;
        temp=a[l];
        a[l]=a[r];
        a[r]=temp;
        if(a[l]==pivot) --r;
        if(a[r]==pivot) ++l;
        }
        if(l==r){
        l++;
        r--;
        }
        if(left<r) sort(left,r);
        if(right>l) sort(l,right);
        }
        
    
    private static void swap(int i, int j) {
        long t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}