一、思想

快速排序是交换排序的一种，主要思想是分治法。

1. 选取一个数作为基准数，将数组中的数以该数为基准分为两部分；
2. 分别对这两部分递归的调用快速排序。
   核心操作就是如何以一个数为基准，把比它小的数放在它左边，比它大的数放在其右边

二、代码实现

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class 快速排序 {
    public static void main(String[] args) {
        Random r = new Random();
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = r.nextInt(100);
        }
//      for(int i=0;i<n;i++){
//          nums[i]=scan.nextInt();
//      }
        System.out.println(Arrays.toString(nums));
        new 快速排序().quickSort(nums, 0, n-1);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 对数组nums中[l,h]范围内的数进行排序
     * @param nums
     * @param l
     * @param h
     */
    public void quickSort(int[] nums, int l, int h) {
        if (l >= h) {
            return;
        }
        // 分治法：把数组分成两部分
        int mid = getMiddle(nums, l, h);
        quickSort(nums, l, mid);
        quickSort(nums, mid + 1, h);
    }

    /**
     * 以数组的第一个数为基准，<=该数的放在它左边，>=该数的放在它右边
     * 
     * @param nums
     * @param l
     * @param h
     * @return：返回基准数的新位置
     */
    private int getMiddle(int[] nums, int l, int h) {
        // 以l位置处的元素作为基准
        int temp = nums[l];
        // 右左左右来回比较
        int i = l;
        int j = h;
        while (i < j) {
            // 先从右边开始比较
            while (nums[j] >= temp && i < j) {
                j--;
            }
            if (i < j) {
                nums[i] = nums[j];
                i++;
            }
            while (nums[i] <= temp && i < j) {
                i++;
            }
            if (i < j) {
                nums[j] = nums[i];
                j--;
            }
        }
        if (i == j) {
            nums[i] = temp;
        }
        return i;
    }

}

三、参考文献

1
排序算法的比较与java实现