Java快速排序详解 Java快速排序案例讲解

交换类排序主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则“交换”之。在这类排序方法中最常见的是冒泡排序和快速排序。上一篇简单写了冒泡排序，这次简单写一写快速排序。

快速排序的思想：

快速排序是将分治法运用到排序问题中的一个典型例子，其基本思想是：通过一个枢轴（pivot）元素将 n 个元素的序列分为左、右两个子序列 Ll 和 Lr，其中子序列 Ll中的元素均比枢轴元素小，而子序列 Lr 中的元素均比枢轴元素大，然后对左、右子序列分别进行快速排序，在将左、右子序列排好序后，则整个序列有序，而对左右子序列的排序过程直到子序列中只包含一个元素时结束，此时左、右子序列由于只包含一个元素则自然有序。

对待排序序列进行划分：

使用两个指针 low 和 high 分别指向待划分序列 r 的范围，取 low 所指元素为枢轴，即 pivot = r[low]。划分首先从 high 所指位置的元素起向前逐一搜索到第一个比 pivot 小的元素，并将其设置到 low 所指的位置；然后从 low 所指位置的元素起向后逐一搜索到第一个比 pivot 大的元素，并将其设置到 high 所指的位置；不断重复上述两步直到 low = high 为止，最后将 pivot 设置到 low 与 high 共同指向的位置。

图示划分：

代码实现：

import java.util.Arrays;
 
public class QuickSortTest {
    public static void main(String[] args){
        Integer[] arr = {5,2,7,3,9,10,8,6,1,4};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
 
    //排序方法-假设从小到大排序
    public static void quickSort(Integer[] arr,int low,int high){
        if(low < high){
            int part=partition(arr,low,high);
            //递归调用
            quickSort(arr,low,part-1);
            quickSort(arr,part+1,high);
        }
    }
 
    //划分方法
    private static int partition(Integer[] arr,int low,int high){
        //使用 r[low]作为枢轴元素
        int pivot = arr[low];
        //从两端交替向内扫描
        while(low < high){
            while(low<high && arr[high] >= pivot) {high--;}
            //将比 pivot 小的元素移向低端
            arr[low] = arr[high];
            while(low<high && arr[low] <= pivot){low++;}
            //将比 pivot 大的元素移向高端
            arr[high] = arr[low];
        }
        //设置枢轴
        arr[low]=pivot;
        //返回枢轴元素位置
        return low;
    }
 
}

空间效率：

快速排序需要一个堆栈来实现递归。若每次划分都将序列均匀分割为长度相近的两个子序列，则堆栈的最大深度为 log n，但是，在最坏的情况下，堆栈的最大深度为 n。

时间效率：

快速排序算法的运行时间依赖于划分是否平衡，即根据枢轴元素 pivot 将序列划分为两个子序列中的元素个数，而划分是否平衡又依赖于所使用的枢轴元素。下面我们在不同的情况下来分析快速排序的渐进时间复杂度。

快速排序的最坏情况是，每次进行划分时，在所得到的两个子序列中有一个子序列为空。在快速排序过程中，如果总是选择r[low]作为枢轴元素，则在待排序序列本身已经有序或逆向有序时，快速排序的时间复杂度为Ο(n2)。

快速排序的最好情况是，在每次划分时，都将序列一分为二，正好在序列中间将序列分成长度相等的两个子序列。此时，算法的时间复杂度T(n) = Θ(n log n)。

在平均情况下，快速排序的时间复杂度 T(n) = kn ㏑ n，其中 k 为某个常数，经验证明，在所有同数量级的排序方法中，快速排序的常数因子 k 是最小的。因此就平均时间而言，快速排序被认为是目前最好的一种内部排序方法。
快速排序的平均性能最好，但是，若待排序序列初始时已按关键字有序或基本有序，则快速排序退化为冒泡排序，其时间复杂度为Ο(n2)。为改进之，可以采取随机选择枢轴元素pivot的方法，具体做法是，在待划分的序列中随机选择一个元素然后与r[low]交换，再将r[low]作为枢轴元素，作如此改进之后将极大改进快速排序在序列有序或基本有序时的性能，在待排序元素个数n较大时，其运行过程中出现最坏情况的可能性可以认为不存在。