史上最简单十大排序算法(Python实现) |
您所在的位置:网站首页 › python给集合排序 › 史上最简单十大排序算法(Python实现) |
目录 十大排序算法(Python实现) 一. 算法介绍及相关概念解读 算法分类 相关概念 1. 交换排序 1.1 冒泡排序(Bubble Sort) 1.2 快速排序(Quick Sort) 2. 插入排序 2.1 简单插入排序(Insert Sort) 2.2 希尔排序(Shell Sort) 3.选择排序 3.1 简单选择排序(Select Sort) 3.2 堆排序(Heap Sort) 4. 归并排序 4.1 二路归并排序(Two-way Merge Sort) 5. 线性时间非比较类排序 5.1 计数排序(Counting Sort) 5.2 桶排序(Bucket Sort) 5.3 基数排序(Radix Sort) 十大排序算法(Python实现) 一. 算法介绍及相关概念解读算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。 线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。 相关概念 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。 1. 交换排序 1.1 冒泡排序(Bubble Sort) 比较相邻的元素。如果第一个比第二个大,就交换它们两个;对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;针对所有的元素重复以上的步骤,除了最后一个;重复步骤1~3,直到排序完成。 冒泡排序对n个数据操作n-1轮,每轮找出一个最大(小)值。 操作只对相邻两个数比较与交换,每轮会将一个最值交换到数据列首(尾),像冒泡一样。 每轮操作O(n)次,共O(n)轮,时间复杂度O(n^2)。 额外空间开销出在交换数据时那一个过渡空间,空间复杂度O(1) def BubbleSort(lst): n=len(lst) if nlst[j+1]: (lst[j],lst[j+1])=(lst[j+1],lst[j]) return lst x=input("请输入待排序数列:\n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=BubbleSort(arr) #print(arr) print("数列按序排列如下:") for i in arr: print(i,end=' ') 1.2 快速排序(Quick Sort) 从数列中挑出一个元素,称为 “基准”(pivot);重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。快速排序基于选择划分,是简单选择排序的优化。 每次划分将数据选到基准值两边,循环对两边的数据进行划分,类似于二分法。 算法的整体性能取决于划分的平均程度,即基准值的选择,此处衍生出快速排序的许多优化方案,甚至可以划分为多块。 基准值若能把数据分为平均的两块,划分次数O(logn),每次划分遍历比较一遍O(n),时间复杂度O(nlogn)。 额外空间开销出在暂存基准值,O(logn)次划分需要O(logn)个,空间复杂度O(logn) def QuickSort(lst): # 此函数完成分区操作 def partition(arr, left, right): key = left # 划分参考数索引,默认为第一个数为基准数,可优化 while left < right: # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现 while left < right and arr[right] >= arr[key]: right -= 1 # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现 while left < right and arr[left] = right: return # 从基准开始分区 mid = partition(arr, left, right) # 递归调用 # print(arr) quicksort(arr, left, mid - 1) quicksort(arr, mid + 1, right) # 主函数 n = len(lst) if n =0 and arr[j]>temp): #从后向前,找打比其小的数的位置 arr[j+d]=arr[j] #向后挪动 j-=d if j!=i-d: arr[j+d]=temp n=len(lst) if n=1: shellinsert(lst,d) d=d//2 return lst x=input("请输入待排序数列:\n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=ShellSort(arr) #print(arr) print("数列按序排列如下:") for i in arr: print(i,end=' ')希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的。 3.选择排序 3.1 简单选择排序(Select Sort) 初始状态:无序区为R[1..n],有序区为空;第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;n-1趟结束,数组有序化了。简单选择排序同样对数据操作n-1轮,每轮找出一个最大(小)值。 操作指选择,即未排序数逐个比较交换,争夺最值位置,每轮将一个未排序位置上的数交换成已排序数,即每轮选一个最值。 每轮操作O(n)次,共O(n)轮,时间复杂度O(n^2)。 额外空间开销出在交换数据时那一个过渡空间,空间复杂度O(1)。 def SelectSort(lst): n=len(lst) if n |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |