快速排序是冒泡排序的改进版，可以说是大名鼎鼎了，只要学过编程的人基本都有所耳闻，原理是通过遍历，判断每个数并放置在数组合适的位置。思路如下：

1. 选定一个基准值pivot（通常指定为数组第一个值），比基准值大的放在右侧，比基准值小的放在左侧
2. 指定左右两个指针分别为left，right ；left < right
3. 指定函数退出条件，即left > right
4. 先从右向左遍历，即右指针向左移动——right–操作，发现比pivot小的值暂停移动
5. 再从左向右遍历，即左指针向右移动——left++操作，发现比pivot大的值暂停移动
6. 交换左右指针发现的两个值的位置
7. 当两指针相遇，即left == right，当前值与pivot交换位置

代码实现

public class QuickSort {

    private QuickSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int j = partition(arr, l, r);
        sort(arr, l, j - 1);
        sort(arr, j + 1, r);
    }

    /**
     * 将l设置为标定点，l左侧一定小于l，l右侧一定大于l
     */
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {

        // 1.生成 [l,r] 之间的随机索引
        int p = l + (new Random()).nextInt(r - l + 1);
        // 2.交换最左侧和随机索引的位置，防止极端情况
        swap(arr, l, p);
        // 3.l是标定掉，防止极端情况的发送，索性将l随机重拍一下
        int j = l;

        // 4.将l设置为标定点，保证l左侧一定小于l，l右侧一定大于l
        for (int i = l + 1; i <= r; i++) {
            // 如果arr[i]<arr[l]，则交换双方位置
            if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, l, j);
        return j;
    }

    /**
     * 根据两个索引交互其在数组中的位置
     */
    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E m = arr[i];
        arr[i] = arr[j];
        arr[j] = m;
    }
}

代码测试

public static void main(String[] args) {
    Random random = new Random();
    Integer[] arrayList = new Integer[10000];
    for (int i = 0; i < 10000; i++) {
        arrayList[i] = random.nextInt(1000);
    }
    for (int i = 0; i < arrayList.length; i++) {
        System.out.print(arrayList[i] + "\t");
    }
    QuickSort.sort(arrayList);
    System.out.println();
    for (int i = 0; i < arrayList.length; i++) {
        System.out.print(arrayList[i] + "\t");
    }
}