QuickSort
快速排序(Quicksort),又称分区交换排序(partition-exchange sort),简称快排,是一种高效的排序算法。由英国计算机科学家 Tony Hoare 于 1959 年开发并于 1961 年发表,至今它仍然是一种常用的排序算法。事实上,如果实施得当,它可以比归并排序、堆排序快两到三倍。
快速排序(Quicksort)
基本原理
快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序,它采用了一种分治的策略,通常称其为 分治法(Divide-and-ConquerMethod)。
分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地求解这些子问题,然后将这些子问题的解组合为原问题的解。
算法步骤
- 从序列中挑出一个元素,作为"基准" (pivot)
- 把所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准值的后面(相同的数可以放到任一边),这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序,直到所有子序列的大小为 0 或 1,这时整体已经排好序了
算法图解
传送门 坐在马桶上看算法:快速排序
动画演示
参考实现
1 | import java.util.Arrays; |
partition的另一种写法,选取最右元素作为基准
1 | public static int partition2(int[] arr, int left, int right) { |
复杂度分析
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
快速排序 | \(O(nlogn)\) | \(O(nlogn)\) | \(O(n^2)\) | \(O(logn) \sim O(n)\) | In-place | 不稳定 |
References
https://en.wikipedia.org/wiki/Quicksort
-
2019-05-24
归并排序(Merge sort),是创建在归并操作上的一种基于比较的排序算法。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
-
2019-05-24
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
-
2019-05-24
桶排序(Bucket sort)或箱排序(Bin sort),是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是 鸽巢排序 的一种归纳结果。
-
2019-05-24
希尔排序(Shellsort),是一种就地比较排序。它可以被看作是交换排序(冒泡排序)或插入排序(插入排序)的泛化。该方法首先对彼此相距很远的元素对进行排序,然后逐步缩小要比较的元素之间的差距。从距离较远的元素开始,它可以比简单的最近邻交换更快地将一些不合适的元素移动到位。1959 年,Donald Shell 出版了第一个版本。Shellsort 的运行时间严重依赖于它使用的间隙序列。对于许多实际的变体,确定它们的时间复杂度仍然是一个悬而未决的问题。
-
2019-05-24
在计算机科学中,堆排序(Heapsort)是一种基于比较的排序算法。Heapsort 可以被认为是一种改进的选择排序:像该算法一样,它将输入分为排序区域和未排序区域,并通过提取最大元素并将其移动到排序区域来迭代缩小未排序区域。改进包括使用堆数据结构而不是线性时间搜索来找到最大值。