快速排序是一种要求时间最快的排序算法，其基本原理如下：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

第一种实现

实例：

实现：

public int getMiddle(int[] list, int low, int high) {
    int tmp = list[low]; // 数组的第一个作为中轴
    while (low < high) {
        while (low < high && list[high] >= tmp) {
            high--;
        }

        list[low] = list[high]; // 比中轴小的记录移到低端

        while (low < high && list[low] <= tmp) {
            low++;
        }

        list[high] = list[low]; // 比中轴大的记录移到高端
    }

    list[low] = tmp; // 中轴记录到尾
    return low; // 返回中轴的位置
}

public void quickSort(int[] list, int low, int high) {
    if (low < high) {
        int middle = getMiddle(list, low, high); // 将list数组进行一分为二
        quickSort(list, low, middle - 1); // 对低字表进行递归排序
        quickSort(list, middle + 1, high); // 对高字表进行递归排序
    }
}

第二种实现

public static void quickSort(int[] numbers, int start, int end) {   
    if (start < end) {   
        int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）   
        int temp; // 记录临时中间值   
        int i = start, j = end;   
        do {   
            while ((numbers[i] < base) && (i < end))   
                i++;   
            while ((numbers[j] > base) && (j > start))   
                j--;   
            if (i <= j) {   
                temp = numbers[i];   
                numbers[i] = numbers[j];   
                numbers[j] = temp;   
                i++;   
                j--;   
            }   
        } while (i <= j);   
        if (start < j)   
            quickSort(numbers, start, j);   
        if (end > i)   
            quickSort(numbers, i, end);   
    }   
}

第三种实现

public static List<Integer> quicksort(final List<Integer> numbers){
    if(numbers.size() <2)
        return numbers;

    final Integer pivot = numbers.get(0); // 选定的基准值（第一个数值作为基准值）   
    final List<Integer> lower = new ArrayList<Integer>();
    final List<Integer> higher = new ArrayList<Integer>();

    for(int i = 1; i < numbers.size();i++){
        if(numbers.get(i) < pivot)
            lower.add(numbers.get(i));
        else 
            higher.add(numbers.get(i));
    }

    final List<Integer> sorted = quicksort(lower);  //比基准值低的数再递归排序

    sorted.add(pivot);   //基准值在中间
    sorted.addAll(quicksort(higher));    //比基准值大的数再递归排序

    return sorted;
}

输出结果

public static void main(String[] args) {
    int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 34, 15, 35, 25,53, 51 };
    quickSort(a, 0, a.length - 1);
    System.out.println("从小到大快速排序：" + Arrays.toString(a));
}

打印结果：

从小到大快速排序：[5, 12, 13, 15, 25, 27, 34, 34, 35, 38, 49, 49, 51, 53, 64, 65, 76, 78, 97]