几种排序方法Python实现.docxVIP

窗体顶端有哪些信誉好的足球投注网站：窗体底端近期文章几种排序方法Python实现docker基础近期评论文章归档2016年十一月分类目录学习笔记 (2) docker (1) 算法 (1) 功能管理站点登出文章RSS评论RSSWordPress.org标签几种排序方法Python实现插入排序原理：将初始序列中的第一个元素作为一个有序序列，然后将剩下的 n-1 个元素按关键字大小依次插入该有序序列，每插入一个元素后依然保持该序列有序，经过 n-1 趟排序后使初始序列有序。其他说明：插入排序在最好的情况下时间复杂度为Θ(n)，比较次数为(n-1)次，移动元素次数是2(n-1)；最坏的情况下时间复杂度为Θ(n^2)；插入排序是稳定的排序算法。def ins_sort(list):? ? j =1? ? n =0? ? m =0? ? while j lt;len(list):? ? ? ? key =list[j]? ? ? ? i = j - 1? ? ? ? while i gt; -1andlist[i] lt; key:? ? ? ? ? ? list[i+1]=list[i]? ? ? ? ? ? list[i]= key? ? ? ? ? ? i = i - 1? ? ? ? ? ? n = n + 1? ? ? ? m = m + 1? ? ? ? j = j + 1? ? ? ? # print(list)? ? print(list,插入排序1---内部循环次数:, n,外部循环次数:, m)def ins_sort_2(list):? ? n =0? ? m =0? ? for j inrange(1,len(list)):? ? ? ? key =list[j]? ? ? ? i = j - 1? ? ? ? while i gt; -1andlist[i] lt; key:? ? ? ? ? ? list[i+1]=list[i]? ? ? ? ? ? list[i]= key? ? ? ? ? ? i = i - 1? ? ? ? ? ? # print(list)? ? ? ? ? ? n = n + 1? ? ? ? # print(result: ,list)? ? ? ? m = m + 1? ? print(list,插入排序2---内部循环次数:, n,外部循环次数:, m)?选择排序原理：将初始序列(A[0]~A[n-1])作为待排序序列，第一趟在待排序序列(A[0]~A[n-1])中找到最小值元素，将其与第一个元素A[0]交换，这样子序列(A[0])已经有序，下一趟在排序在待排序子序列(A[1]~A[n-1])中进行。第i趟排序在待排序子序列(A[i-1]~A[n-1])中找到最小值元素，与该子序列中第一个元素A[i-1]交换。经过 n-1 趟排序后使得初始序列有序。其他说明：选择排序的最好、最坏和平均情况的时间复杂度都为Θ(n^2)，而且它还需交换元素(n-1)次和移动元素3(n-1)次；它是不稳定的排序算法。def sel_sort(l):? ? n =0? ? m =0? ? for j inrange(len(l)-1):? ? ? ? min_key = j? ? ? ? for i inrange(j + 1,len(l)):? ? ? ? ? ? if l[i] gt; l[min_key]:? ? ? ? ? ? ? ? min_key = i? ? ? ? ? ? # print(内部循环：,l,(n + 1))? ? ? ? ? ? n = n + 1? ? ? ? key = l[j]? ? ? ? l[j]=l[min_key]? ? ? ? l[min_key]=key? ? ? ? # print(外部循环：, l,m + 1)? ? ? ? m = m + 1? ? print(l,选择排序---内部循环次数:, n,外部循环次数:, m)冒泡排序原理：第一趟在序列(A[0]~A[n-1])中从前往后进行两个相邻元素的比较，若后者小，则交换，比较 n-1 次；第一趟排序结束，最大元素被交换到A[n-1]中，下一趟排序只需要在子序列(A[0]~A[n-2])中进行；冒泡排序最多进行 n-1 趟。基本的冒泡排序可以利用旗标的方式稍微减少一些比较的时间，当寻访完序列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的比较与交换动作。其他说明：冒泡排序最好的情况下只需进行一趟排序，(n-1)次比较，此时的时间复杂度为O(n)，无需移动元素；最坏的情况下进行 n-1 趟排序，时间复杂度为O(n2)；冒泡排序是稳定的排序算法。def bubble_sort(l):? ? length