本期导读
排序算法可以说是每个程序员都必须得掌握的了, 弄明白它们的原理和实现很有必要，以下为大家介绍十大常用排序算法的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]
往期推荐
Python送你王者荣耀官网全套皮肤！！！
12306火车票查询--Python可以这么玩！！!
《你好，李焕英》为什么能超越《唐探3》！！！
END
以上就是本期为大家整理的全部内容了，赶快练习起来吧，喜欢的朋友可以
点赞、点在看
也可以分享到朋友圈让更多人知道哦
