上次实现了几种排序方法，这次继续写其他的排序方法插入排序定义：插入排序是一种简单直观的排序算法。Sorted序列，对于未排序的数据，在sorted中从前向后扫描，找到对应的位置插入。(On^2)代码实现：definsert_sort(alist):#从第二个位置开始向前插入，即下标为1的元素foriinrange(1,len(alist)):#从第i个元素开始开始向前比较，如果小于前一个元素，则在range(i,0,-1)中为j交换位置：ifalist[j]len(nums):n=max(nums)else:n=len(nums)+1mid=max(nums)//nifmid==0:mid=1#创建一个所有元素为0的列表，作为一个桶bucket=[[]foriinrange(n+1)]#将所有元素放入桶中foriinnums:bucket[int(i/mid)].append(i)print(bucket)sort_nums=[]#取出桶中的元素forjinrange(len(bucket)):iflen(bucket[j])!=0:#如果len(bucket[j])>=2andlen(set(nums))!=1:bucket[j]=bucketSort(bucket[j],n)#取出bucket[j]中y的排序元素:sort_nums.append(y)returnsort_numsnums=[5,6,3,2,1,2,0,8,0,65]print(bucketSort(nums,5））计数排序的定义：计数排序不是基于比较的排序算法。它的核心是将输入的数据值转换成key，存储在一个额外的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入数据必须是一定范围内的整数。(On+k)代码实现defcountSort(arr):#outputsequenceifmax(arr)>len(arr):n=max(arr)+1else:n=len(arr)+1output=[0foriinrange(n)]#计数序列count=[0foriinrange(n)]foriinarr:count[i]+=1foriinrange(len(arr)):count[i+1]+=count[i]print(count)foriinrange(len(arr)):#下标从0开始output[count[arr[i]]-1]=arr[i]count[arr[i]]-=1return(output[:len(arr)])arr=[5,6,3,2,1,2,0,8,0]ans=countSort(arr)print(ans)#################字母排序##################defcountSort(arr):n=len(arr)#输出序列output=[0foriinrange(256)]#计数序列count=[0foriinrange(256)]ans=[""foriinrange(n)]foriinarr:count[ord(i)]+=1foriinrange(256):count[i]+=count[i-1]foriinrange(n):#下标从0开始output[count[ord(arr[i])]-1]=arr[i]count[ord(arr[i])]-=1foriinrange(len(arr)):ans[i]=output[i]returnansarr="wwwrunoobcom"ans=countSort(arr)print("字符数组排序%s"%("".join(ans)))选择排序定义：选择排序（Selectionsort)是一种简单直观的排序算法，其工作原理如下。先在未排序的序列中找到最小（最大）的元素，将其存入已排序序列的开头，然后继续从剩余未排序的元素中寻找最小（最大）的元素，然后放在已排序序列的末尾.依此类推，直到所有元素都排序完毕。选择排序的主要优点与数据移动有关。如果元素处于正确的最终位置，则不会移动它。选择排序每次交换一对元素，至少其中一个会被移动到它的最终位置，所以对n个元素的列表排序总共最多执行n-1次交换。在所有完全依靠交换来移动元素的排序方法中，选择排序是一种非常好的方法。(On^2)代码实现：defselection_sort(alist):n=len(alist)foriinrange(n-1):#记录最小位置min_index=iforjinrange(i+1,n):ifalist[j]
