题目描述

785 代码模板题

算法1

快速排序 $O(nlogn)$

Java 代码

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

public class Main {
    public static void main(String[] args) throws IOException {
//      创建数组，进行输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String trim = s.trim();
//        输入空值 直接返回即可
        if (trim.isEmpty()){
            return;
        }
        int n  = Integer.parseInt(s);
        int[] p = new int[n];
        String[] nums = br.readLine().split(" "); //切分字符数字
        for (int i = 0; i < p.length; i++) {
            p[i] = Integer.parseInt(nums[i]);
        }
        //模板进行快速排序
        quickSort(p,0,p.length-1);
        for (int j : p) {
            System.out.print(j + " ");
        }
        br.close();
    }
    public static void quickSort(int[] p , int l ,int r){
        if (p == null || l >= r){
            return;
        }
        int x = p[l+r >> 1] , i = l-1, j = r+1;
        while ( i<j) {
            while (p[++i] < x);
            while (p[--j] > x);
            if ( i<j ){
                int t = p[i];
                p[i] = p[j];
                p[j] = t;
            }
        }
        quickSort(p,l,j);
        quickSort(p,j+1,r);
    }
}