发布时间 : 星期六 文章常用排序算法比较与分析 - 图文更新完毕开始阅读3d5bb4afdf88d0d233d4b14e852458fb770b38bd
常用排序算法比较与分析
一、常用排序算法简述
下面主要从排序算法的基本概念、原理出发,分别从算法的时间复杂度、空间复杂度、算法的稳定性和速度等方面进行分析比较。依据待排序的问题大小(记录数量 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. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
#-------------------------直接插入排序-------------------------------- def insert_sort(data_list):
#遍历数组中的所有元素，其中0号索引元素默认已排序，因此从1开始 for x in range(1, len(data_list)):
#将该元素与已排序好的前序数组依次比较，如果该元素小，则交换 #range(x-1,-1,-1):从x-1倒序循环到0 for i in range(x-1, -1, -1): #判断：如果符合条件则交换 if data_list[i] > data_list[i+1]: temp = data_list[i+1] data_list[i+1] = data_list[i] data_list[i] = temp
2.1.2 希尔排序
核心思想：是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序时间复杂度会比O(n2)好一些，然而，多次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。
Python源代码：
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.
#-------------------------希尔排序------------------------------- def insert_shell(data_list):
#初始化step值，此处利用序列长度的一半为其赋值 group = int(len(data_list)/2)
#第一层循环：依次改变group值对列表进行分组 while group > 0:
#下面：利用直接插入排序的思想对分组数据进行排序 #range(group,len(data_list)):从group开始 for i in range(group, len(data_list)):
#range(x-group,-1,-group):从x-group开始与选定元素开始倒序比较，每个比较元素之间间隔group for j in range(i-group, -1, -group):
#如果该组当中两个元素满足交换条件，则进行交换 if data_list[j] > data_list[j+group]: temp = data_list[j+group] data_list[j+group] = data_list[j] data_list[j] = temp #while循环条件折半 group = int(group / 2)
2.2 选择排序
核心思想：每一趟扫描时，从待排序的数据元素中选出关键码最小或最大的一个元素，顺序放在已经排好顺序序列的最后，直到全部待排序的数据元素排完为止。
2.2.1 直接选择排序
核心思想：给每个位置选择关键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后在剩下的元素中再选择最小的与第二个位置的元素交换，直到倒数第二个元素和最后一个元素比较为止。
根据其基本思想，每当扫描一趟时，如果当前元素比一个元素小，而且这个小元素又出现在一个和当前元素相等的元素后面，则它们的位置发生了交换，所以直接选择排序时不稳定的，其时间复杂度为平方阶O(n2)，空间复杂度为O(l)。
Python源代码：
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
#-------------------------直接选择排序------------------------------- def select_sort(data_list): #依次遍历序列中的每一个元素 for i in range(0, len(data_list)):
#将当前位置的元素定义此轮循环当中的最小值 minimum = data_list[i]
#将该元素与剩下的元素依次比较寻找最小元素 for j in range(i+1, len(data_list)): if data_list[j] < minimum: temp = data_list[j]; data_list[j] = minimum; minimum = temp
#将比较后得到的真正的最小值赋值给当前位置 data_list[i] = minimum
2.2.2 堆排序
堆排序时对直接选择排序的一种有效改进。
核心思想：将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶的数据元素和序列的最后一个元素交换;接着重建堆、交换数据，依次下去，从而实现对所有的数据元素的排序。完成堆排序需要执行两个动作：建堆和堆的调整，如此反复进行。
堆排序有可能会使得两个相同值的元素位置发生互换，所以是不稳定的，其平均时间复杂度为0(nlog2n)，空间复杂度为O(l)。
Python源代码：
1. 2. 3. 4. 5. 6. 7.
#-------------------------堆排序-------------------------------- #**********获取左右叶子节点********** def LEFT(i): return 2*i + 1
def RIGHT(i): return 2*i + 2
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.
#********** 调整大顶堆 **********
#data_list:待调整序列 length: 序列长度 i:需要调整的结点 def adjust_max_heap(data_list,length,i): #定义一个int值保存当前序列最大值的下标 largest = i
#执行循环操作：两个任务：1 寻找最大值的下标；2.最大值与父节点交换 while 1:
#获得序列左右叶子节点的下标 left, right = LEFT(i), RIGHT(i)
#当左叶子节点的下标小于序列长度 并且 左叶子节点的值大于父节点时，将左叶子节点的下标赋值给largest if (left < length) and (data_list[left] > data_list[i]): largest = left #print('左叶子节点') else: largest = i
#当右叶子节点的下标小于序列长度 并且 右叶子节点的值大于父节点时，将右叶子节点的下标值赋值给largest if (right < length) and (data_list[right] > data_list[largest]): largest = right #print('右叶子节点')
#如果largest不等于i 说明当前的父节点不是最大值，需要交换值 if (largest != i): temp = data_list[i]
data_list[i] = data_list[largest] data_list[largest] = temp i = largest #print(largest) continue else: break
#********** 建立大顶堆 ********** def build_max_heap(data_list): length = len(data_list)
for x in range(int((length-1)/2),-1,-1): adjust_max_heap(data_list,length,x)
#********** 堆排序 ********** def heap_sort(data_list):
#先建立大顶堆，保证最大值位于根节点；并且父节点的值大于叶子结点 build_max_heap(data_list)
#i：当前堆中序列的长度.初始化为序列的长度 i = len(data_list)
#执行循环：1. 每次取出堆顶元素置于序列的最后(len-1,len-2,len-3...)