快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一 部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序 过程可以递归进行，以此达到整个数据变成有序序列。

需求

排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}

排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}

排序原理

1. 首先将默认第一个元素为关键值key，设置好关键值key后基于key进行排序。
2. 将大于或等于key的元素放到到数组右边，小于key的元素放到数组的左边。此时左边部分中各元素都小于 或等于key，而右边部分中各元素都大于或等于key；
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个key，将该部分数据分成左右两 部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

示例代码

public class Quick {
    /*
  比较v元素是否小于w元素
*/
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    /*
   数组元素i和j交换位置
    */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    /*
    对组内元素进行排序
     */
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    //对数组a中从索引lo到索引hi之间的元素进行排序
    private static void sort(Comparable[] a, int lo, int hi) {
        if(lo>=hi){
            return;
        }
        //需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）；
        int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引

        //让左子组有序
        sort(a,lo,partition-1);

        //让右子组有序
        sort(a,partition+1,hi);
    }
    private static int partition(Comparable[] a, int lo, int hi) {
        int key = lo;
        int begin = lo;
        int end = hi+1;
        while(true){
            while(less(a[key],a[--end])) {              //如果右边的元素小于key
                if (end == lo) {
                    break;
                }
            }
            while(less(a[++begin],a[key])){          //从左边开始轮
                if(begin==hi){
                    break;
                }
            }
            //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (begin>=end){
                break;
            }else{
                exch(a,begin,end);
            }
        }
        exch(a,key,end);
        return end;
    }

快速排序时间复杂度

快速排序是冒泡排序的的基础上改进的，但是效率比冒泡排序要高很多，因其跳跃性大，而冒泡排序只是相邻的两个数，每次排序只能和旁边交换，跳跃性比较小，因此效率相对比较低。

在一般情况下，快速排序的时间复杂度为O(log n)，而在最差情况下则是每次交换只交换一个元素，此时的时间复杂度为O(n)。

快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变。

快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。