十大排序算法快速排序之Java实现
快速排序
快速排序（Quick Sort）是对冒泡排序的一种改进，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数。
快速排序在1960年由查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为C. A. R. Hoare）提出，昵称为东尼·霍尔（Tony Hoare）。
算法步骤
- 从数组中选择一个轴点元素（pivot），假设每次都选择索引为0的元素为轴点元素。
- 利用pivot将数组分割成2个子数组，将小于pivot的元素放在pivot前面（左侧），将大于pivot的元素放在pivot后面（右侧），等于pivot的元素放哪边都可以。
- 递归对子序列进行前面两步操作，直到不能再分割（子序列中只剩下1个元素）。
快速排序的本质：逐渐将每一个元素都转换成轴点元素。
动图演示
代码实现
package com.morris.data.struct.sort.cmp;import com.morris.data.struct.sort.AbstractSort;/** * 快速排序 */public class QuickSort<E extends Comparable> extends AbstractSort<E> {@Overrideprotected 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==endreturn 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)。
更多精彩内容关注本人公众号：架构师升级之路
阳光穿透心脏的1/2处
Myth丶恋晨
朱雀
傷城~
向右看齐
还没有评论，来说两句吧...