题目描述

quicksort

样例

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] arr = new int[n];
        String[] strs = reader.readLine().split(" ");
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(strs[i]);
        }
        quickSort(arr, 0, arr.length - 1);

        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        reader.close();
    }

    private static void quickSort(int[] arr, int start, int end){
        if (start>= end) return;
        int p = partition(arr,start,end);
        quickSort(arr,start,p-1);
        quickSort(arr,p+1,end);
    }
    private static int partition(int[] arr, int low, int high){
        int v = arr[low];
        int i = low, j = high+1;
        while(true){
            while(arr[++i] <= v){
                if (i==high) break;
            }
            while(arr[--j]>v){
                if (j==low) break;
            }
            if (i>=j) break;
            swap(arr,i,j);
        }
        swap(arr,low,j);
        return j;
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

算法1

时间复杂度

参考文献

JAVA 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

java 代码

blablabla