一、桶排序
1. 算法思想：桶排序是将待排序序列中处于相同值域的元素存入同一个桶中，即将一个数据表分割成许多桶，然后每个桶中的元素各自排序。它采用分治策略，是一种分布式的排序方法。
2. 算法过程：
（1）根据待排序序列中最大元素和最小元素的差值和映射规则，确定申请的桶个数；
（2）遍历待排序序列，将每一个元素存储到对应的桶中；
（3）分别对每一个桶中元素进行排序，并存储到原序列中，获得一个已排序序列。
3. 图例分析：
待排序序列为：[29, 25, 3, 49, 9, 37, 21, 43]，以间隔大小10来区分不同值域，待申请桶的个数为5。
4. 代码演示：
def bucket_sort(a:list)->list:
step = 10 #以间隔大小10来区分不同值域
maximum, minimum = max(a), min(a)
buckets = [[] for i in range(maximum //step - minimum // step + 1)] #桶的数量
for i in a: #将处于相同值域（即index相同）的元素存入同一个桶中
index = i // step - minimum // step
buckets[index].append(i)
a.clear()
for b in buckets:
b.sort() #对每一个桶中元素进行排序
a.extend(b) #将各个桶的元素按顺序存储到原序列中
return a
二、简单计数排序
1. 算法思想：若待排序序列的元素均为非负整数，且最大值为maximum，则分配maximum+1个桶，每个桶的编号（下标）就等于待排序元素的值，每个桶的元素值就是存入桶中的待排序元素个数。为了描述方便，我们将桶序列称为统计数组。
2. 算法过程：
（1）根据待排序序列中最大元素值，确定申请的桶个数，并将桶全部清空；
（2）统计待排序序列中每个值为i的元素出现的次数，存入编号为i的桶；
（3）依次把数据从桶里倒出来，存储到原序列中，获得一个已排序序列。
3. 图例分析：
待排序序列为：[3, 5, 1, 0, 3, 0]，待申请桶的个数为5+1=6。
4. 代码演示：
def counting_sort(a:list)->list:
n = max(a) + 1
c = [0] * n #将所有的桶均清空
for num in a: #将值为num的元素存入下标为num桶中
c[num] += 1
a.clear()
for i in range(n): #依次把数据从桶里倒出来
a.extend([i] * c[i]) #依次存储所有值为i的元素
return a
三、优化计数排序
简单计数排序有两个缺陷，一是根据最大元素值来确定桶的数量，完全不考虑最小元素值，当最小值也很大时会造成空间浪费。二是统计数组中的桶相当于一个“栈”数据结构，具有“先进后出”特征，如果我们直接按顺序把数据从桶里倒出来，存储到原数组a中，就会改变数组a中等值元素的相对位置，造成“不稳定排序”的后果。
下面我们对这两个缺陷进行改进。
1. 算法思想：对于待排序序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。它相当于桶排序中step=1的一个特例，因此它需要创建桶的数量为maximum - minimum + 1，每个桶的编号（下标）就等于待排序元素的值，每个桶的元素值就是存入桶中的待排序元素个数。为了描述方便，我们将桶序列称为统计数组。
2. 算法过程：
（1）根据待排序序列中最大元素和最小元素的差值，确定申请桶的个数，并将桶全部清空；
（2）统计待排序序列中每个值为i的元素出现的次数，存入编号为i的桶；
（3）依次求出每个桶的前缀和；
（4）反向填充目标数组，每放一个元素就将对应桶的元素值减一。
3. 图例分析：
待排序序列为：[3, 5, 1, 0, 3, 0]，待申请桶的个数为5-0+1=6。
4. 代码演示：
def counting_sort2(a:list)->list:
maximum, minimum = max(a), min(a)
c = [0] * (maximum - minimum + 1) #将所有的桶均清空
for i in a: #将值为i的元素存入下标为i桶中
c[i-minimum] += 1
for i in range(1, len(c)): #依次求出每个桶的前缀和
c[i] += c[i-1]
b = [0] * len(a)#设置目标数组
for i in a[::-1]: #反向填充目标数组
c[i-minimum] -= 1
b[c[i-minimum]] = i
return b
四、基数排序
1. 算法思想：基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。
2. 算法过程：
（1）将所有待比较数值统一为同样的数位长度，数位较短的数前面补零；
（2）从最低位开始，依次进行一次桶排序；
（3）从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
3. 图例分析：
待排序序列为：[53, 3, 542, 748, 14, 214, 154, 63, 616]，数位长度为3。
4. 代码演示：
def radix_sort(a:list)->list:
def cout_sort(a:list, exp:int):
c = [0] * 10
for i in a:
c[(i//exp)%10] += 1
for i in range(1, len(c)): #依次求出每个桶的前缀和
c[i] += c[i-1]
t = a[::-1] #将原数组逆序复制到临时数组t
for i in t: #反向填充目标数组
c[(i//exp)%10] -= 1
a[c[(i//exp)%10]] = i
exp, m = 1, max(a)
while m // exp > 0:
cout_sort(a, exp)
exp *= 10
return a
网友评论