基本思想：

• 基于"二分"思想
• 找一个数作为基准数，然后左右俩个探针开始找茬，
• 先从右边开始找，找到比它小的数的位置a
• 接着从左边开始找，找到比它大的数，换位置b
• 如果他们的探针位置没有相遇，就交换a,b
• 如果探针他们遇到了，归位基准数
• 递归调用，左边与右边

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

/**
 * @author NIWA
 *
 * 
 * 依次输入5个数字
 */
public class Main {
    int[] a = new int[100];
    int temp;//基准数
    static int n;//排序个数
    int i;
    int j;
    public static void main(String[] args) {
        Main mMain = new Main();
        mMain.scanf();
        mMain.sort(1, n);
        mMain.print();

    }


    private void print() {
        for (int i = 1; i <= n; i++) {
            System.out.println(a[i]);
        }
    }

    /**
     *  输入数据
     * */
    private void scanf() {
        Scanner sc1 =new Scanner(System.in);
        n = sc1.nextInt();

        for (int i = 1; i <= n; i++) {
            Scanner sc2 = new Scanner(System.in);
            a[i] = sc2.nextInt();
        }
    }

    /**
     * 快速排序
     */
    private void sort(int left, int right) {
        if(left > right){
            return;
        }

        temp = a[left];

        i = left;
        j = right;
        while(i != j){
            //顺序很重要，要从右边开始向左找，找比基准数小的
            while(a[j] >= temp && i < j){
                j--;//如果大于temp，那就接着找
            }
            
            //从左边向右找比基准数大的
            while(a[i] <= temp && i < j){
                i++;
            }

            
            //如果还没相遇，那就交换两个数在数组中的位置
            if(i < j){
                int t;
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        
        //基准数归位，放到该放的位置
        a[left] = a[i];
        a[i] = temp;
        
        
        sort(left, i-1);//继续处理左边的，这里是一个递归的过程
        sort(i+1, right);//右边的
    }
}

测试

6
8 7 5 3 9 4

输出
3 4 5 7 8 9

时间复杂度

• 最坏情况，可以是=相邻的俩个数进行了交换，最差时间复杂度和冒泡排序一样是O(N^2)
• 平均时间复杂度为O(NlogN)