python排序算法详解,python排序函数代码

　　Hill、Merging和quick sort可以归为一类，它们的共同点都是基于分而治之的思想。把大问题拆分成小问题，解决所有的小问题，然后合并每个小问题的结果，最后得到原问题的答案。本文将介绍这三种算法的实现代码，有需要的可以参考。

　　00-1010 1.前言2。希尔排序2.1前后拆分2.2增量拆分3。归并排序3.1分解子问题3.2求解子问题3.3归并排序4。基数排序5。摘要

1. 前言

　　在解释Hill之前，让我们回顾一下插入排序。理论上，插入排序的平均时间复杂度与冒泡排序相同，但如果序列在第一部分排序，则每轮只需比较一次。对于n个数的原始序列，时间复杂度可以达到O(n)。

　　为什么插入的时间复杂度会有这么有趣的变化？

　　插入排序算法的排序思想是尽量减少数字之间的交换次数。一般来说，交换处理的时间是移动的3倍左右。这就是为什么插入排序的性能可能比冒泡排序好。Hill排序算法的本质是插入排序，或者说是插入排序的改进。

　　其算法理念：让原始数列不断趋近于排序，从而降低插入排序的时间复杂度。

　　希尔排序的实现流程：

　　从逻辑上将原始序列切割成许多子序列。使用插入排序算法对每个子序列进行排序。当所有子序列都完成时，原始序列通过最后插入算法排序。希尔排序算法的思想：当数列局部有序时，全局必然是趋向于有序”.

　　希尔排序的关键在于如何切割分子序列。有两种方法可以切割它：

　　每当用分而治之的概念解决一个问题时，拆分子问题是关键和核心。

2. 希尔排序

　　如果有一个原序列=[3，9，8，1，6，5，7]，就分成两个子序列。

　　前后分是一个简单粗暴的分割方案，没有太多的技术含量。这种一轨分割的方法可能对原问题的最终性能优化没有太大影响。

　　如上图所示，对子数列进行排序后，如果将原数列中的所有数字按从小到大的顺序排列，后面部分的数字几乎都会移动到前面部分的数字中间，移动量非常大。

　　后面的

　　e>4个数字中，1需要移动 3 次，5、6、7需要移动2次，肉眼可见的次数是9次。

　　这种分法很难实现数字局部有序的正态分布，因为数字的位置变化不大。

　　如下图是原始数列=[3，9，8，1，6，5，7]的原始位置示意图：

　　使用前后切分后的数字位置变化如下图所示，和上图相比较，数字的位置变化非常有限，而且是限定在一个很窄的范围内。也就是说子问题的求解结果对最终问题的结果的影响很微小。

2.2 增量切分

　　增量切分采用间隔切分方案，可能让数字局部有序以正态分布。

　　增量切分，需要先设定一个增量值。如对原始数列=[3，9，8，1，6，5，7]设置切分增量为3时，整个数列会被切分成 3 个逻辑子数列。增量数也决定最后能切分多少个子数列。

　　对切分后的3个子数列排序后可得到下图：

　　在此基础之上，再进行插入排序的的次数要少很多。

　　使用增量切分后再排序，原始数列中的数字的位置变化范围较大。

　　如数字9原始位置是1，经过增量切分再排序后位置可以到4。已经很接近9的最终位置6了。

　　下图是增量切分后数字位置的变化图，可以看出来，几乎所有的数字都产生了位置变化，且位置变化的跨度较大。有整体趋于有序的势头。

　　实现希尔排序算法时，最佳的方案是先初始化一个增量值，切分排序后再减少增量值，如此反复直到增量值等于 1 （也就是对原数列整体做插入排序）。

　　增量值大，数字位置变化的跨度就大，增量值小，数字位置的变化会收紧。

　　编码代码希尔排序：

# 希尔排序
　　def shell_sort(nums):
　　 # 增量
　　 increment = len(nums) // 2
　　 # 新数列
　　 while increment > 0:
　　 # 增量值是多少，则切分的子数列就有多少
　　 for start in range(increment):
　　 insert_sort(nums, start, increment)
　　 # 修改增量值，直到增量值为 1 
　　 increment = increment // 2
　　# 插入排序
　　def insert_sort(nums, start, increment):
　　 for back_idx in range(start + increment, len(nums), increment):
　　 for front_idx in range(back_idx, 0, -increment):
　　 if nums[front_idx] < nums[front_idx - increment]:
　　 nums[front_idx], nums[front_idx - increment] = nums[front_idx - increment], nums[front_idx]
　　 else:
　　 break
　　nums = [3, 9, 8, 1, 6, 5, 7]
　　shell_sort(nums)
　　print(nums)

　　这里会有一个让人疑惑的观点：难道一次插入排序的时间复杂度会高于多次插入排序时间复杂度？

　　通过切分方案，经过子数列的微排序（因子数列数字不多，其移动交换量也不会很大），最后一次插入排序的移动次数可以达到最小，只要增量选择合适，时间复杂度可以控制在O(n)到O（<sup>2</sup>）之间。完全是有可能优于单纯的使用一次插入排序。

3. 归并排序

　　归并排序算法也是基于分治思想。和希尔排序一样，需要对原始数列进行切分，但是切分的方案不一样。

　　相比较希尔排序，归并排序的分解子问题，求解子问题，合并子问题的过程分界线非常清晰。可以说，归并排序更能完美诠释什么是分治思想。

3.1 分解子问题

　　归并排序算法的分解过程采用二分方案。

　　把原始数列一分为二。

　　然后在已经切分后的子数列上又进行二分。

　　如此反复，直到子数列不能再分为止。

　　如下图所示：

　　如下代码，使用递归算法对原数列进行切分，通过输出结果观察切分过程：

# 切分原数列
　　def split_nums(nums):
　　 print(nums)
　　 if len(nums) > 1:
　　 # 切分线，中间位置
　　 sp_line = len(nums) // 2
　　 split_nums(nums[0:sp_line])
　　 split_nums(nums[sp_line:])
　　nums = [3, 9, 8, 1, 6, 5, 7]
　　split_nums(nums)

　　输出结果：和上面演示图的结论一样。

[3, 9, 8, 1, 6, 5, 7]
[3, 9, 8]
[3]
[9, 8]
[9]
[8]
[1, 6, 5, 7]
[1, 6]
[1]
[6]
[5, 7]
[5]
[7]
　　

3.2 求解子问题

　　切分后，对每相邻2个子数列进行合并。当对相邻2个数列进行合并时，不是简单合并，需要保证合并后的数字是排序的。如下图所示：

3.3 合并排序

　　如何实现2个数字合并后数字有序？

　　使用子数列中首数字比较算法进行合并排序。如下图演示了如何合并nums01=[1,3,8,9]、nums02=[5,6,7]2 个子数列。

　　子数列必须是有序的！！

　　数字 1 和数字 5 比较，5 大于 1 ，数字 1 先位于合并数列中。

　　数字 3 与数字 5 比较，数字 3 先进入合并数列中。

　　数字 8 和数字 5 比较，数字 5 进入合并数列中。

　　从头至尾，进行首数字大小比较，最后，可以保证合并后的数列是有序的。

　　编写一个合并排序代码：

　　如果仅仅是合并2个有序数列，本文提供2个方案：

　　不增加额外的存储空间：把最终合并排序好的数字全部存储到其中的一个数列中。

def merge_sort(nums01, nums02):
　　 # 为 2 个数列创建 2 个指针
　　 idx_01 = 0
　　 idx_02 = 0
　　 while idx_01 < len(nums01) and idx_02 < len(nums02):
　　 if nums01[idx_01] > nums02[idx_02]:
　　 # 这里不额外增加存储空间，如果数列 2 中的值大于数字 1 的插入到数列 1 中
　　 nums01.insert(idx_01, nums02[idx_02])
　　 idx_02 += 1
　　 # 数列 1 的指针向右移动 
　　 idx_01 += 1
　　 # 检查 nums02 中的数字是否已经全部合并到 nums01 中
　　 while idx_02 < len(nums02):
　　 nums01.append(nums02[idx_02])
　　 idx_02 += 1
　　nums01 = [1, 2, 8, 9]
　　nums02 = [5, 6, 7, 12, 15]
　　merge_sort(nums01, nums02)
　　# 合并后的数字都存储到了第一个数列中
　　print(nums01)
　　输出结果：
　　[1,2,5,6,7,8,9,12,15]

　　增加一个空数列，用来保存最终合并的数字。

# 使用附加数列
　　nums=[]
　　def merge_sort(nums01, nums02):
　　 # 为 2 个数列创建 2 个指针
　　 idx_01 = 0
　　 idx_02 = 0
　　 k=0
　　 while idx_01 < len(nums01) and idx_02 < len(nums02):
　　 if nums01[idx_01] > nums02[idx_02]:
　　 nums.append(nums02[idx_02])
　　 idx_02 += 1
　　 else:
　　 nums.append(nums01[idx_01])
　　 idx_01 += 1
　　 k+=1
　　 # 检查是否全部合并
　　 while idx_02 < len(nums02):
　　 nums.append(nums02[idx_02])
　　 idx_02 += 1
　　 while idx_01 < len(nums01):
　　 nums.append(nums01[idx_01])
　　 idx_01 += 1
　　nums01 = [1, 2, 8, 9]
　　nums02 = [5, 6, 7, 12, 15]
　　merge_sort(nums01, nums02)
　　print(nums)

　　前面是分步讲解切分和合并逻辑，现在把切分和合并逻辑合二为一，就完成了归并算法的实现：

def merge_sort(nums):
　　 if len(nums) > 1:
　　 # 切分线，中间位置
　　 sp_line = len(nums) // 2
　　 nums01 = nums[:sp_line]
　　 nums02 = nums[sp_line:]
　　 merge_sort(nums01)
　　 merge_sort(nums02)
　　 # 为 2 个数列创建 2 个指针
　　 idx_01 = 0
　　 idx_02 = 0
　　 k = 0
　　 while idx_01 < len(nums01) and idx_02 < len(nums02):
　　 if nums01[idx_01] > nums02[idx_02]:
　　 # 合并后的数字要保存到原数列中
　　 nums[k] = nums02[idx_02]
　　 idx_02 += 1
　　 else:
　　 nums[k] = nums01[idx_01]
　　 idx_01 += 1
　　 k += 1
　　 # 检查是否全部合并
　　 while idx_02 < len(nums02):
　　 nums[k] = nums02[idx_02]
　　 idx_02 += 1
　　 k += 1
　　 while idx_01 < len(nums01):
　　 nums[k] = nums01[idx_01]
　　 idx_01 += 1
　　 k += 1
　　nums = [3, 9, 8, 1, 6, 5, 7]
　　merge_sort(nums)
　　print(nums)

　　个人觉得，归并算法对于理解分治思想有大的帮助。

　　从归并算法上可以完整的体现分治理念的哲学之美。

4. 基数排序

　　基数排序（radix sort）属于分配式排序（distribution sort），又称桶子法（bucket sort）或 bin sort。

　　基数排序没有使用分治理念，放在本文一起讲解，是因为基数排序有一个对数字自身切分逻辑。

　　基数排序的最基本思想：

　　如对原始数列nums = [3, 9, 8, 1, 6, 5, 7]中的数字使用基数排序。

　　先提供一个长度为10的新空数列（本文也称为排序数列）。

　　为什么新空数列的长度要设置为 10？等排序完毕，相信大家就能找到答案。

　　把原数列中的数字转存到新空数列中，转存方案：

　　nums 中的数字 3 存储在新数列索引号为 3 的位置。

　　nums 中的数字 9 存储在新数列索引号为 9 的位置。

　　nums 中的数字 8 存储在新数列索引号为 8 的位置。

　　……

　　从上图可知，原数列中的数字所转存到排序数列中的位置，是数字所代表的索引号所指的位置。显然，经过转存后，新数列就是一个排好序的数列。

　　新空数列的长度定义为多大由原始数列中数字的最大值来决定。

　　编码实现：

# 原数列
　　nums = [3, 9, 8, 1, 6, 5, 7]
　　# 找到数列中的最大值
　　sort_nums=[0]*(max(nums)+1)
　　for i in nums:
　　 sort_nums[i]=i
　　print([i for i in sort_nums if i!=0])
　　输出结果：
　　[1,3,5,6,7,8,9]

　　使用上述方案创建新空数据，如果数字之间的间隔较大时，新数列的空间浪费就非常大。

　　如对nums=[1,98,51,2,32,4,99,13,45]使用上述方案排序，新空数列的长度要达到99，真正需要保存的数字只有7个，如此空间浪费几乎是令人恐怖的。

　　所以，有必要使用改良方案。如果在需要排序的数字中出现了2位以上的数字，则使用如下法则：

　　先根据每一个数字个位上的数字进行存储。个位数是 1 存储在位置为 1 的位置，是 9 就存储在位置是 9 的位置。如下图：

　　可看到有可能在同一个位置保存多个数字。这也是基数排序也称为桶排序的原因。

　　一个位置就是一个桶，可以存放多个具有相同性质的数字。如上图：个位上数字相同的数字就在一个桶中。

把存放在排序数列中的数字按顺序重新拿出来，这时的数列顺序变成nums=[1，51，2，32，13，4，45，8，99]
把重组后数列中的数字按十位上的数字重新存入排序数列。

　　可以看到，经过 2 轮转存后，原数列就已经排好序。

　　这个道理是很好理解的：

　　现实生活中，我们在比较 2 个数字大小时，可以先从个位上的数字相比较，然后再对十位上的数字比较。

　　基数排序，很有生活的味道！！

　　编码实现基数排序：

nums = [1, 98, 51, 2, 32, 4, 99, 13, 45]
　　# 数列中的最大值
　　m = max(nums)
　　# 确定最大位数，用来确定需要转存多少次
　　l = len(str(m))
　　for i in range(l + 1):
　　 # 排序数列，也是桶
　　 sort_nums = [[] for _ in range(10)]
　　 for n in nums:
　　 # 分解数字个位上的数字
　　 g_s = (n // 10 ** i) % 10
　　 # 根据个位上的数字找到转存位置
　　 sub_nums = sort_nums[g_s]
　　 sub_nums.append(n)
　　 # 合并数据
　　 nums = []
　　 for l in sort_nums:
　　 nums.extend(l)
　　print(nums)
　　输出结果：
　　[1, 2, 4, 13, 32, 45, 51, 98, 99]

　　上述转存过程是由低位到高位，也称为LSD，也可以先高位后低位方案转存MSD。

5. 总结

　　分治很有哲学味道，当你遇到困难，应该试着找到问题的薄弱点，然后一点点地突破。

　　当遇到困难时，老师们总会这么劝解我们。

　　分治其实和项目开发中的组件设计思想也具有同工异曲之处。

　　到此这篇关于Python实现希尔排序,归并排序和桶排序的示例代码的文章就介绍到这了,更多相关Python 排序算法内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。