上次实现了几个排序形式，这次咱们持续往下再来写一下其余的排序形式
插入排序
定义：
插入排序是一种简略直观的排序算法，它的工作原理是通过构建有序序列，对未排序数据，在已排中从前向后扫描，找到相应地位并插入。（On^2） 代码实现：
def insert_sort(alist): # 从第二个地位，即下标为1的元素开始向前插入 for i in range(1, len(alist)): # 从第i个元素开始向前比拟，如果小于前一个元素，替换地位 for j in range(i, 0, -1): if alist[j] < alist[j-1]: alist[j], alist[j-1] = alist[j-1], alist[j]alist = [54,26,93,17,77,31,44,55,20]insert_sort(alist)print(alist)桶排序
定义：
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的要害就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假如输出数据遵从均匀分布，将数据分到无限数量的桶里，每个桶再别离排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排）。（On^2） 代码实现
def bucketSort(nums, n): # 抉择一个最大的数 if max(nums) > len(nums): n = max(nums) else: n = len(nums) + 1 mid = max(nums) // n if mid == 0: mid = 1 # 创立一个元素全是0的列表, 当做桶 bucket = [[] for i in range(n + 1)] # 把所有元素放入桶中 for i in nums: bucket[int(i / mid)].append(i) print(bucket) sort_nums = [] # 取出桶中的元素 for j in range(len(bucket)): if len(bucket[j]) != 0: # 应用递归持续桶排序 if len(bucket[j]) >= 2 and len(set(nums)) != 1: bucket[j] = bucketSort(bucket[j], n) # 取出排序好的元素 for y in bucket[j]: sort_nums.append(y) return sort_numsnums = [5, 6, 3, 2, 1, 2, 0, 8, 0, 65]print(bucketSort(nums, 5))计数排序
定义：计数排序不是基于比拟的排序算法，其外围在于将输出的数据值转化为键存储在额定开拓的数组空间中。作为一种线性工夫复杂度的排序，计数排序要求输出的数据必须是有确定范畴的整数。(On+k) 代码实现
def countSort(arr): # 输入序列 if max(arr) > len(arr): n = max(arr) + 1 else: n = len(arr) + 1 output = [0 for i in range(n)] # 计数序列 count = [0 for i in range(n)] for i in arr: count[i] += 1 for i in range(len(arr)): count[i + 1] += count[i] print(count) for i in range(len(arr)): # 下标从0开始 output[count[arr[i]] - 1] = arr[i] count[arr[i]] -= 1 return (output[:len(arr)])arr = [5,6,3,2,1,2,0,8,0]ans = countSort(arr)print(ans)#################字母排序##################def countSort(arr): n = len(arr) # 输入序列 output = [0 for i in range(256)] # 计数序列 count = [0 for i in range(256)] ans = ["" for i in range(n)] for i in arr: count[ord(i)] += 1 for i in range(256): count[i] += count[i - 1] for i in range(n): # 下标从0开始 output[count[ord(arr[i])] - 1] = arr[i] count[ord(arr[i])] -= 1 for i in range(len(arr)): ans[i] = output[i] return ansarr = "wwwrunoobcom"ans = countSort(arr)print("字符数组排序 %s" % ("".join(ans)))抉择排序
定义：
抉择排序（Selection sort）是一种简略直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，寄存到排序序列的起始地位，而后，再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端。以此类推，直到所有元素均排序结束。
抉择排序的次要长处与数据挪动无关。如果某个元素位于正确的最终地位上，则它不会被挪动。抉择排序每次替换一对元素，它们当中至多有一个将被移到其最终地位上，因而对n个元素的表进行排序总共进行至少n-1次替换。在所有的齐全依附替换去挪动元素的排序办法中，抉择排序属于十分好的一种。(On^2)
代码实现：
def selection_sort(alist): n = len(alist) for i in range(n-1): # 记录最小地位 min_index = i for j in range(i+1, n): if alist[j] < alist[min_index]: min_index = j # 如果抉择出的数据不在正确地位，进行替换 if min_index != i: alist[i], alist[min_index] = alist[min_index], alist[i]alist = [54,226,93,17,77,31,44,55,20]selection_sort(alist)print(alist)这样的排序形式，你学废了吗？