你所忽视的排序算法（上）

算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用语计算，数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

——维基百科

程序猿圈子里似乎都默然这样的一个等式：程序=数据结构+算法。思考起来，就感觉相当于：作文=语法+词语。这句话相当出名，因为这是1986年尼古拉斯赵四（逃）在获得图灵奖时说的一句话，现在听起来，似乎没有什么不正确的。当然，这就好比当年牛顿在1687年提出万有引力一样，现在看起来是废话一样，但是当时这句话确定奠定了程序的基础概念。

所以我们就来讲讲算法，那么问题来了，什么是算法呢？喏，开头已经引用了维基百科的对算法的定义，下面接而来了一段解释：

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和初始输入（可能为空）开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

看懂了吗？别急别急，没看懂没关系，我也不是很理解；不过没关系，我们用一句通俗的话来阐释一下：算法（Algorithm）就是解决问题的方法。所以我们就这样来理解就好了。

在InfoQ上有一篇文章《计算机科学最重要的32个算法》，介绍了二分查找法（Binary Search），快速傅里叶变换（Fast Fourier transform，FFT），哈希算法（Hashing），堆排序（Heaps）等等，有兴趣的可以看看。当然，我也是在学习中。今天这篇文章是算法系列的第一篇，我们先从排序算法（Sort）开始。

计划是来介绍十大常见的排序算法，为了控制文章篇幅，分上下两篇来介绍，一些算法定义解释和动态图过程分析展示大多来自于自由全面的维基百科。此文为上篇，介绍算法引入排序以及介绍部分简单的排序算法。下篇介绍剩余的排序算法和下一章预告。

排序

排序算法大致可以分为两大类：非线性时间比较类排序和线性时间非比较类。前者是通过比较来决定元素间的次序，其时间复杂度不能突破O（nlogn）；后者不通过比较来决定元素间的次序，但是可以突破基于比较排序的时间下界，以线性时间运行。有点数学基础的各位看官很好理解线性和非线性的区别，以及过程中会提到复杂度，这里不在赘述，以后有机会单开一篇介绍。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，常作为程序设计入门算法介绍。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

逻辑描述

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

代码实现

比较常见的算法，代码略。

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

逻辑描述

N个记录的直接选择排序可经过N-1趟直接选择排序得到有序结果。

  • 初始状态：无序区为R[1…n]，有序区为空
  • 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
  • n-1趟结束，数组有序化了

代码实现

比较常见的算法，代码略。

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

逻辑描述

插入排序在实现上，通常采用in-place排序（即只需用到{\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

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

代码实现

比较常见的算法，代码略。

希尔排序

希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。

逻辑描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
  • 按增量序列个数k，对序列进行k趟排序
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package org.pross.sort;

import java.util.Map;

/**
 * @describe:
 * @author:彭爽pross
 * @date: 2018/10/27
 */
public class ShellSort {

	public static int[] shellSort(int[] array) {
		int i;
		int j;
		int temp;
		//自定义间隔序列
		int number = array.length / 2;
		while (number >= 1) {
			for (i = number; i < array.length; i++) {
				temp = array[i];
				j = i - number;
				while (j >= 0 && array[j] < temp) {
					array[j + number] = array[j];
					j = j - number;
				}
				array[j + number] = temp;
			}
			number = number / 2;
		}

		return array;
	}
}

算法分析

希尔排序是基于插入排序的以下两点性质而提出改进方法的：1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

归并排序

归并排序（Merge sort，或mergesort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

逻辑描述

  1. 将序列每相邻两个数字进行归并操作，形成{\displaystyle ceil(n/2)}个序列，排序后每个序列包含两/一个元素
  2. 若此时序列数不是一个则将上述序列再次归并，形成{\displaystyle ceil(n/4)}个序列，每个序列包含四/三个元素
  3. 重复第2步操作，直到所有元素排序完毕，即序列数为1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package org.pross.sort;

/**
 * @describe: 归并排序
 * @author:彭爽pross
 * @date: 2018/10/27
 */
public class MergeSort {

	public static int[] mergeSort(int[] arr) {
		int[] orderedArr = new int[arr.length];
		for (int i = 2; i < arr.length * 2; i *= 2) {
			for (int j = 0; j < (arr.length + i - 1) / i; j++) {
				int left = i * j;
				int mid = left + i / 2 >= arr.length ? (arr.length - 1) : (left + i / 2);
				int right = i * (j + 1) - 1 >= arr.length ? (arr.length - 1) : (i * (j + 1) - 1);
				int start = left, l = left, m = mid;
				while (l < mid && m <= right) {
					if (arr[l] < arr[m]) {
						orderedArr[start++] = arr[l++];
					} else {
						orderedArr[start++] = arr[m++];
					}
				}
				while (l < mid)
					orderedArr[start++] = arr[l++];
				while (m <= right)
					orderedArr[start++] = arr[m++];
				System.arraycopy(orderedArr, left, arr, left, right - left + 1);
			}
		}
		return orderedArr;
	}
}

上篇介绍了，冒泡排序，选择排序，插入排序，希尔排序和归并排序。

所有代码可以在我的Github查阅。