常用排序算法比较与分析

一、常用排序算法简述

下面主要从排序算法的基本概念、原理出发,分别从算法的时间复杂度、空间复杂度、算法的稳定性和速度等方面进行分析比较。依据待排序的问题大小(记录数量 n)的不同，排序过程中需要的存储器空间也不同，由此将排序算法分为两大类：【内排序】、【外排序】。

内排序：指排序时数据元素全部存放在计算机的随机存储器RAM中。

外排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中还需要对外存进行访问的排序过程。

先了解一下常见排序算法的分类关系(见图1-1)

图1-1 常见排序算法

二、内排序相关算法

2.1 插入排序

核心思想：将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数据元素依然有序，直到待排序数据元素全部插入完为止。

2.1.1 直接插入排序

核心思想：将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2 、i-3、 … 数据元素的值进行顺序比较，通过这种线性搜索的方法找到第i个数据元素的插入位置 ，并且原来位置 的数据元素顺序后移，直到全部排好顺序。

直接插入排序中，关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的，时间复杂度的最坏值为平方阶O(n2)，空间复杂度为常数阶O(l)。

Python源代码：

1. #-------------------------直接插入排序-------------------------------- 
2. def insert_sort(data_list): 
3.  #遍历数组中的所有元素，其中0号索引元素默认已排序，因此从1开始 
4.  for x in range(1, len(data_list)): 
5.  #将该元素与已排序好的前序数组依次比较，如果该元素小，则交换 
6.  #range(x-1,-1,-1):从x-1倒序循环到0 
7.  for i in range(x-1, -1, -1): 
8.  #判断：如果符合条件则交换 
9.  if data_list[i] > data_list[i+1]: 
10.  temp = data_list[i+1] 
11.  data_list[i+1] = data_list[i] 
12.  data_list[i] = temp 

2.1.2 希尔排序

核心思想：是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序时间复杂度会比O(n2)好一些，然而，多次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。

Python源代码：

1. #-------------------------希尔排序------------------------------- 
2. def insert_shell(data_list): 
3.  #初始化step值，此处利用序列长度的一半为其赋值 
4.  group = int(len(data_list)/2) 
5.  #第一层循环：依次改变group值对列表进行分组 
6.  while group > 0: 
7.  #下面：利用直接插入排序的思想对分组数据进行排序 
8.  #range(group,len(data_list)):从group开始 
9.  for i in range(group, len(data_list)): 
10.  #range(x-group,-1,-group):从x-group开始与选定元素开始倒序比较，每个比较元素之间间隔group 
11.  for j in range(i-group, -1, -group): 
12.  #如果该组当中两个元素满足交换条件，则进行交换 
13.  if data_list[j] > data_list[j+group]: 
14.  temp = data_list[j+group] 
15.  data_list[j+group] = data_list[j] 
16.  data_list[j] = temp 
17.  #while循环条件折半 
18.  group = int(group / 2) 

2.2 选择排序

核心思想：每一趟扫描时，从待排序的数据元素中选出关键码最小或最大的一个元素，顺序放在已经排好顺序序列的最后，直到全部待排序的数据元素排完为止。

2.2.1 直接选择排序

核心思想：给每个位置选择关键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后在剩下的元素中再选择最小的与第二个位置的元素交换，直到倒数第二个元素和最后一个元素比较为止。

根据其基本思想，每当扫描一趟时，如果当前元素比一个元素小，而且这个小元素又出现在一个和当前元素相等的元素后面，则它们的位置发生了交换，所以直接选择排序时不稳定的，其时间复杂度为平方阶O(n2)，空间复杂度为O(l)。

Python源代码：

1. #-------------------------直接选择排序------------------------------- 
2. def select_sort(data_list): 
3. #依次遍历序列中的每一个元素 
4.  for i in range(0, len(data_list)): 
5. #将当前位置的元素定义此轮循环当中的最小值 
6.  minimum = data_list[i] 
7. #将该元素与剩下的元素依次比较寻找最小元素 
8.  for j in range(i+1, len(data_list)): 
9.  if data_list[j] < minimum: 
10.  temp = data_list[j]; 
11.  data_list[j] = minimum; 
12.  minimum = temp 
13. #将比较后得到的真正的最小值赋值给当前位置 
14.  data_list[i] = minimum 

2.2.2 堆排序

堆排序时对直接选择排序的一种有效改进。

核心思想：将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶的数据元素和序列的最后一个元素交换;接着重建堆、交换数据，依次下去，从而实现对所有的数据元素的排序。完成堆排序需要执行两个动作：建堆和堆的调整，如此反复进行。

堆排序有可能会使得两个相同值的元素位置发生互换，所以是不稳定的，其平均时间复杂度为0(nlog2n)，空间复杂度为O(l)。

Python源代码：

1. #-------------------------堆排序-------------------------------- 
2. #**********获取左右叶子节点********** 
3. def LEFT(i): 
4.  return 2*i + 1 
5.   
6. def RIGHT(i): 
7.  return 2*i + 2 
8.   
9. #********** 调整大顶堆 ********** 
10. #data_list:待调整序列 length: 序列长度 i:需要调整的结点 
11. def adjust_max_heap(data_list,length,i): 
12. #定义一个int值保存当前序列最大值的下标 
13.  largest = i 
14. #执行循环操作：两个任务：1 寻找最大值的下标；2.最大值与父节点交换 
15.  while 1: 
16. #获得序列左右叶子节点的下标 
17.  left, right = LEFT(i), RIGHT(i) 
18. #当左叶子节点的下标小于序列长度 并且 左叶子节点的值大于父节点时，将左叶子节点的下标赋值给largest 
19.  if (left < length) and (data_list[left] > data_list[i]): 
20.  largest = left 
21.  #print('左叶子节点') 
22.  else: 
23.  largest = i 
24. #当右叶子节点的下标小于序列长度 并且 右叶子节点的值大于父节点时，将右叶子节点的下标值赋值给largest 
25.  if (right < length) and (data_list[right] > data_list[largest]): 
26.  largest = right 
27.  #print('右叶子节点') 
28. #如果largest不等于i 说明当前的父节点不是最大值，需要交换值 
29.  if (largest != i): 
30.  temp = data_list[i] 
31.  data_list[i] = data_list[largest] 
32.  data_list[largest] = temp 
33.  i = largest 
34.  #print(largest) 
35.  continue 
36.  else: 
37.  break 
38.   
39. #********** 建立大顶堆 ********** 
40. def build_max_heap(data_list): 
41.  length = len(data_list) 
42.  for x in range(int((length-1)/2),-1,-1): 
43.  adjust_max_heap(data_list,length,x) 
44.   
45. #********** 堆排序 ********** 
46. def heap_sort(data_list): 
47. #先建立大顶堆，保证最大值位于根节点；并且父节点的值大于叶子结点 
48.  build_max_heap(data_list) 
49. #i：当前堆中序列的长度.初始化为序列的长度 
50.  i = len(data_list) 
51. #执行循环：1. 每次取出堆顶元素置于序列的最后(len-1,len-2,len-3...) 
52. # 2. 调整堆，使其继续满足大顶堆的性质，注意实时修改堆中序列的长度 
53.  while i > 0: 
54.  temp = data_list[i-1] 
55.  data_list[i-1] = data_list[0] 
56.  data_list[0] = temp 
57. #堆中序列长度减1 
58.  i = i-1 
59. #调整大顶堆 
60.  adjust_max_heap(data_list, i, 0) 

2.3交换排序

核心思想：顾名思义，就是一组待排序的数据元素中，按照位置的先后顺序相互比较各自的关键码，如果是逆序，则交换这两个数据元素，直到该序列数据元素有序为止。

2.3.1 冒泡排序

核心思想：对于待排序的一组数据元素，把每个数据元素看作有重量的气泡，按照轻气泡不能在重气泡之下的原则，将未排好顺序的全部元素自上而下的对相邻两个元素依次进行比较和调整，让较重的元素往下沉，较轻的往上冒。

根据基本思想，只有在两个元素的顺序与排序要求相反时才将调换它们的位置，否则保持不变，所以冒泡排序时稳定的。时间复杂度为平方阶O(n2)，空间复杂度为O(l)。

Python源代码：

1. #-------------------------冒泡排序-------------------------------- 
2. def bubble_sort(data_list): 
3.  length = len(data_list) 
4. #序列长度为length，需要执行length-1轮交换 
5.  for x in range(1,length): 
6. #对于每一轮交换，都将序列当中的左右元素进行比较 
7. #每轮交换当中，由于序列最后的元素一定是最大的，因此每轮循环到序列未排序的位置即可 
8.  for i in range(0,length-x): 
9.  if data_list[i] > data_list[i+1]: 
10.  temp = data_list[i] 
11.  data_list[i] = data_list[i+1] 
12.  data_list[i+1] = temp 

2.3.2 快速排序

快速排序是对冒泡排序本质上的改进。

核心思想：是一个就地排序，分而治之，大规模递归的算法。即：通过一趟扫描后确保基准点的这个数据元素的左边元素都比它小、右边元素都比它大，接着又以递归方法处理左右两边的元素，直到基准点的左右只有一个元素为止。

快速排序时一个不稳定的算法，其最坏值的时间复杂度为平方阶O(n2)，空间复杂度为O(log2n)。

Python源代码：

1. #-------------------------快速排序-------------------------------- 
2. #data_list：待排序的序列；start排序的开始index,end序列末尾的index 
3. #对于长度为length的序列：start = 0;end = length-1 
4. def quick_sort(data_list,start,end): 
5.  if start < end: 
6.  i , j , pivot = start, end, data_list[start] 
7.  while i < j: 
8. #从右开始向左寻找第一个小于pivot的值 
9.  while (i < j) and (data_list[j] >= pivot): 
10.  j = j-1 
11. #将小于pivot的值移到左边 
12.  if (i < j): 
13.  data_list[i] = data_list[j] 
14.  i = i+1 
15. #从左开始向右寻找第一个大于pivot的值 
16.  while (i < j) and (data_list[i] < pivot): 
17.  i = i+1 
18. #将大于pivot的值移到右边 
19.  if (i < j): 
20.  data_list[j] = data_list[i] 
21.  j = j-1 
22. #循环结束后，说明 i=j，此时左边的值全都小于pivot,右边的值全都大于pivot 
23. #pivot的位置移动正确，那么此时只需对左右两侧的序列调用此函数进一步排序即可 
24. #递归调用函数：依次对左侧序列：从0 ~ i-1//右侧序列：从i+1 ~ end 
25.  data_list[i] = pivot 
26. #左侧序列继续排序 
27.  quick_sort(data_list,start,i-1) 
28. #右侧序列继续排序 
29.  quick_sort(data_list,i+1,end) 

2.4归并排序

核心思想：把数据序列递归地分成短序列，即把1分成2、2分成4、依次分解，当分解到只有1个一组的时候排序这些分组，然后依次合并回原来的序列，不断合并直到原序列全部排好顺序。

合并过程中可以确保两个相等的当前元素中，把处在前面的元素保存在结果序列的前面，因此归并排序是稳定的，其时间复杂度为O(nlog2n)，空间复杂度为O(n)。

Python源代码：

1. #-------------------------归并排序-------------------------------- 
2. #这是合并的函数 
3. # 将序列data_list[first...mid]与序列data_list[mid+1...last]进行合并 
4. def mergearray(data_list,first,mid,last,temp): 
5. #对i,j,k分别进行赋值 
6.  i,j,k = first,mid+1,0 
7. #当左右两边都有数时进行比较，取较小的数 
8.  while (i <= mid) and (j <= last): 
9.  if data_list[i] <= data_list[j]: 
10.  temp[k] = data_list[i] 
11.  i = i+1 
12.  k = k+1 
13.  else: 
14.  temp[k] = data_list[j] 
15.  j = j+1 
16.  k = k+1 
17. #如果左边序列还有数 
18.  while (i <= mid): 
19.  temp[k] = data_list[i] 
20.  i = i+1 
21.  k = k+1 
22. #如果右边序列还有数 
23.  while (j <= last): 
24.  temp[k] = data_list[j] 
25.  j = j+1 
26.  k = k+1 
27. #将temp当中该段有序元素赋值给data_list待排序列使之部分有序 
28.  for x in range(0,k): 
29.  data_list[first+x] = temp[x] 
30. # 这是分组的函数 
31. def merge_sort(data_list,first,last,temp): 
32.  if first < last: 
33.  mid = (int)((first + last) / 2) 
34. #使左边序列有序 
35.  merge_sort(data_list,first,mid,temp) 
36. #使右边序列有序 
37.  merge_sort(data_list,mid+1,last,temp) 
38. #将两个有序序列合并 
39.  mergearray(data_list,first,mid,last,temp) 
40. # 归并排序的函数 
41. def merge_sort_array(data_list): 
42. #声明一个长度为len(data_list)的空列表 
43.  temp = len(data_list)*[None] 
44. #调用归并排序 
45.  merge_sort(data_list,0,len(data_list)-1,temp) 

2.5 基数排序

核心思想：首先是低位排序，然后收集;其次是高位排序，然后再收集;依次类推，直到最高位。

Python源代码：

1. #-------------------------基数排序-------------------------------- 
2. #确定排序的次数 
3. #排序的顺序跟序列中最大数的位数相关 
4. def radix_sort_nums(data_list): 
5.  maxNum = data_list[0] 
6. #寻找序列中的最大数 
7.  for x in data_list: 
8.  if maxNum < x: 
9.  maxNum = x 
10. #确定序列中的最大元素的位数 
11.  times = 0 
12.  while (maxNum > 0): 
13.  maxNum = (int)(maxNum/10) 
14.  times = times+1 
15.  return times 
16. #找到num从低到高第pos位的数据 
17. def get_num_pos(num,pos): 
18.  return ((int)(num/(10**(pos-1))))%10 
19. #基数排序 
20. def radix_sort(data_list): 
21.  count = 10*[None] #存放各个桶的数据统计个数 
22.  bucket = len(data_list)*[None] #暂时存放排序结果 
23. #从低位到高位依次执行循环 
24.  for pos in range(1,radix_sort_nums(data_list)+1): 
25.  #置空各个桶的数据统计 
26.  for x in range(0,10): 
27.  count[x] = 0 
28.  #统计当前该位(个位，十位，百位....)的元素数目 
29.  for x in range(0,len(data_list)): 
30.  #统计各个桶将要装进去的元素个数 
31.  j = get_num_pos(int(data_list[x]),pos) 
32.  count[j] = count[j]+1 
33.  #count[i]表示第i个桶的右边界索引 
34.  for x in range(1,10): 
35.  count[x] = count[x] + count[x-1] 
36.  #将数据依次装入桶中 
37.  for x in range(len(data_list)-1,-1,-1): 
38.  #求出元素第K位的数字 
39.  j = get_num_pos(data_list[x],pos) 
40.  #放入对应的桶中，count[j]-1是第j个桶的右边界索引 
41.  bucket[count[j]-1] = data_list[x] 
42.  #对应桶的装入数据索引-1 
43.  count[j] = count[j]-1 
44.  # 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表 
45.  for x in range(0,len(data_list)): 
46.  data_list[x] = bucket[x] 

三、排序算法实测

图3-1 常用排序算法测试统计

四、排序算法对比与分析

表4-1各个排序算法比较

[直接插入排序]是对冒泡排序的改进，比冒泡排序快，但是只适用于数据量较小(1000 ) 的排序

[希尔排序]比较简单，适用于小数据量(5000以下)的排序，比直接插入排序快、冒泡排序快，因此，希尔排序适用于小数据量的、排序速度要求不高的排序。

[直接选择排序]和冒泡排序算法一样，适用于n值较小的场合，而且是排序算法发展的初级阶段，在实际应用中采用的几率较小。

[堆排序]比较适用于数据量达到百万及其以上的排序，在这种情况下，使用递归设计的快速排序和归并排序可能会发生堆栈溢出的现象。

[冒泡排序]是最慢的排序算法，是排序算法发展的初级阶段，实际应用中采用该算法的几率比较小。

[快速排序]是递归的、速度最快的排序算法，但是在内存有限的情况下不是一个好的选择;而且，对于基本有序的数据序列排序，快速排序反而变得比较慢。

[归并排序]比堆排序要快，但是需要的存储空间增加一倍。

[基数排序]适用于规模n值很大的场合，但是只适用于整数的排序，如果对浮点数进行基数排序，则必须明确浮点数的存储格式，然后通过某种方式将其映射到整数上，最后再映射回去，过程复杂。