上次实现了几个排序形式，这次咱们持续往下再来写一下其余的排序形式
插入排序
定义：
插入排序是一种简略直观的排序算法，它的工作原理是通过构建有序序列，对未排序数据，在已排中从前向后扫描，找到相应地位并插入。（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_nums
nums = [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 ans
arr = "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)这样的排序形式，你学废了吗？