> 文档中心 > 【基数排序~python】

【基数排序~python】

python进阶江湖

  • 基数排序
  • 个人数据结构小总结:
  • 上一章链接:[计数排序](https://blog.csdn.net/m0_66318554/article/details/124755654)
    • 江湖一言:
      • 持续更新中...

基数排序

# -*- coding = utf-8 -*-# @Time : 2022/5/16 19:35# @Author : lxw_pro# @File : py-17.py# @Software : PyCharm# 基数排序:'''多关键字排序:假如现在有一个员工表,要求按照薪资排序,     年龄相同的员工按照年龄排序。先按照年龄进行排序,在按照薪资进行稳定的排序''''''时间复杂度:O(kn)空间复杂度:O(k+n)注意:k表示数字位数'''import randomdef j_sort(li):    max_num = max(li)   # li中的最大值,如9→1, 99→2,999→3,88888→5    t = 0 # 存储一个变量    while 10 ** t <= max_num: ts = [[] for _ in range(10)] for tol in li:     digit = (tol // 10 ** t) % 10   # 列出个位     ts[digit].append(tol) # 分桶完成 li.clear() for ton in ts:     li.extend(ton)    # 将数量添加到li中 t += 1  # 每过一次循环增加一次li = list(range(1000)) # 随机列出1000个数random.shuffle(li)     # random.shuffle() 函数将序列中的元素随机打乱j_sort(li)      # 调用print(li)

个人数据结构小总结:

'''一、 数据结构的底层存储方式只有两种:数组(顺序存储)和链表(链式存储)。二者的优缺点如下:数组由于是紧凑连续存储,因此可以随机访问,通过索引快速找到对应的元素,而且相对于节约存储空间。但正因为连续存储,内存空间必须一次性分配足,所以数组如果要扩容,需要先重新分配一块更大的空间,在把数据全被复制过去,时间复杂度为O(N);而且如果想在数组中间进行插入和删除操作,每次必须搬移后面的所有数据以保持连续,时间复杂度为O(N)。链表因为元素不连续,靠指针指向下一个元素的位置,所以不存在数组的扩容问题;如果知道某一元素的前驱和后驱,操作指针即可杀出该元素或者插入新元素,时间复杂度O(1)。但是正因为存储空间不连续,你无法根据一个索引算出对应元素的地址,所以不能随机访问;而且由于每个元素必须存储指向前后元素位置的指针,因此会消耗相对更多的存储空间。数据结构种类很多,但他们存在的目的无非就是在不同的应用场景下尽可能高效地增、删、查、改。所谓的框架思维,就是套路。不管增、删、查、改,这些代码都是永远无法脱离的结构。数据结构是工具,算法是通过合适的工具解决特定问题的方法。先刷二叉树,先刷二叉树,先刷二叉树?因为二叉树是最容易培养框架四位,而且大部分常考算法本质上都是树的遍历问题。'''

上一章链接:计数排序


江湖一言:

司马懿说:
看人之短,天一无一可交之人;
看人之长,世间一切皆是吾师;
这一路走来,没有敌人,
全是朋友和老师。


持续更新中…