Python实现常见排序算法
2021/12/18 20:52:06
本文主要是介绍Python实现常见排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.冒泡排序与鸡尾酒排序
''' @Author : "HCL" *冒泡排序以及其优化 1.当整体数组有序时结束循环 2.更新有序边界 *鸡尾酒排序 ''' from typing import List # python 自带的sorted()和sort原理归并排序,并且利用了python无法实现的底层实现,比侦察和那个归并排序快10-20倍 # 需要排序的列表 need_sortlist = [3, 2, 15, 4, 5, 6, 7, 8, 1222] def bubble_sort(need_sortlist: List[int]) -> List[int]: """ 冒泡排序朴素版 时间复杂度O(n^2) :param need_sortlist:待排序的数组 :return: 排序完成的数组 """ for i in range(len(need_sortlist) - 1): for j in range(len(need_sortlist) - 1 - i): if need_sortlist[j] > need_sortlist[j + 1]: need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j] return need_sortlist # print(bubble_sort(need_sortlist)) def bubble_sort1(need_sortlist: List[int]) -> List[int]: """ 冒泡排序朴素版优化 1.当待排序数组已经有序,冒泡排序仍未执行完毕时,我们让函数每一轮比较结束后都判断数组是否有序,如果有序,则直接结束函数循环 时间复杂度O(n^2) :param need_sortlist:待排序的数组 :return: 排序完成的数组 """ # 控制外层循环 for i in range(len(need_sortlist) - 1): # 每次大循环我们都认定数组已经有序 isorted = True # 控制内层比较 for j in range(len(need_sortlist) - 1 - i): if need_sortlist[j] > need_sortlist[j + 1]: need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j] # 一旦发生元素交换,说明数组仍无序 isorted = False if isorted: break return need_sortlist def bubble_sort2(need_sortlist: List[int]) -> List[int]: """ 冒泡排序朴素版优化 1.当待排序数组已经有序,冒泡排序仍未执行完毕时,我们让函数每一轮比较结束后都判断数组是否有序,如果有序,则直接结束函数循环 时间复杂度O(n^2) 2.设计有序边界,避免数组实际有序区域大于冒泡排序逻辑有序区域 :param need_sortlist:待排序的数组 :return: 排序完成的数组 """ sorted_border = len(need_sortlist) - 1 last_change_index = 0 # 控制外层循环 for i in range(len(need_sortlist) - 1): # 每次大循环我们都认定数组已经有序 isorted = True # 控制内层比较 for j in range(sorted_border): if need_sortlist[j] > need_sortlist[j + 1]: need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j] # 一旦发生元素交换,说明数组仍无序 isorted = False # 记录并更新最后一次元素交换的位置 last_change_index = j # 将有序边界设定为最后一次元素交换的位置 sorted_border = last_change_index # print(sorted_border) if isorted: break return need_sortlist # print(bubble_sort2(need_sortlist)) def cocktail_sort(need_sortlist: List[int]) -> List[int]: """ 鸡尾酒排序 :param need_sortlist:待排序的数组 :return: 排序完成的数组 """ # 记录大循环次数 times = 0 # 记录向左比较时交换元素的位置 left_lastchange_index = 0 # 记录向右比较时交换元素的位置zz right_lastchange_index = 0 # 左有序边界 leftsorted_border = 0 # 右有序边界 rightsorted_border = len(need_sortlist) - 1 for i in range(len(need_sortlist) - 1): times = i # 默认有序 issorted = True # 奇数次大循环,从左至右 if (i + 1) % 2 != 0: # print(leftsorted_border,rightsorted_border) for j in range(leftsorted_border, rightsorted_border): if need_sortlist[j] > need_sortlist[j + 1]: need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j] # 发生元素交换 issorted = False left_lastchange_index = j if issorted: break # 偶数次大循环,从右至左 else: for j in range(rightsorted_border, leftsorted_border, -1): if need_sortlist[j] < need_sortlist[j - 1]: need_sortlist[j], need_sortlist[j - 1] = need_sortlist[j - 1], need_sortlist[j] # 发生元素交换 issorted = False right_lastchange_index = j if issorted: break leftsorted_border = left_lastchange_index rightsorted_border = right_lastchange_index print("共大循环%s次" % times) return need_sortlist print(cocktail_sort(need_sortlist))
2.计数排序与桶排序
''' @Author : "HCL" 计数排序&桶排序 ''' from typing import List def count_sort(need_sortlist: List[int]) -> List[int]: """ 计数排序 适用于 1.整数排序。当数列元素不是整数时,不适合用计数排序。 2.数值区间小。当数列最大和最小值差距过大时,不适合用计数排序。 :param need_sortlist: :return: """ # 创建结果数组 res = [0 for i in range(len(need_sortlist))] # 获得数组最大值 max_val = max(need_sortlist) # 获得数组最小值 min_val = min(need_sortlist) # 创建计数数组,数组的长度等于最大值减去最小值+1,初始所有元素为0 # 元素值的含义为当前元素的下标在待排序数组中出现的次数 countlist = [0 for i in range(max_val - min_val + 1)] # 排序数组中 元素值 - 基准值 = 下标, for i in need_sortlist: countlist[i - min_val] += 1 # 计数数组元素值累加,代表下标在完成排序后数组中的*位次* for i in range(1, len(countlist)): countlist[i] += countlist[i - 1] # 逆序遍历待排序数组,在结果数组对应 *位次* 填入元素 for i in need_sortlist[-1::-1]: res[countlist[i - min_val] - 1] = i # 相同元素值每填入一个,位次-1 countlist[i - min_val] -= 1 return res # print(count_sort([95, 94, 91, 98, 99, 90, 99, 93, 91, 92])) def bucket_sort(need_sortelist: list) -> list: """ 桶排序 :param need_sortelist: 待排序的数组 :return: 排序完成的数组 """ res = [] # 数组最大值 max_val = max(need_sortelist) # 数组最小值 min_val = min(need_sortelist) # 桶的数量 bucket_num = len(need_sortelist) # 桶的区间跨度 d = float(max_val - min_val) / (bucket_num - 1) # 创建桶 bucket = [[] for i in range(bucket_num)] # 向桶里添加元素 for i in need_sortelist: if i == min_val: bucket[0].append(i) continue n = int((i - min_val) / d) bucket[n - 1].append(i) # print(bucket) # 对每个桶里的元素排序 for i in range(len(bucket)): # sorted() O(nlogn) bucket[i] = sorted(bucket[i]) # print(bucket) # 遍历桶,依次输出 for i in bucket: res.extend(i) return res print(bucket_sort([4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09]))
3.快速排序
''' @Author : "HCL" 利用递归分治的思想,快速排序 ''' import time from typing import List def quicksort(need_sortlist: List[int]) -> List[int]: """ 快速排序,利用递归分治的思想 :param need_sortlist: :return: """ # 设置递归边界 if len(need_sortlist) < 2: return need_sortlist provit = need_sortlist[0] # print(provit) # 比基准小的元素 small = [i for i in need_sortlist[1:] if i < provit] # 比基准大的元素 big = [i for i in need_sortlist[1:] if i > provit] return quicksort(small) + [provit] + quicksort(big)
这篇关于Python实现常见排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python