程序员必须掌握的十大排序算法（下）-Tutorial Python-php.cn

程序员必须掌握的十大排序算法（下）

Python当打之年

Lepaskan： 2023-08-15 14:53:11

ke hadapan

1415 orang telah melayarinya

本期导读

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

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

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

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

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

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

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

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

10 桶排序——分布类排序

希尔排序

希尔排序（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]

Salin selepas log masuk

归并排序

归并排序（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]

Salin selepas log masuk

计数排序

计数排序（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]

Salin selepas log masuk

基数排序

基数排序（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]

Salin selepas log masuk

桶排序

桶排序 (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]

Salin selepas log masuk

Atas ialah kandungan terperinci 程序员必须掌握的十大排序算法（下）. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!