快排

流程：

1. 选定一个分界值，根据该分界值将数据分为左右两部分。
2. 将大于该值的数据放到右边，小于或等于该值的数据放到左边。（这样该值的左边部分的数据一定小于或等于该值，右边部分一定大于该值。也就是说选定的分界值已经处于最终排序的位置了。）
3. 然后将选定分界值的左边部分和右边部分重复上诉步骤。

Java代码

交换法（每次扫描到符合要求的数据，直接与分界值交换位置）：

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int key = arr[left];
        int i = left;
        int j = right;

        while (i != j) {
            while (i < j && arr[j] >= key) {
                j--;
            }
            swap(arr, i, j);

            while (i < j && arr[i] < key) {
                i++;
            }

            swap(arr, i, j);
        }

        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public static void swap(int[] arr, int src, int des) {
        int temp = arr[src];
        arr[src] = arr[des];
        arr[des] = temp;
    }
}

填坑法（将选定的分界值当作坑位，每次扫描到符合要求的数据项，直接往坑里填，然后该数据项位置为新坑位，最后将分界值填到属于它的位置）：

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int key = arr[left];
        int i = left;
        int j = right;

        while (i != j) {
            while (i < j && arr[j] > key) {
                j--;
            }

            if(i < j) {
                arr[i] = arr[j];
                i++;
            }

            while(i <j && arr[i] <= key) {
                i++;
            }

            if(i < j) {
                arr[j] = arr[i];
                j--;
            }
        }

        arr[i] = key;

        quickSort(arr, left,i -1);
        quickSort(arr, i + 1, right);
    }
}