题目描述

快速排序

时间复杂度

nlogn

java 代码

import java.io.*;
import java.util.*;

class Main{
    static int[] nums;

    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());
        //读入一行，"空格"截断, java8 stream函数 字符转类型 mapToInt.最后转成数组;
        nums = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();

        quick_sort(0, n-1);

        for(int i: nums){
            System.out.print(i+" ");
        }
    }
    //快排模板 
    //
    //a.快排利用指针 左大右小swap. 
    //b.再迭代
    public static void quick_sort(int l, int r){
        //b1. 迭代终止条件
        if(l>=r)return;

        //a1.初始化指针, 小技巧, 两端各走多一位. 利用do while 可少一特判.
        int i = l-1, j = r+1;
        int x = nums[l+r>>1];

        //a2.利用指针 如果左大右小. swap
        while(i<j){
            //a【2.1】 左指针大于中值 stop.
            do i++; while(nums[i]<x);
            //a【2.2】 右指针小于中值 stop.
            do j--; while(nums[j]>x);

            //a【2.3】 未达终止条件. swap
            if(i<j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        //b2. 迭代
        //传入参数还是边界.只有i,j指针在变动.
        //所以可以利用指针和传入参数分割出左右范围.
        quick_sort(l,j);
        quick_sort(j+1,r);
    }
}