十大排序算法快速排序之Java实现

快速排序

快速排序（Quick Sort）是对冒泡排序的一种改进，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数。

快速排序在1960年由查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为C. A. R. Hoare）提出，昵称为东尼·霍尔（Tony Hoare）。

算法步骤

1. 从数组中选择一个轴点元素（pivot），假设每次都选择索引为0的元素为轴点元素。
2. 利用pivot将数组分割成2个子数组，将小于pivot的元素放在pivot前面（左侧），将大于pivot的元素放在pivot后面（右侧），等于pivot的元素放哪边都可以。
3. 递归对子序列进行前面两步操作，直到不能再分割（子序列中只剩下1个元素）。

快速排序的本质：逐渐将每一个元素都转换成轴点元素。

动图演示

代码实现

package com.morris.data.struct.sort.cmp;

import com.morris.data.struct.sort.AbstractSort;

/**
 * 快速排序
 */
public class QuickSort<E extends Comparable> extends AbstractSort<E> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    private void sort(int begin, int end) {

        if(end - begin < 2) {
            return;
        }

        int pivotIndex = pivotIndex(begin, end);

        sort(begin, pivotIndex);
        sort(pivotIndex + 1, end);

    }

    /**
     * 返回轴点元素的真正索引
     * @param begin
     * @param end
     * @return
     */
    private int pivotIndex(int begin, int end) {

        // 随机选择一个元素跟begin位置进行交换，为了降低最好时间复杂度
        swap(begin, begin + (int)(Math.random() * (end - begin)));

        E pivot = array[begin];
        end--;

        while (begin < end) {

            while (begin < end) {
                // 从右向左扫描
                if(cmp(array[end], pivot) < 0) {
                    array[begin++] = array[end];
                    break;
                } else {
                    end--;
                }
            }

            while (begin < end) {
                // 从左向右扫描
                if(cmp(array[begin], pivot) > 0) {
                    array[end--] = array[begin];
                    break;
                } else {
                    begin++;
                }
            }
        }

        array[begin] = pivot; // begin==end

        return begin;
    }
}

在轴点左右元素数量比较均匀的情况下，同时也是最好的情况，所以最好时间复杂度和平均时间复杂度均为O(nlogn)。

如果轴点左右元素数量极度不均匀就会出现最坏情况，所以最坏时间复杂度为O(n^2)。

为了降低最坏情况的出现概率，一般采取的做法是：随机选择轴点元素。

由于递归调用的缘故，所以空间复杂度为O(logn)。

对相等元素的处理

当代码中下面两处的比较为<或>时，快速排序对相等元素的处理过程如下：

...
// 从右向左扫描
if(cmp(array[end], pivot) < 0) {
...
...
// 从左向右扫描
if(cmp(array[begin], pivot) > 0) {
...

如果数组中的所有元素都与轴点元素相等，利用目前的算法实现，轴点元素可以将数组分割成2个均匀的子序列。

当代码中下面两处的比较为<=或>=时，快速排序对相等元素的处理过程如下：

...
// 从右向左扫描
if(cmp(array[end], pivot) <= 0) {
...
...
// 从左向右扫描
if(cmp(array[begin], pivot) >= 0) {
...

根据轴点元素分割出来的子数组极度不均匀，会导致出现最坏时间复杂度O(n^2)。更多精彩内容关注本人公众号：架构师升级之路