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

傷城~ 2023-02-28 01:54 111阅读 0赞

# 快速排序 #

快速排序（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个元素）。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]

## 动图演示 ##

![在这里插入图片描述][20200719140744278.gif]

## 代码实现 ##

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) { 
    ...

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]  
根据轴点元素分割出来的子数组极度不均匀，会导致出现最坏时间复杂度O(n^2)。

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: /images/20230209/ae9bae0db6fe47178860fd93b030d5cf.png
[20200719140744278.gif]: /images/20230209/47240090f20a4d95a03dde6caa24cace.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: /images/20230209/0ce739df7d0445bea66c05a12ea6cdb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: /images/20230209/438d5ddc0dfb40bfba40f0d439af6215.png
[20200627175030665.jpg]: /images/20230209/71174be070af45498928ddcbe9c668a7.png