node 做的大型网站,招聘网站开发工程师,痘痘该怎么去除效果好,网页项目本篇博客主要详细讲解一下其他排序#xff08;基数排序#xff0c;希尔排序和桶排序#xff09;也是排序综合系列里最后一篇博客。第一篇博客讲解的是LowB三人组#xff08;冒泡排序#xff0c;插入排序#xff0c;选择排序#xff09;#xff08;数据结构课设篇1…本篇博客主要详细讲解一下其他排序基数排序希尔排序和桶排序也是排序综合系列里最后一篇博客。第一篇博客讲解的是LowB三人组冒泡排序插入排序选择排序数据结构课设篇1python版排序综合第二篇博客讲解的是NB三人组堆排序归并排序快速排序数据结构课设篇2python版排序综合。
random和time库的用法在第一篇冒泡排序里讲解过。数据结构课设实验内容和要求也在第一篇博客中。
基数排序
概念
基数排序是一种非比较型的排序算法它根据数字的位数进行排序。它首先按照个位数进行排序然后按照十位数进行排序以此类推直到最高位数。基数排序适用于整数或字符串的排序。假设待排序的数据有 n 个每个数据的位数为 d数据的范围为 k那么基数排序的时间复杂度可以表示为 O(d*(nk))。基数排序的基本思想是
根据个位数进行排序将数据分配到0-9的桶中。按照顺序将桶中的数据合并起来。根据十位数进行排序再次将数据分配到0-9的桶中。按照顺序将桶中的数据合并起来。 依次类推直到最高位排序完成。
如图 代码及详细注释
import random
import time
def radix_sort(li):max_num max(li) # 找到列表中的最大值it 0 # 初始化迭代次数while 10 ** it max_num: # 循环直到最高位buckets [[] for _ in range(10)] # 定义十个空桶for val in li:digit (val // 10 ** it) % 10 # 取val的第it位数字个位、十位、百位等buckets[digit].append(val) # 将val放入对应的桶中# 分桶完成li.clear()for buc in buckets: # 将桶中的元素按顺序合并为一个列表li.extend(buc)# 把数重新写回liit 1 # 迭代次数加1li [random.randint(1, 100000000) for i in range(10000)]
print(li)
start time.time()
radix_sort(li)
end time.time()
print(li)
print(运行时间%s Seconds%(end-start))基数排序的思想和代码都比较好理解详细过程注释中都有说明。
运行结果 希尔排序
概念
希尔排序是一种插入排序的改进版本它通过将待排序的数据分成若干个小组分别进行插入排序然后逐渐减少小组的数量和增加小组内元素的间隔直到最后一次将整个数据序列作为一个小组进行插入排序。希尔排序的时间复杂度在O(nlogn)和O(n^2)之间。希尔排序的基本思想是
首先选择一个增量序列例如n/2、n/4、n/8等将待排序的数据分成若干个小组。然后对每个小组内的数据进行插入排序。接着逐渐减少增量重复上述步骤直到增量为1最后进行一次插入排序。
如图 代码及详细注释
import random
import time
def insert_sort_gap(li, gap):for i in range(gap, len(li)): # 从第gap个元素开始依次向前进行插入排序j i - gap # j指向当前元素的前一个元素tmp li[i] # 记录当前元素的值while j 0 and li[j] tmp: # 如果前面的元素比当前元素大li[j gap] li[j] # 将前面的元素后移gap位j - gap # 继续向前寻找插入位置li[j gap] tmp # 插入当前元素到正确的位置
def shell_sort(li):d len(li) // 2 # 初始步长取数组长度的一半while d 1:insert_sort_gap(li, d) # 对每个步长进行插入排序d // 2 # 步长减半li [random.randint(1, 100000000) for i in range(100000)]
print(li)
start time.time()
shell_sort(li)
end time.time()
print(li)
print(运行时间%s Seconds%(end-start))希尔排序的思路和代码也是比较好理解和实现的注释里讲解的还是比较详细的。
运行结果 桶排序
概念
桶排序是一种排序算法它将待排序的数据分成若干个桶然后对每个桶内的数据进行排序最后将所有桶内的数据按照顺序合并起来。桶排序适用于待排序的数据分布比较均匀的情况下。
桶排序的时间复杂度取决于使用的排序算法和桶的数量。在最理想的情况下桶排序的时间复杂度为O(nk)其中n是待排序元素的数量k是桶的数量。这是因为在最理想的情况下每个桶中的元素都是均匀分布的因此每个桶内的排序所需的时间是O(1)。然而在最坏的情况下所有元素都被放入同一个桶中此时桶排序的时间复杂度将变为O(nlogn)这是因为在这种情况下需要使用其他的排序算法对桶内的元素进行排序。 桶排序的基本思想是
首先确定桶的数量并将待排序的数据分配到对应的桶中。然后对每个桶内的数据进行排序可以使用任何一种排序算法通常使用插入排序或者快速排序。最后按照桶的顺序将所有桶内的数据合并起来。
如图 代码及详细注释
import random
import time
def bucket_sort(li, n100, max_num10000):buckets [[] for _ in range(n)] # 创建n个空桶for val in li:i min(val // (max_num // n), n - 1) # 计算val应该放到哪个桶里buckets[i].append(val) # 将val加入对应的桶中# 保持桶内的顺序for j in range(len(buckets[i]) - 1, 0, -1): # 对桶内元素进行排序if buckets[i][j] buckets[i][j - 1]: # 如果当前元素比前一个元素小buckets[i][j], buckets[i][j - 1] buckets[i][j - 1], buckets[i][j] # 交换两个元素的位置else:break # 如果当前元素大于等于前一个元素则停止排序sorted_li []for buc in buckets: # 将所有桶中的元素按顺序合并为一个列表sorted_li.extend(buc)return sorted_li # 返回排序后的列表li [random.randint(1, 100000000) for i in range(10000)]
print(li)
start time.time()
bucket_sort(li)
end time.time()
print(li)
print(运行时间%s Seconds%(end-start))运行结果 总结
至此排序综合系列讲解完毕排序综合1讲解了LowB三人组冒泡排序插入排序选择排序数据结构课设篇1python版排序综合排序综合2讲解了NB三人组堆排序归并排序快速排序数据结构课设篇2python版排序综合。这些也是数据结构的课设之一大家可以借鉴参考一下。总体来说排序的思路和代码还是相对与其他算法好理解和实现的 在这里我也给大家对所有讲过的排序进行一个运行效率上的比较不是通过时间复杂度而是通过运行结果在此之前每个排序我都对好几组不同内容和不同规模大小的数组进行排序运行最后得出的结果是桶排序和冒泡排序最慢其次是插入排序和选择排序再次是希尔排序最后是基数排序堆排序归并排序和快速排序其中基数排序在大规模运算下效率高运行时间最短如有不对欢迎指正。
