排序算法之快速排序(Quick Sort)

排序算法之快速排序(Quick Sort)

Scroll Down

基本思想

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法描述

快速排序使用分治法来把一个数列分为两个子数列。具体算法描述如下:
1.从数列中跳出一个元素,称为"基准"(pivot);
2.重新排列数列,所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准的后面(相同的数可以到任一边),该基准就处于数列的中间位置。这称为分区(partition)操作;
3.递归地(recursive)对小于基准值元素的子数列进行快速排序。

动图演示

快速排序

代码实现

快速排序最核心的步骤就是partition操作,即从待排序的数列中选出一个数最为基准,将所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准的后面(相同的数可以到任一边),该基准就处于数列的中间位置。partition函数返回基准的位置,然后可以对基准为止的左右子序列递归地进行同样的快拍操作,从而使整个序列有序。

基本思路

1.将数组的最后一个数right作为基准数key
2.分区过程:从数组的首元素begin开始想后找比key大的数(begin找大);end开始向前找比key小的数(end找小);找到后交换两者(swap),直到begin>=end终止遍历。最后将begin(此时begin==end)和最后一个数交换(这个时候end不是最后一个位置),即key作为中间数(左区间都是比key小的数,右区间都是比key大的数)
3.再对左右区间重复第2步,直到各区间只有一个数。
快速排序2

/**
 * partition操作
 * @param array
 * @param left 数列左边界
 * @param right 数列右边界
 * @return
 */
public static int partition(int[] array,int left,int right) {
        int begin = left;
        int end = right;
        int key = right;

        while( begin < end ) {
            //begin找大
            while(begin < end && array[begin] <= array[key])
                begin++;
            //end找小
            while(begin < end && array[end] >= array[key])
                end--;
            swap(array,begin,end);
        }
        swap(array,begin,right);
        return begin;   //返回基准位置
    }
 
/**
 * 交换数组内两个元素
 * @param array
 * @param i
 * @param j
 */
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

实现了partition操作,我们就可以递归地进行快速排序了

 /**
 * 快速排序方法
 * @param array
 * @param left 数列左边界
 * @param right 数列右边界
 * @return
 */
public static void Quicksort(int array[], int left, int right) {
        if(left < right){
            int pos = partition(array, left, right);
            Quicksort(array, left, pos - 1);
            Quicksort(array, pos + 1, right);
        }
    }

时间复杂度

快速排序平均时间复杂度为O(nlogn),最好时间复杂度为O(nlogn),最坏时间复杂度为O(n2)。
最好情况:基准选择得当,partition函数每次恰好能均分序列,其递归树的深度就为logn,时间复杂度为O(nlogn)。
最坏情况:选择了最大或者最小数字作为基准,每次划分只能将序列分为一个元素与其他元素两部分,此时快速排序退化为冒泡排序,如果用树画出来,得到的将会是一棵单斜树,即所有的结点只有左(右)结点的树,树的深度为 n,时间复杂度为O(n2)。

空间复杂度

快速排序的空间复杂度主要考虑递归时使用的栈空间。
在最好情况下,即partition函数每次恰好能均分序列,空间复杂度为O(logn);在最坏情况下,即退化为冒泡排序,空间复杂度为O(n)。平均空间复杂度为O(logn)。

稳定性

快速排序是不稳定的。

作者:Steven1997
链接:https://www.jianshu.com/p/47170b1ced23
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。