数组查找、排序算法

两大查找:线性查找二分查找
七大排序:插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序

线性查找 linearSearch

线性查找又称顺序查找,是一种最简单的查找方法,它的基本思想是从第一个记录开始,逐个比较记录的关键字,直到和给定的 K 值相等,则查找成功;若比较结果与文件中 n 个记录的关键字都不等,则查找失败。

假设一个数组中有 n 个元素,最好的情况就是要寻找的特定值就是数组里的第一个元素,这样仅需要 1 次比较就可以。而最坏的情况是要寻找的特定值不在这个数组或者是数组里的最后一个元素,这就需要进行 n 次比较。

算法实现(Java):

时间复杂度:平均情况O(n)、最好情况O(1)、最坏情况O(n)
空间复杂度:O(1)

二分查找 binarySearch

二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

算法实现(Java):

时间复杂度:平均情况O(logn)、最好情况O(1)、最坏情况O(logn)
空间复杂度:O(1)

时间复杂度是怎么算来的?这里只讨论最坏情况,很明显,无非就是看while (beg <= end)的循环次数。beg <= end条件的意思就是:只要还有至少一个元素,就继续循环下去。因为每次循环都会过滤掉 1/2 的元素(要么选择左边要么选择右边),假设数组长度为 n,第一次循环后,长度为 n/2,第二次循环后,长度为 n/4,第三次循环后,长度为 n/8,第 k 次循环后(最后一次),长度为 n/(2^k) = 1,2^k = n,k = log2(n),因此时间复杂度为O(logn)

插入排序 insertionSort

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place(原地)排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素腾出插入空间。

直接插入排序 - 动图演示

一般来说,插入排序都采用 in-place 在数组上实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤 2~5

如果比较操作的代价比交换操作大,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找插入排序(稍后介绍)。

算法实现(Java):

时间复杂度:平均情况O(n^2)、最好情况O(n)、最坏情况O(n^2)
空间复杂度:O(1)
算法稳定性:稳定

最好情况,即待排数组为升序排列。这种情况下,内层 for 循环的条件arr[j] > curVal将不成立,因此只需考虑外层 for 循环的次数,即为 n-1 次。因此时间复杂度为O(n)
最坏情况,即待排数组为降序排列。这种情况下,内层 for 循环的条件arr[j] > curVal始终成立,因此只需考虑j = i - 1; j >= 0,i 的取值范围为[1, n-1],则 j 的取值范围为[0, n-2],j = 0,循环 1 次,j = 1,循环 2 次,j = n-2,循环 n-1 次。总共循环的次数为 1 + 2 + 3 + … + n-1,即n(n-1)/2,因此时间复杂度为O(n^2)

排序算法稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且 ri 在 rj 之前,而在排序后的序列中,ri 仍在 rj 之前,则称这种排序算法是稳定的;否则称为不稳定的。

在上述的插入排序中,会改变元素位置的就是arr[j + 1] = arr[j]语句,因为是从后往前扫描的,而又只有比待排元素大的才会往后挪动,当遇到与之相等的元素时,循环条件已经不成立了,因此待排元素只会插入到它的后面,它们之间的相对顺序没有改变,即直接插入排序是稳定的

在直接插入排序中,找到插入位置 k 之前,必须经过 i - k 次比较,如果比较操作的开销比移动操作的开销大,可以考虑使用二分查找法来寻找合适的插入位置,即直接插入排序的变种 - 折半插入排序。算法实现如下(Java):

直接插入排序和折半插入排序的元素移动次数是一样的,但是折半插入排序的元素比较次数总体上会更少一些。因为存在额外的二分查找过程,如果元素之间的比较操作开销很小(如基本类型的比较)可能会得不偿失。也就是说,除非你确定元素之间的比较操作开销大(如引用类型,比较操作要调用 Comparable.compareTo() 或 Comparator.compare() 方法),否则不要尝试折半插入排序。

为了说明这个问题,我们分别使用直接插入排序和折半插入排序,将拥有 10000 个元素的 int[] 和 Integer[] 数组升序排列。

如果改成 100000(十万)个元素,差距更加明显:

希尔排序 shellSort

希尔排序算法是按其设计者希尔(Donald Shell)的名字命名,该算法由 1959 年公布,是插入排序的一种更高效的改进版本。它的做法不是每次一个元素挨一个元素的比较,而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置,然后增量缩小,最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  1. 插入排序在对几乎已经排好序的数据操作时,效率高,可以达到线性排序的效率
  2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据往前移动一个位置

希尔排序的算法思路:

  1. 取一正整数d1 (d1 < n),把全部记录分成 d1 个组,所有距离为 d1 倍数的记录看成一组,在各组内进行插入排序
  2. 然后取d2 (d2 < d1)
  3. 重复上述分组和排序操作,直到取di = 1 (i >= 1)位置,即所有记录成为一个组,最后对这个组进行直接插入排序

一般选 d1 约为 n/2,d2 为 d1 / 2,d3 为 d2 / 2,…,di = 1

希尔排序 - 图解

算法实现(Java):

时间复杂度:平均情况O(nlogn) ~ O(n^2)、最好情况O(n^1.3)、最坏情况O(n^2)
空间复杂度:O(1)
算法稳定性:不稳定

为什么希尔排序是不稳定的呢?举个例子 [5, 1, 2, 1, 3, 4],数组长度为 6,初始步长为 6 / 2 = 3,索引为 3 的元素 1 小于 5,将 1 插入到索引 0 处,因此改变了原索引 1 和原索引 3 的两个相同元素的相对位置,因此希尔排序是不稳定的

选择排序 selectionSort

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小的元素,将其与未排序序列的第一个元素交换位置。然后,再从剩余的未排序序列中寻找最小的元素,将其与未排序序列的第一个元素交换位置。以此类推,直到所有元素均排序完毕。

算法实现(Java):

时间复杂度:平均情况O(n^2)、最好情况O(n^2)、最坏情况O(n^2)
空间复杂度:O(1)
算法稳定性:不稳定

为什么选择排序是不稳定的呢?举个例子 [5, 2, 3, 4, 5, 1],在第一轮选择中,最小值为 1,将其与第一个 5 交换位置,此时两个 5 之间的相对顺序被改变,因此简单选择排序是不稳定的

堆排序 heapSort

要了解堆排序,首先要了解什么是(二叉堆),要了解二叉堆,还要先了解什么是完全二叉树

堆(英语:Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

除非特别指明,否则堆一般均指二叉堆,二叉堆实际是一颗完全二叉树,二叉堆性质如下:

  • 任意节点小于(或大于)它的所有后裔节点,最小元(或最大元)在堆的根上(堆序性)。
  • 因为是完全二叉树,因此除最底层外,其它层的节点均被元素填满,且最底层尽可能地从左到右填入。

根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

满二叉树:满二叉树
完全二叉树:完全二叉树
普通二叉树:普通二叉树

最大堆:最大堆
最小堆:最小堆

完全二叉树的几个性质(序号从 1 开始,从上到下,从左到右,依次编号):

  • 第 n 个节点的左子节点:2n
  • 第 n 个节点的右子节点:2n + 1
  • 第 n 个节点的双亲节点:floor(n / 2)
  • 最后一个非叶子节点:floor(len / 2)

完全二叉树的几个性质(序号从 0 开始,从上到下,从左到右,依次编号):

  • 第 n 个节点的左子节点:2n + 1
  • 第 n 个节点的右子节点:2n + 2
  • 第 n 个节点的双亲节点:floor((n - 1) / 2)
  • 最后一个非叶子节点:floor(len / 2) - 1

因为数组都是 Zero-Based(下标从 0 开始),因此我们主要关注后者。

因为这里主要讨论升序排列,因此选择最大堆,如果是降序排列,则应选择最小堆。

堆排序的算法思路:

  1. 首先,将数组看作一颗完全二叉树,将其构造成一个最大堆
  2. 此时,数组的头部元素就是最大的元素,将其与数组尾部元素交换
  3. 交换后,可能破坏了最大堆的性质,因此需要将剩下的序列调整为最大堆
  4. 调整完成后,头部元素又成为了最大的元素,然后将其与序列尾部元素交换
  5. 重复步骤 3~4

两个主要操作:最大堆构造最大堆调整,而最大堆构造本质还是最大堆调整,只不过是从最后一个非叶子节点开始,从后往前,从下往上,递归的调整。因此,我们只要实现了最大堆调整,就可以轻而易举的写出一个堆排序。

调整最大堆的思路:在交换首尾元素之前,最大堆的特性还在,将根节点与序列尾部元素交换后,很有可能破坏了最大堆的特性,因此,需要在根节点左子节点右子节点中找到最大值,如果根节点依旧是最大的,则无需调整,如果不是,则将其与最大的子节点交换,交换后,又有可能破坏了该子节点所在的二叉堆的性质,因此我们需要递归的进行调整,直到无需调整或到达序列末尾时为止。

堆排序的算法实现(Java):

时间复杂度:平均情况O(nlogn)、最好情况O(nlogn)、最坏情况O(nlogn)
空间复杂度:O(1)
算法稳定性:不稳定

为什么堆排序是不稳定的呢?举个例子 [1, 0, 1],初始时,无需调整即满足最大堆的定义,因此,将第一个 1 交换到数组末尾,交换后,仍然满足最大堆的定义,于是又将另一个 1 交换到数组倒数第二个位置,因此这两个 1 之间的相对顺序被改变了,即堆排序是不稳定的

冒泡排序 bubbleSort

冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对 n 个项目需要O(n^2)的比较次数,且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一,但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的运行时间,但是两种算法在需要的交换次数却很大地不同。在最坏的情况,冒泡排序需要 O(n^2) 次交换,而插入排序只要最多 O(n) 交换。冒泡排序的实现通常会对已经排序好的数列拙劣地运行(O(n^2)),而插入排序在这个例子只需要 O(n) 个运算。因此很多现代的算法教科书避免使用冒泡排序,而用插入排序取代之。冒泡排序如果能在内部循环第一次运行时,使用一个 flag 来表示有无需要交换的可能,也可以把最优情况下的复杂度降低到 O(n)。在这个情况,已经排序好的数列就无交换的需要。若在每次走访数列时,把走访顺序反过来,也可以稍微地改进效率。有时候称为鸡尾酒排序(稍后介绍),因为算法会从数列的一端到另一端之间穿梭往返。

冒泡排序的算法思路:

  • 比较相邻的元素,如果第一个比第二个大,就交换它们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

对于序列 [4, 2, 1, 3],长度为 4,排序过程(升序)如下:

  1. 第一轮交换,需要走访的索引范围为[0, 2]
    • 比较 4 和 2,因为 4 比 2 大,因此交换它们的位置,交换后序列为 [2, 4, 1, 3]
    • 比较 4 和 1,因为 4 比 1 大,因此交换它们的位置,交换后序列为 [2, 1, 4, 3]
    • 比较 4 和 3,因为 4 比 3 大,因此交换它们的位置,交换后序列为 [2, 1, 3, 4]
    • 第一轮交换结束,最大值 4 已经浮到了序列末尾,因此下轮交换不需要再考虑它
  2. 第二轮交换,需要走访的索引范围为[0, 1]
    • 比较 2 和 1,因为 2 比 1 大,因此交换它们的位置,交换后序列为 [1, 2, 3, 4]
    • 比较 2 和 3,因为 2 比 3 小,因此不需要进行交换,此时序列仍为 [1, 2, 3, 4]
    • 第二轮交换结束,最大值 3 已经浮到了序列末尾,因此下轮交换不需要再考虑它
  3. 第三轮交换,需要走访的索引范围为[0, 0]
    • 比较 1 和 2,因为 1 比 2 小,因此不需要进行交换,此时序列仍为 [1, 2, 3, 4]
    • 第三轮交换结束,最大值 2 已经浮到了序列末尾,因为只剩一个元素,结束排序

可以看出,长度为 4 的数组最多进行 3 轮交换,而每一次需走访的范围都逐步缩小,直到为 1。

算法实现(Java):

时间复杂度:平均情况O(n^2)、最好情况O(n)、最坏情况O(n^2)
空间复杂度:O(1)
算法稳定性:稳定

为什么冒泡排序是稳定的呢?举个例子 [1, 2, 1],第一轮交换后,2 浮到末尾,变成 [1, 1, 2];第二轮交换时,因为前面的 1 不会大于后面的 1,因此排序结束后,它们的相对顺序没有改变,即冒泡排序是稳定的

鸡尾酒排序(双向冒泡排序)
为什么叫鸡尾酒排序?其实我也不知道,其实它还有很多奇怪的名称,比如双向冒泡排序(Bidirectional Bubble Sort)、波浪排序(Ripple Sort)、摇曳排序(Shuffle Sort)、飞梭排序(Shuttle Sort)和欢乐时光排序(Happy Hour Sort)。本文中就以鸡尾酒排序来称呼它。

鸡尾酒排序是冒泡排序的轻微变形。不同的地方在于,鸡尾酒排序是从低到高然后从高到低来回排序,而冒泡排序则仅从低到高去比较序列里的每个元素。它可比冒泡排序的效率稍微好一点,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列 (2, 3, 4, 5, 1) 为例,鸡尾酒排序只需要访问一次序列就可以完成排序(先从后往前再从前往后),但如果使用冒泡排序则需要四次。但是在乱数序列状态下,鸡尾酒排序与冒泡排序的效率都很差劲。

鸡尾酒排序的算法思路:

  1. 先对数组从左到右进行冒泡排序(升序),结束后,最大的元素浮到最右端
  2. 再对数组从右到左进行冒泡排序(降序),结束后,最小的元素浮到最左端
  3. 以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到只剩一个元素

鸡尾酒排序的算法实现(Java):

时间复杂度:平均情况O(n^2)、最好情况O(n)、最坏情况O(n^2)
空间复杂度:O(1)
算法稳定性:稳定

快速排序 quickSort

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序 n 个项目要O(nlogn)(大 O 符号)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 O(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

分治法的基本思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题,递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

快速排序的算法思路:

  1. 从数列中挑出一个元素,称为基准(pivot)
  2. 所有比基准值小的元素移到基准前面,所有比基准值大的元素移到基准后面(相等的可到任意一边)。该操作称为分区(partition)操作,分区结束后,基准元素所处的位置就是最终排序后它的位置。
  3. 对”基准”左边和右边的两个子集,不断重复第 1 步和第 2 步,直到所有子集只剩下一个元素为止。

分区(partition)是快速排序的主要内容,用伪代码可以表示如下(原地分区版本):

首先,把基准元素移到末尾(如果直接选择最后一个元素为基准元素,那就不用移动),然后从左到右(除了最后的基准元素),循环移动小于等于基准元素的元素到数组的开头,每次移动 storeIndex 自增 1,表示下一个小于等于基准元素将要移动到的位置。循环结束后 storeIndex 所代表的位置就是基准元素的最终摆放位置。所以最后将基准元素所在位置(这里是 right)与 storeIndex 所代表的位置的元素交换。要注意的是,一个元素在到达它的最后位置前,可能会被交换很多次。

一旦我们有了这个分区算法,要写快速排列本身就很容易:

快速排序的算法实现(Java):

时间复杂度:平均情况O(nlogn)、最好情况O(nlogn)、最坏情况O(n^2)
空间复杂度:最好情况O(logn)、最坏情况O(n)
算法稳定性:不稳定

关于迭代版的几点说明:

  • 快速排序的最小递归深度为O(logn),最大递归深度为O(n),因此栈的容量至少为 arr.length,而又因为序列范围包含左右边界,因此需要2 * arr.length长度的数组来存储。
  • 因为”栈”这种数据结构是后进先出(LIFO)的,因此,后入栈的元素会比先入栈的元素更先出栈。在上例中,先将右边界入栈,再将左边界入栈,出栈时,就反过来了,左边界先出栈,右边界后出栈。

归并排序 mergeSort

归并排序(Merge Sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

归并操作(Merge),也叫归并算法,指的是将两个已经排序的序列合并成一个有序序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序,可用于内排序,也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

归并排序的算法思路:

  • 把 n 个记录看成 n 个长度为 1 的有序子表
  • 进行两两归并,得到 n/2 个长度为 2 的有序子表
  • 重复第 2 步直到所有记录归并成一个长度为 n 的有序表

归并排序(动图演示):归并排序 - 动图演示
[5, 2, 4, 6, 1, 3, 2, 6] 排序过程:归并排序 - 静态图示

归并排序的算法实现(Java):

时间复杂度:平均情况O(nlogn)、最好情况O(nlogn)、最坏情况O(nlogn)
空间复杂度:O(n)
算法稳定性:稳定

七大排序算法总结

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性 备注
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定 n 小时较好
希尔排序 O(nlogn)
~O(n^2)
O(n^1.3) O(n^2) O(1) 不稳定 都比较合适
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定 n 小时较好
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 n 大时较好
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定 n 小时较好
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)
~O(n)
不稳定 n 大时较好
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定 n 大时较好

相关参考资料:
常见排序算法【归档】
经典排序算法总结与实现
线性搜索 - 维基百科,自由的百科全书
二分搜索 - 维基百科,自由的百科全书
插入排序 - 维基百科,自由的百科全书
希尔排序 - 维基百科,自由的百科全书
选择排序 - 维基百科,自由的百科全书
堆排序 - 维基百科,自由的百科全书
冒泡排序 - 维基百科,自由的百科全书
鸡尾酒排序 - 维基百科,自由的百科全书
快速排序 - 维基百科,自由的百科全书
归并排序 - 维基百科,自由的百科全书