前言

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。八大排序算法均属于内部排序。如果按照策略来分类，大致可分为：交换排序、插入排序、选择排序、归并排序和基数排序。如下图所示：

alt

下表给出各种排序的基本性能，具体分析请参看各排序的详解

4SLFjU.png

1. 冒泡排序

冒泡排序是一种交换排序。其两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。

1.1 算法思想

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

1.2 效果示意图

　　假设有一个大小为 N 的无序序列。以升序冒泡排序为例，冒泡排序就是要每趟排序过程中通过两两比较相邻元素，将小的数字放到前面，大的数字放在后面,其示意图如下：

alt

1.3 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding:utf-8 -*-

def bubbleSort(input_list):
	'''
	函数说明:冒泡排序（升序）
	Parameters: input_list - 待排序列表
	Returns: sorted_list - 升序排序好的列表
	'''
	if len(input_list) == 0:
		return []
	sorted_list = input_list
	for i in range(len(sorted_list) - 1):
		print('第%d趟排序:' % (i + 1))
		for j in range(len(sorted_list) - 1):
			if sorted_list[j + 1] < sorted_list[j]:
				sorted_list[j], sorted_list[j + 1] = sorted_list[j + 1], sorted_list[j]
			print(sorted_list)
	return sorted_list

if __name__ == '__main__':
	input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
	print('排序前:', input_list)
	sorted_list = bubbleSort(input_list)
	print('排序后:', sorted_list)

1.4 算法分析

1.4.1 时间复杂度

　　若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好时间复杂度为O(N)。但是上述代码，不能扫描一趟就完成排序，它会进行全扫描。所以一个改进的方法就是，当冒泡中途发现已经为正序了，便无需继续比对下去。改进方法一会儿介绍。若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax = N(N-1)/2 = O(N^2)
Mmax = 3N(N-1)/2 = O(N^2)

　　冒泡排序的最坏时间复杂度为O(N^2)。因此，冒泡排序的平均时间复杂度为O(N^2)。

　　总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。

1.4.2 算法稳定性

　　假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

　　冒泡排序就是把小的元素往前调或者把大的元素往后调。是相邻的两个元素的比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

1.5 冒泡优化

　　对冒泡排序常见的改进方法是加入标志性变量exchange，用于标志某一趟排序过程中是否有数据交换。如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。 

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
# -*- coding:utf-8 -*-

def bubbleSort(input_list):
	'''
	函数说明:冒泡排序（升序）
	Parameters: input_list - 待排序列表
	Returns: sorted_list - 升序排序好的列表
	'''
	if len(input_list) == 0:
		return []
	sorted_list = input_list
	for i in range(len(sorted_list) - 1):
		bChanged = False
		print('第%d趟排序:' % (i + 1))
		for j in range(len(sorted_list) - i - 1):
			if sorted_list[j + 1] < sorted_list[j]:
				sorted_list[j], sorted_list[j + 1] = sorted_list[j + 1], sorted_list[j]
				bChanged = True
			print(sorted_list)
		if not bChanged:
			break
	return sorted_list


if __name__ == '__main__':
	input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
	print('排序前:', input_list)
	sorted_list = bubbleSort(input_list)
	print('排序后:', sorted_list)

2. 插入排序

直接插入排序（Insertion Sort）序是一种最简单的插入排序

2.1 算法思想

　　插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，知道全部插入完成。

2.2 效果示意图

　　直接插入排序，每次将一个新数据插入到有序队列中的合适位置里。

alt

2.3 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def insertSort(input_list):
	if len(input_list) == 0:
		return []
	sorted_list = input_list

	for i in range(1, len(sorted_list)):
		temp = sorted_list[i]
		j = i - 1
		while j >=0 and temp < sorted_list[j]:
			sorted_list[j + 1] = sorted_list[j]
			j -= 1
		sorted_list[j + 1] = temp
	return sorted_list


if __name__ == '__main__':
	input_list = [6, 4, 8, 9, 2, 3, 1]
	print('排序前:', input_list)
	sorted_list = insertSort(input_list)
	print('排序后:', sorted_list)

2.4 算法分析

2.4.1 时间复杂度

　　当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N^2)。所以，数据越接近正序，直接插入排序的算法性能越好。

2.4.2 空间复杂度

　　由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。

2.4.3 算法稳定性

　　直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。

2.4.4 优化

　　因为在一个有序序列中查找一个插入位置，以保证有序序列的序列不变，所以可以使用二分查找，减少元素比较次数提高效率。

　　二分查找是对于有序数组而言的，假设如果数组是升序排序的。那么，二分查找算法就是不断对数组进行对半分割，每次拿中间元素和目标数字进行比较，如果中间元素小于目标数字，则说明目标数字应该在右侧被分割的数组中，如果中间元素大于目标数字，则说明目标数字应该在左侧被分割的数组中。 

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
def BinarySearch(input_list, end, value):
	left = 0
	right = end - 1
	while left <= right:
		middle = left + (right - left) // 2
		if input_list[middle] > value:
			right = middle - 1
		else:
			left = middle + 1

	return left if left < end else -1

def BinaryInsertSort(input_list):
	if len(input_list) == 0:
		return []
	result = input_list
	for i in range(1, len(input_list)):
		j = i - 1
		temp = result[i]
		insert_index = BinarySearch(result, i, result[i])
		if insert_index != -1:
			while j >= insert_index:
				result[j + 1] = result[j]
				j -= 1
			result[j + 1] = temp
	return result


if __name__ == '__main__':
	input_list = [6, 4, 8, 9, 2, 3, 1]
	print('排序前:', input_list)
	sorted_list = BinaryInsertSort(input_list)
	print('排序后:', sorted_list)

3 希尔排序

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。希尔排序，也称递减增量排序算法，以其设计者希尔（Donald Shell）的名字命名，该算法由 1959 年公布。

3.1 算法思想

　　我们举个例子来描述算法流程:

　　假设有这样一组数 {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10}，如果我们以步长为 5 开始进行排序： 

1
2
3
4
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

　　然后我们对每列进行排序：

1
2
3
4
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

　　将上述四行数字，依序接在一起时我们得到：{10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45}，然后再以 3 为步长： 

1
2
3
4
5
6
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

　　同样我们对每列进行排序：

1
2
3
4
5
6
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

　　最后以 1 为步长进行排序（此时就是简单的插入排序了）。

　　可想而知，步长的选择是希尔排序的重要部分。算法最开始以一定的步长进行排序，然后会继续以更小的步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为直接插入排序，这就保证了数据一定会被全部排序。

3.2 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def shellSort(input_list):
	length = len(input_list)
	if length <= 1:
		return input_list
	sorted_list = input_list
	gap = length // 2
	while gap > 0:
		for i in range(gap, length):
			j = i - gap
			temp = sorted_list[i]
			while j >= 0 and temp < sorted_list[j]:
				sorted_list[j+gap] = sorted_list[j]
				j -= gap
			sorted_list[j+gap] = temp
		gap //= 2
	return sorted_list 


if __name__ == '__main__':
	input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
	print('排序前:', input_list)
	sorted_list = shellSort(input_list)
	print('排序后:', sorted_list)

3.3 算法分析

3.3.1 时间复杂度

　　步长的选择是希尔排序的重要部分，只要最终步长为1任何步长序列都可以工作。

　　算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

　　步长序列的不同，会导致最坏的时间复杂度情况的不同。

　　上例以N/2为步长的最坏时间复杂度为N^2。

　　Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比O(N^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

　　用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

3.3.2 算法稳定性

　　希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。

3.3.3 直接插入排序和希尔排序的比较
  • 直接插入排序是稳定的；而希尔排序是不稳定的。
  • 直接插入排序更适合于原始记录基本有序的集合。
  • 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
  • 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
  • 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。

4 快速排序

快速排序是一种交换排序，它由C. A. R. Hoare在1962年提出。

4.1 算法思想

　　快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

4.2 效果示意图

alt

　　上图中，演示了快速排序的处理过程：

　　初始状态为一组无序的数组：2、4、5、1、3。经过以上操作步骤后，完成了第一次的排序，得到新的数组：1、2、5、4、3。

　　新的数组中，以2为分割点，左边都是比2小的数，右边都是比2大的数。因为2已经在数组中找到了合适的位置，所以不用再动。2左边的数组只有一个元素1，所以显然不用再排序，位置也被确定。（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。而对于2右边的数组5、4、3，设置left指向5，right指向3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。

4.3 算法实现

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
36
37
def QuickSort(input_list, left, right):
	'''
	函数说明:快速排序（升序）
	Parameters: input_list - 待排序列表
	Returns: 无
	'''	
	def division(input_list, left, right):
		'''
		函数说明:根据left和right进行一次扫描，重新找到基准数
		Parameters:
			input_list - 待排序列表
			left - 左指针位置
			right - 右指针位置
		Returns: left - 新的基准数位置
		'''	
		base = input_list[left]
		while left < right:
			while left < right and input_list[right] >= base:
				right -= 1
			input_list[left] = input_list[right]
			while left < right and input_list[left] <= base:
				left += 1
			input_list[right] = input_list[left]
		input_list[left] = base
		return left

	if left < right:
		base_index = division(input_list, left, right)
		QuickSort(input_list, left, base_index - 1)
		QuickSort(input_list, base_index + 1, right)


if __name__ == '__main__':
	input_list = [6, 4, 8, 9, 2, 3, 1]
	print('排序前:', input_list)
	QuickSort(input_list, 0, len(input_list) - 1)
	print('排序后:', input_list)

4.4 算法分析

4.4.1 时间复杂度

　　 当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。

4.4.2 空间复杂度

　　 快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 logN次的分割处理，所以占用空间也是 logN 个。

4.4.3 算法稳定性

　　 在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。

5 简单选择排序

简单选择排序是一种选择排序。
选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

5.1 算法思想

　　 简单排序很简单，它的大致处理流程为：

  • 从待排序序列中，找到关键字最小的元素；
  • 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
  • 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

5.2 效果示意图

　　 如下图所示，每趟排序中，将当前第 i 小的元素放在位置 i 上。

alt

5.3 算法实现

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
def SelectSort(input_list):
	'''
	函数说明:简单选择排序（升序）
	Parameters: input_list - 待排序列表
	Returns: sorted_list - 升序排序好的列表
	'''	
	if len(input_list) == 0:
		return []
	sorted_list = input_list
	length = len(sorted_list)
	for i in range(length):
		min_index = i
		for j in range(i + 1, length):
			if sorted_list[min_index] > sorted_list[j]:
				min_index = j
		if min_index == i:
			continue
		temp = sorted_list[i]
		sorted_list[i] = sorted_list[min_index]
		sorted_list[min_index] = temp
	return sorted_list


if __name__ == '__main__':
	input_list = [6, 4, 8, 9, 2, 3, 1]
	print('排序前:', input_list)
	sorted_list = SelectSort(input_list)
	print('排序后:', sorted_list)

5.4 算法分析

5.4.1 时间复杂度

　　 简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数总是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.当序列反序时，移动次数最多，为3N (N - 1) / 2。

　　 所以，综合以上，简单排序的时间复杂度为 O(N^2)。

5.4.2 空间复杂度

　　 简单选择排序需要占用 1 个临时空间，用于保存最小值得索引。

5.4.3 稳定性

　　 在简单选择排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。

6 堆排序

堆排序是一种选择排序。选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止

6.1 算法思想

　　 堆排序是利用堆的性质进行的一种选择排序。

　　 堆是一棵顺序存储的完全二叉树。

  • 其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
  • 其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

　　 举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：

  • Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
  • Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

　　 其中i=1,2,…,n/2向下取整。

如下图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

alt

堆中有两个结点，元素3和元素8。

元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：

设当前元素在数组中以R[i]表示，那么，

  1. 它的左孩子结点是：R[2*i+1];
  2. 它的右孩子结点是：R[2*i+2];
  3. 它的父结点是：R[(i-1)/2];
  4. R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；如此反复，直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作：

  1. 根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）；
  2. 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。；

当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下，如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }

构造初始堆过程如下：

alt

堆排序过程如下：

alt

通过以上两幅图，应该能很直观的演示堆排序的操作处理。

看完上面所述的流程你可能有一个疑问：如何确定最后一个非叶子结点？

其实这是有一个公式的，设二叉树结点总数为 n，则最后一个非叶子结点是第 ⌊n/2⌋ 个。

6.2 效果示意图

　　 堆排序的效果示意图如下：

alt

6.3 算法实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def HeadSort(input_list):
	'''
	函数说明:堆排序（升序）
	Parameters:	input_list - 待排序列表
	Returns:    sorted_list - 升序排序好的列表
	'''
	def HeadAdjust(input_list, parent, length):
		'''
		函数说明:堆调整，调整为最大堆
		Parameters:
			input_list - 待排序列表
			parent - 堆的父结点
			length - 数组长度
		Returns:
			无
		'''	
		temp = input_list[parent]
		child = 2 * parent + 1

		while child < length:
			if child + 1 < length and input_list[child] < input_list[child+1]:
				child += 1
			if temp >= input_list[child]:
				break
			input_list[parent] = input_list[child]
			parent = child
			child = 2 * parent + 1
			
		input_list[parent] = temp

	if len(input_list) == 0:
		return []
	sorted_list = input_list
	length = len(sorted_list)

	for i in range(0, length // 2)[::-1]:
		HeadAdjust(sorted_list, i, length)
    print("构建起始堆", sorted_list)
    
	for j in range(1, length)[::-1]:
		sorted_list[0], sorted_list[j] = sorted_list[j], sorted_list[0]
		HeadAdjust(sorted_list, 0, j)
		print('第%d趟排序:' % (length - j), end = '')
		print(sorted_list)

	return sorted_list


if __name__ == '__main__':
	input_list = [6, 4, 8, 9, 2, 3, 1]
	print('排序前:', input_list)
	sorted_list = HeadSort(input_list)
	print('排序后:', sorted_list)

6.4 算法分析

6.4.1 时间复杂度

　　 首先计算建堆的时间，也就是下面的代码，分析得出时间复杂度为 O(n)。 

1
2
3
# 建立初始堆
for i in range(0, length // 2)[::-1]:
    HeadAdjust(sorted_list, i, length)

　　 接下来就是排序的时间，即下面的代码： 

1
2
3
4
# 进行n-1次循环，完成排序
for j in range(1, length)[::-1]:
    sorted_list[0], sorted_list[j] = sorted_list[j], sorted_list[0]
    HeadAdjust(sorted_list, 0, j)

　　 HeapAdjust() 耗时 logn，共 n 次，故排序时间为 O(nlogn)。

　　 堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。

6.4.2 稳定性

　　 堆排序是一种不稳定的排序方法。因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

7 归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

7.1 算法思想

　　 该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

7.2 效果示例图

　　 分而治之：

alt

　　 可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。

7.3 算法实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def MergeSort(input_list):
	'''
	函数说明:归并排序（升序）
	Parameters: input_list - 待排序列表
	Returns:    sorted_list - 升序排序好的列表
	'''
	def merge(input_list, left, mid, right, temp):
		'''
		函数说明:合并函数
		Parameters:	
		    input_list - 待合并列表
			left - 左指针
			right - 右指针
			temp - 临时列表
		'''	
		i = left
		j = mid + 1
		k = 0

		while i <= mid and j <= right:
			if input_list[i] <= input_list[j]:
				temp[k] = input_list[i]
				i += 1
			else:
				temp[k] = input_list[j]
				j += 1
			k += 1

		while i <= mid:
			temp[k] = input_list[i]
			i += 1
			k += 1
		while j <= right:
			temp[k] = input_list[j]
			j += 1
			k += 1

		k = 0
		while left <= right:
			input_list[left] = temp[k]
			left += 1
			k += 1

	def merge_sort(input_list, left, right, temp):
		if left >= right:
			return;
		mid = (right + left) // 2
		merge_sort(input_list, left, mid, temp)
		merge_sort(input_list, mid + 1, right, temp)

		merge(input_list, left, mid, right, temp)

	if len(input_list) == 0:
		return []
	sorted_list = input_list
	temp = [0] * len(sorted_list)
	merge_sort(sorted_list, 0, len(sorted_list) - 1, temp)
	return sorted_list


if __name__ == '__main__':
	input_list = [6, 4, 8, 9, 2, 3, 1]
	print('排序前:', input_list)
	sorted_list = MergeSort(input_list)
	print('排序后:', sorted_list)

7.4 算法分析

7.4.1 时间复杂度

　　 归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。

7.4.2 空间复杂度

　　 由上述的算法说明可知，算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。

7.4.3 稳定性

　　 在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。

7.4.4 归并排序和堆排序、快速排序的比较
  • 若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
  • 若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
  • 若从平均情况下的排序速度考虑，应该选择快速排序。

8 基数排序

基数排序（桶排序）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

8.1 算法思想

　　 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

    基数排序的算法步骤如下 ：
  • 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零；
  • 从最低位开始，依次进行一次排序；
  • 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

　　 基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

　　 不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

　　 我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来表示的，所以我们不妨把 0~9 视为 10 个桶。

　　 我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。

alt

　　 分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。

　　 按照个位数排序得到： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

　　 接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。

8.2 效果示例图

　　 动态效果示意图如下:

alt

8.3 算法实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
def RadixSort(input_list):
    '''
    函数说明:基数排序（升序）
    Parameters:	input_list - 待排序列表
    Returns:	sorted_list - 升序排序好的列表
    '''

    def MaxBit(input_list):
        '''
        函数说明:求出数组中最大数的位数的函数
        Parameters:	input_list - 待排序列表
        Returns:	bits-num - 位数
        '''
        max_data = max(input_list)
        bits_num = 0
        while max_data:
            bits_num += 1
            max_data //= 10
        return bits_num

    def digit(num, d):
        '''
        函数说明:取数xxx上的第d位数字
        Parameters:
            num - 待操作的数
            d - 第d位的数
        Returns: 取数结果
        '''
        p = 1
        while d > 1:
            d -= 1
            p *= 10
        return num // p % 10

    if len(input_list) == 0:
        return []
    sorted_list = input_list
    length = len(sorted_list)
    bucket = [0] * length

    # 数字的位数共三位 d = 1, 2, 3
    for d in range(1, MaxBit(sorted_list) + 1):
        count = [0] * 10

        # 计算当前d位数上对应为0-9的个数
        for i in range(0, length):
            count[digit(sorted_list[i], d)] += 1
        print("")

        # 对count数组向前统计各个位上的数字
        for i in range(1, 10):
            count[i] += count[i - 1]
        print("")

        # i 9,8,7,...,1,0
        for i in range(0, length)[::-1]:
            # 依次取数sorted_list[i]上的第d位数字
            # i: 9,8,..,1,0  d:1
            k = digit(sorted_list[i], d)
            bucket[count[k] - 1] = sorted_list[i]
            count[k] -= 1

        for i in range(0, length):
            sorted_list[i] = bucket[i]

    return sorted_list


if __name__ == '__main__':
    input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
    print('排序前:', input_list)
    sorted_list = RadixSort(input_list)
    print('排序后:', sorted_list)

8.4 算法分析

8.4.1 时间复杂度

　　 这个时间复杂度比较好计算：count * length；其中 count 为数组元素最高位数，length为元素个数；所以时间复杂度：O(n * d)

8.4.2 空间复杂度

　　 空间复杂度是使用了两个临时的数组：10 + length；所以空间复杂度：O（n）。

8.4.3 稳定性

　　 在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。

参考: 程序员内功：八大排序算法