程序员必须掌握的十大排序算法(下)

发布: 2023-08-15 14:53:11
转载
1412 人浏览过


本期导读

排序算法可以说是每个程序员都必须得掌握的了, 弄明白它们的原理和实现很有必要,以下为大家介绍十大常用排序算法的python实现方式,方便大家学习。


01 冒泡排序——交换类排序
02 快速排序——交换类排序

03 选择排序——选择类排序
04 堆排序——选择类排序

05 插入排序——插入类排序

06 希尔排序——插入类排序

07 归并排序——归并类排序

08 计数排序——分布类排序

09 基数排序——分布类排序

10 桶排序——分布类排序



06
希尔排序
希尔排序(Shell Sort): 是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。

算法原理:
  • 取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列,所有距离为gap的倍数的记录放在同一个组中

  • 对各组内的元素进行直接插入排序, 这一趟排序完成之后,每一个组的元素都是有序的

  • 减小gap的值,并重复执行上述的分组和排序

  • 重复上述操作,当gap=1时,排序结束

代码如下:
'''希尔排序''' def Shell_Sort(arr): # 设定步长,注意类型 step = int(len(arr) / 2) while step > 0: for i in range(step, len(arr)): # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置 while i >= step and arr[i - step] > arr[i]: arr[i], arr[i - step] = arr[i - step], arr[i] i -= step step = int(step / 2) return arr arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22] result = Shell_Sort(arr) print('result list: ', result) # result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]
登录后复制


07
归并排序
归并排序(Merge Sort) 是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,将已有序的子序列合并,得到完全有序的序列。

算法原理:
  • 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  • 设定两个索引,最初索引位置分别为两个已经排序序列的起始位置

  • 比较两个索引所指向的元素,选择相对小的元素放入到合并空间,并移动索引到下一位置

  • 重复上一步骤直到某一索引超出序列尾

  • 将另一序列剩下的所有元素直接复制到合并序列尾


代码如下:
'''归并排序'''def Merge(left, right): arr = [] i = j = 0 while j < len(left) and i < len(right): if left[j] < right[i]: arr.append(left[j]) j += 1 else: arr.append(right[i]) i += 1 if j == len(left): # right遍历完 for k in right[i:]: arr.append(k) else: # left遍历完 for k in left[j:]: arr.append(k) return arr def Merge_Sort(arr): # 递归结束条件 if len(arr) <= 1: return arr # 二分 middle = len(arr) // 2 left = Merge_Sort(arr[:middle]) right = Merge_Sort(arr[middle:]) # 合并 return Merge(left, right) arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18] result = Merge_Sort(arr) print('result list: ', result) # result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]
登录后复制

08
计数排序
计数排序(Count sort):是一个非基于比较的排序算法,它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。

算法原理:
  • 找出待排序的数组中最大和最小的元素

  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项

  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)

  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1


代码如下:
'''计数排序''' def Count_Sort(arr): max_num = max(arr) min_num = min(arr) count_num = max_num - min_num + 1 count_arr = [0 for i in range(count_num)] res = [0 for i in range(len(arr))] # 统计数字出现的次数 for i in arr: count_arr[i - min_num] += 1 # 统计前面有几个比自己小的数 for j in range(1, count_num): count_arr[j] = count_arr[j] + count_arr[j - 1] # 遍历重组 for k in range(len(arr)): res[count_arr[arr[k] - min_num] - 1] = arr[k] count_arr[arr[k] - min_num] -= 1 return res arr = [5, 10, 76, 55, 13, 79, 5, 49, 51, 65, 30, 5] result = Count_Sort(arr) print('result list: ', result) # result list: [5, 5, 5, 10, 13, 30, 49, 51, 55, 65, 76, 79]
登录后复制

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

算法原 理(以LSD为例):
  • 根据个位数的数值,遍历列表将它们分配至编号0到9的桶子中

  • 将这些桶子中的数值重新串接起来

  • 根据十位数的数值,遍历列表将它们分配至编号0到9的桶子中

  • 再将这些桶子中的数值重新串接起来


代码如下:
'''基数排序''' def Radix_Sort(arr): max_num = max(arr) place = 0 while 10 ** place <= max_num: # 创建桶 buckets = [[] for _ in range(10)] # 分桶 for item in arr: pos = item // 10 ** place % 10 buckets[pos].append(item) j = 0 for k in range(10): for num in buckets[k]: arr[j] = num j += 1 place += 1 return arr arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53] result = Radix_Sort(arr) print('result list: ', result) # result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]
登录后复制

10
桶排序
桶排序 (Bucket sort)或所谓的箱排序: 划分多个范围相同的桶区间,每个桶自排序,最后合并, 桶排序可以看作是计数排序的扩展。

算法原理:
  • 计算有限桶的数量

  • 逐个桶内部排序

  • 遍历每个桶,进行合并


代码如下:
'''桶排序''' def Bucket_Sort(arr): num = max(arr) # 列表置零 pre_lst = [0] * num result = [] for data in arr: pre_lst[data - 1] += 1 i = 0 while i < len(pre_lst): # 遍历生成的列表,从小到大 j = 0 while j < pre_lst[i]: result.append(i + 1) j += 1 i += 1 return result arr = [26, 53, 83, 86, 5, 46, 5, 72, 21, 4, 75] result = Bucket_Sort(arr) print('result list: ', result) # result list: [4, 5, 5, 21, 26, 46, 53, 72, 75, 83, 86]
登录后复制

以上是程序员必须掌握的十大排序算法(下)的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:Python当打之年
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!