Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        int num = Integer.parseInt(bufferedReader.readLine());
        int [] array = new int [num];
        String [] result = bufferedReader.readLine().split(" ");
        for (int i = 0;i<num;i++){
            array[i] = Integer.parseInt(result[i]);
        }
        quickSort(array,0,array.length-1);
        for(int i = 0; i <array.length;i++){
            System.out.print(array[i]+" ");
        }
        bufferedReader.close();
     }
    public static int getPivotKey(int[] array, int left, int right) {
        //三数取中，将中间元素放在第一个位置
        if ( left >= right )
            return -1;
        int mid =( left +  right  ) / 2;
        if ( array [ left ] < array [ right ])
        {
            if ( array [ right ] < array [mid])
                return right ;
            else if ( array [ left ] < array [mid])
                return mid;
            else
                return left ;
        }
        else
        {
            if ( array [ left ] < array [mid])
                return left ;
            else if ( array [ right ] < array [mid])
                return mid;
            else
                return right ;
        }
    }
    public static int PartSort(int array[],int left , int right){
        //每次进来取数值比较居中的元素的位置
        int midIndex = getPivotKey( array , left , right );
        swap(array,midIndex,right);
        int current = left;
        int prev = left-1;
        while (current<right){
            //只要a[cur] < key成立，则++prev，不管最后进不进去if循环
            // 找到小于基准值的元素
            // 两个指针一起走，若碰到大于基准值的元素前指针停下，后指针继续++
            if (array[current]<array[right]&&++prev!=current){
                swap(array,current,prev);
            }
            current++;
        }
        swap(array,++prev,right);
        return prev;
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }

    public static void quickSort(int array[] , int left , int right){
        if (left>=right) return;;
        //获取枢纽值
        int keyIndex = PartSort(array, left, right);
        //使用递归对两侧进行排序
        quickSort(array,left,keyIndex-1);
        quickSort(array,keyIndex+1,right);
    }
}