排序算法 java实现-上海财经大学统计与管理学院副教授快速排序算法解析

上海财经大学统计与管理学院副教授

1

简介

已有许多经典的排序算法，可以划分为两大类，比较类和非比较类，如下所示的十大经典排序算法。在以后有关算法和数据科学等行业面试，以及研究生复试设计算法面试时，排序算法几乎是必问题。通过下面的介绍，希望大家能愉快地理解算法背后的原理，并快速写出代码。

它们的算法复杂度各有不同，请参见下图。在数学上，可以证明比较类排序算法的复杂度的下界为 O(n log(n)). 然而，非比较类排序算法可以突破 O(n log n) 的下界排序算法 java实现，达到 O(n) 的线性界。

a. 说明：所谓排序的稳定性是指相等元素的顺序在输入和输出中是相同的。在实际中，大多数排序并不关心稳定性。

b. 在上述表格中，k 依赖于数据本身和算法设计，详细说明请见对应的算法。

c. 请注意，上表中的空间复杂度只考察了额外设置数组的长度，并没有考虑局部变量所占用的空间。

2

快速排序（Quick sort）

快速排序是一种分而治之的算法。有时称为“分区交换排序”（partition-exchange sort）。

由英国计算机科学家 Tony Hoare 于1960年提出。如果实施得当，它可以比主要竞争对手（归并排序和堆排序）快两到三倍。快速排序的数学分析表明，平均而言，该算法将进行 O(n log n) 比较，其中 n 为项数。最坏的情况，比较 O(n^2) 次，尽管很少见。

算法：

S1. 从数组中选择一个“基准”元素，然后根据其他元素是否小于或大于基准，将其他元素划分为两个子数组；

S2. 然后将子数组递归排序。

更多详细信息可参考 wiki

()

快速排序有广泛的应用，已经被一些语言内置为默认的排序算法，比如 Unix排序算法 java实现，也是 C 标准库排序算法 qsort，同时也是 Java 推荐的排序算法。

Vladimir Yaroslavskiy 在 2009 年提出了对偶基准快速排序算法（dual-pivot quick sort）。经过大量实例测试，Yaroslavskiy 的对偶已经被 Oracle 中 Java 7 的 runtime 库内置为默认排序算法。

这里有一个动画演示了如何快速排序，如何逐步实现，其中原始数组是 arr[] = {2,6,7,1,9,8,3,4,5}；

快速排序 C 语言实现

对偶基准快速排序的 C 语言实现 (dual-pivot Quicksort)

3

堆排序（Heap sort）

堆排序算法由 J. W. J. Williams 在1964年提出。

二叉堆是采用二叉树形式的堆数据结构。二叉堆定义为具有两个附加约束的二叉树：

a. 形状属性：二叉堆是完整的二叉树；也就是说，除了可能的最后一层（最深）之外，树的所有级别都已完全填充，并且，如果树的最后一层未完成，则从左到右填充该级别的节点。

b. 堆属性：根据某些总顺序，存储在每个节点中的数大于等于（≥）或小于等于（≤）节点子代中的数。

堆排序实现分两步：

a. 从给定数组构建二叉堆；

b. 迭代：

S1. 交换第一个（当前数组中最大的键）和最后一个键；

S2. 从其余数组中重建二叉堆。

尽管在大多数机器实践中，堆排序比快速排序要慢一些，但它具有更有利的最坏情况，即 O(n log n)。堆排序是原位算法，不是稳定的排序。

更多细节可参考 wiki

()

这里有一个动画演示了堆排序如何逐步实现，其中原始数组是 arr[] = {2,6,7,1,9,8,3,4,5}；

堆排序 C 语言实现

4

归并排序（Merge sort）

大多数可实现稳定的排序，即相等元素的顺序在输入和输出中是相同的。

归并排序是约翰·冯·诺伊曼（John von Neumann）于1945 年发明的分治法（Divide and Conquer）。自下而上的归并排序的详细描述和分析最早出现于 Goldstine 和冯·诺伊曼（von Neumann）在1948年的一份报告中。

从概念上讲，归并排序的工作方式如下：

S1. 将未排序的列表划分为 n 个子数组，每个子数组包含一个元素（将一个元素的列表视为已排序）；

S2. 重复合并子数组以产生新的排序子数组，直到仅剩一个子数组为止。最终得到排序列表。

更多细节可参考 wiki

()

这里有一个动画说明归并排序如何逐步实现，其中原始数组是 arr[] = {2,6,7,1,9,8,3,4,5}；

归并排序 C 语言实现

5

希尔排序（Shell sort）

希尔排序，也称为 Shell 排序或 Shell 的方法，是一种原位（in-place）比较排序。可以将其视为交换排序（冒泡排序）或插入排序的推广。

由 Donald Shell 于1959年首先提出。

算法：

S1. 列表称为 h-sorted，因此从任何地方开始考虑每个 h 元素都会给出一个排序列表；

S2. 从大的 h 开始，使元素可以用较大的步长移动数据，从而为较小的 h 排序减少移动次数；

S3. 如果列表被 k-sorted (其中 k

S4. 从 h 减少到 1 的排序方法，可保证最终得到排序列表。

更多细节可参考 wiki

()

这里有一个动画说明希尔排序如何逐步实现，其中原始数组是 arr[] = {2,6,7,1,9,8,3,4,5}；

希尔排序 C 语言实现

6

冒泡排序（Bubble sort）

又称为下沉排序，是一种简单的排序算法，它会反复遍历数组（或列表），比较相邻元素并进行交换。

冒泡排序的最坏情况和平均复杂度为 O(n^2) ，其中 n 是要排序的项数。大多数实用的排序算法通常具有更好的最坏情况或平均复杂度 O(n log n)。

此方法需要 n-1 个循环，并且在第 j 次循环需要 j-1 次比较。因此共需要 n(n-1)/2 次比较。

更多细节可参考 wiki

()

这里有一个动画说明冒泡排序如何逐步实现，原始数组为 arr[] = {2,6,7,1,9,8,3,4,5}；

冒泡排序 C 语言实现

7

选择排序（Selection sort）

该算法将输入数组分为两部分：

S1. 在数组的前面（左）从左到右建立的项的排序子数组；

S2. 剩余未排序项的子数组，占据数组的其余部分。

算法开始时，已排序的子数组为空，未排序的子数组为整个输入数组。

该算法通过在未排序的子数组中找到最小（或最大，取决于排序顺序）元素，将其与最左边的未排序元素交换（按排序顺序放置），并将子数组边界向右移动一个元素来进行。

选择排序的时间效率为 O(n^2)，因此有许多排序技术比选择排序具有更好的时间复杂度。选择排序优于其他排序算法的唯一一点是，它能使交换的数量最小化，在最坏的情况下为 n − 1。

更多细节可参考 wiki

()

这里有一个动画说明插入排序如何逐步实现，其中原始数组是 arr[] = {2,6,7,1,9,8,3,4,5}；

选择排序 C 语言实现

8

插入排序（Insertion sort）

插入排序是一种简单的排序算法，可以一次构建一个最终的排序数组（或列表）。在大型列表上，它的效率比快速排序，堆排序或归并排序*等更高级的算法低得多。但是，插入排序具有几个优点：

a. 实施简单：Jon Bentley 给出了三行 C 版本和五行优化版本。

b. 对于很小的数据集十分高效，非常类似于其他二次排序算法。

c. 在实践中算法复杂度低，优于选择排序或冒泡排序等算法。

d. 算法是自适应的，即对已经进行实质排序的数据集有效：当输入中的每个元素距离其排序位置不超过 k 个位置时，算法时间复杂度是 O(kn) 。

e. 稳定，即不使用相等的键更改元素的相对顺序。

f. 原位 (in-place)，即只需要恒定数量为 O(1) 的额外存储空间。

g. 实时，即可以实现对在线数据流排序。

算法：

S1. 插入排序迭代，每次重复消耗一个输入元素，并增加排序的输出列表；

S2. 在每次迭代时，插入排序都会从输入数据中删除一个元素，在排序列表中找到它所属的位置，然后将其插入那里；

S3. 重复直到没有输入元素剩余为止。

更多细节可参考 wiki

()

这里有一个动画说明插入排序如何逐步实现，其中原始数组是 arr[] = {2,6,7,1,9,8,3,4,5}；

插入排序 C 语言实现

9

计数排序（Counting sort）

计数排序是一种整数排序算法。

通过对每个键值不同的对象的数量进行计数，并对这些计数进行算术运算来确定每个键值在输出序列中的位置。

运行时间在项目数以及最大和最小键值之间的差异上是线性的，因此仅适用于键的变化不明显大于项目数的情况。

但是，它通常用作另一排序算法（基数排序）的子过程，该算法可以更有效地处理较大的键。

因为计数排序使用键值作为数组的索引，所以它不是比较类排序，比较排序的下界 O(n log n) 不适用。

更多细节可参考 wiki

()

这里有一个动画来说明计数排序如何逐步实现，其中原始数组是 arr[] = {2,6,6,4,9,8,6,4,5}；

计数排序 C 语言实现

10

桶排序（Bucket sort）

又称为箱排序 (Bin sort)

思路：

a. 将数组的元素分布到多个存储桶中；

b. 使用不同的排序算法，或通过递归应用存储桶排序算法，分别对每个存储桶进行排序。

可以通过比较来实现存储桶排序，因此也可以将其视为比较排序算法。

计算复杂度取决于用于对每个存储桶进行分类的算法，要使用的存储桶数以及输入是否为均匀分布。

算法：

S1. 设置最初为空的“存储桶”数组；

S2. 分散：遍历原始数组，将每个对象放入其存储桶中；

S3. 对每个非空存储桶进行排序；

S4. 聚集：按顺序访问存储桶，然后将所有元素放回到原始数组中。

更多细节可参考 wiki

()

这里有一个动画说明了桶排序如何逐步实现，其中原始数组是 arr[] = {12,6,27,21,39,48,33,34,25,28,31,35,18}；

桶排序 C 语言实现

11

基数排序（Radix sort）

基数排序是一种非比较排序算法。它通过根据元素的基数创建元素并将其分配到存储桶中来避免进行比较。

基数排序可以追溯到1887年 Herman Hollerith 在制表机上的工作。最早于1923年，基数排序算法已成为一种常用的排序打孔卡的方法。

基数排序是第一存储高效的计算机算法，由麻省理工学院 (MIT) 的 Harold H. Seward 在1954年提出。由于人们认为需要对未知尺寸的铲斗进行可变分配，因此计算机化的基数排序以前被认为是不切实际的。

现在，基数排序最常应用于二进制字符串和整数集合。

更多细节可参考 wiki

()

这里有一个动画演示了如何实现基数排序，其中原始数组是 arr[] = {281, 33, 52, 86, 712, 24, 9, 67, 107, 3, 88, 302}；

基数排序 C 语言实现

12

总结

本文总结了十种经典排序算法的核心思想、C 语言代码实现，以及动画演示。

a. 由于冒泡排序、选择排序和插入排序的算法复杂度为 O(n^2)，因此在实际中不常用，在课堂上常做例子讲解。

b. 由于对数据有特殊要求，比如要求整数数据的最大和最小键值 (key-value) 差异很小，因此计数算法、桶排序和基数排序在实际中并不常用。

c. 由于快速排序，堆排序，希尔排序和归并排序算法的复杂度较低，因此在实践中经常被使用。因为在实际中平均运行时间较少，快速排序往往是四种排序算法的首选。