达川网站制作,品牌软文营销案例,seo查询,四平网站优化1.冒泡排序:冒泡排序算法的运作如下#xff1a;比较相邻的元素。如果第一个比第二个大(升序)#xff0c;就交换他们两个。对每一对相邻元素作同样的工作#xff0c;从开始第一对到结尾的最后一对。这步做完后#xff0c;最后的元素会是最大的数。针对所有的元素重复以上的步…1.冒泡排序:冒泡排序算法的运作如下比较相邻的元素。如果第一个比第二个大(升序)就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。def bulle_sort(a):for i in range(0,len(a)-1): # 外层循环for j in range(0,len(a)-1-i): #每层循环所需要的操作if a[j]a[j1]: # 比较两个元素的大小a[j],a[j1]a[j1],a[j] # 交换位置,便可得到当此循环的最大值,并放到最后时间复杂度最优时间复杂度O(n) (表示遍历一次发现没有任何可以交换的元素排序结束。)最坏时间复杂度O(n2)稳定性稳定2.选择排序选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小(大)元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。def select_sort(a):for i in range(0,len(a)-1):for j in range(i1,len(a)):if a[i]a[j]:a[i],a[j] a[j],a[i] # 找到最小的,然后进行交换时间复杂度最优时间复杂度O(n2) # 因为每次都是进行完全遍历,不管是否先排好序最坏时间复杂度O(n2)稳定性不稳定(考虑升序每次选择最大的情况)3.插入排序插入排序(英语Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。def insert_sort(a):for i in range(1,len(a)):for j in range(0,i): # 这里是从前面插入,当然,这里也可以从后面插入,只需要把j从大到小,后面的if条件也相反就可以if a[j]a[i]:a[j],a[i] a[i],a[j] # 将元素插入到前面排好序的数据中时间复杂度:最优时间复杂度O(n) (升序排列序列已经处于升序状态)最坏时间复杂度O(n2)稳定性稳定4.快速排序快速排序(英语Quicksort)又称划分交换排序(partition-exchange sort)通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。步骤为从数列中挑出一个元素称为基准(pivot)重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后该基准就处于数列的中间位置。这个称为分区(partition)操作。递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形是数列的大小是零或一也就是永远都已经被排序好了。虽然一直递归下去但是这个算法总会结束因为在每次的迭代(iteration)中它至少会把一个元素摆到它最后的位置去。def quick_sort(a,start0,endlen(a)-1):#设置基准# start 0# end len(a)-1if startend:returncur a[start] # 设置判定基准while start时间复杂度最优时间复杂度O(nlogn)最坏时间复杂度O(n2)稳定性不稳定5.希尔排序希尔排序的基本思想是将数组列在一个表中并对列分别进行插入排序重复这过程不过每次用更长的列(步长更长了列数更少了)来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法算法本身还是使用数组进行排序。def shell_sort(a):# 设定插入的长度n len(a)length n//2# 进入循环体while length0:for i in range(length,n):j iwhile jlength and a[j-length]a[j]: # 相当于进行列排序a[j-length],a[j] a[j],a[j-length]j - length# 更新步长length length//2时间复杂度最优时间复杂度根据步长序列的不同而不同最坏时间复杂度O(n2)稳定想不稳定6.归并排序归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组再合并数组。将数组分解最小之后然后合并两个有序数组基本思路是比较两个数组的最前面的数谁小就先取谁取了后相应的指针就往后移一位。然后再比较直至一个数组为空最后把另一个数组的剩余部分复制过来即可。def merge_sort(a):# 设置递归的终止条件if len(a)1:return a# 拆开n len(a)//2left merge_sotr(a[0:n])right merge_sort(a[n:])# 进行合并return merge(left,right)def merge(left,right):cur_left 0cur_right 0result []# 将排序好的两个列表进行合并排序:while cur_left时间复杂度最优时间复杂度O(nlogn)最坏时间复杂度O(nlogn)稳定性稳定常见排序算法效率比较
