用 python 实现各种排序算法_程序人生

用 python 实现各种排序算法

admin

2023-07-31 00:47:33

0次

总结了一下常见集中排序的算法

归并排序

归并排序也称合并排序，是分治法的典型应用。分治思想是将每个问题分解成个个小问题，将每个小问题解决，然后合并。

具体的归并排序就是，将一组无序数按n/2递归分解成只有一个元素的子项，一个元素就是已经排好序的了。然后将这些有序的子元素进行合并。

合并的过程就是对两个已经排好序的子序列，先选取两个子序列中最小的元素进行比较，选取两个元素中最小的那个子序列并将其从子序列中

去掉添加到最终的结果集中，直到两个子序列归并完成。

代码如下：

12345678910111213141516171819202122232425262728293031323334

#!/usr/bin/python import sys def merge(nums, first, middle, last): \’\’\’\’\’ merge \’\’\’ # 切片边界,左闭右开并且是了0为开始 lnums = nums[first:middle+1] rnums = nums[middle+1:last+1] lnums.append(sys.maxint) rnums.append(sys.maxint) l = 0 r = 0 for i in range(first, last+1): if lnums[l] < rnums[r]: nums[i] = lnums[l] l+=1 else: nums[i] = rnums[r] r+=1 def merge_sort(nums, first, last): \’\’\’\’\’ merge sort merge_sort函数中传递的是下标，不是元素个数 \’\’\’ if first < last: middle = (first + last)/2 merge_sort(nums, first, middle) merge_sort(nums, middle+1, last) merge(nums, first, middle,last) if __name__ == \’__main__\’: nums = [10,8,4,–1,2,6,7,3] print \’nums is:\’, nums merge_sort(nums, 0, 7) print \’merge sort:\’, nums

稳定，时间复杂度 O(nlog n)

插入排序

代码如下：

123456789101112131415161718192021

#!/usr/bin/python import sys def insert_sort(a): \’\’\’\’\’ 插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序。刚开始一个元素显然有序，然后插入一个元素到适当位置，然后再插入第三个元素，依次类推 \’\’\’ a_len = len(a) if a_len = 0 and a[j] > key: a[j+1] = a[j] j-=1 a[j+1] = key return a if __name__ == \’__main__\’: nums = [10,8,4,–1,2,6,7,3] print \’nums is:\’, nums insert_sort(nums) print \’insert sort:\’, nums

稳定，时间复杂度 O(n^2)

交换两个元素的值python中你可以这么写：a, b = b, a，其实这是因为赋值符号的左右两边都是元组

（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的，而不是括号）。

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到

排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所

有元素均排序完毕。

上一篇：Python模板库Mako的用法

下一篇：依赖安装：setup.py和requirements.txt的对比

用 python 实现各种排序算法

归并排序

插入排序

选择排序

相关内容

热门资讯