特殊有序集的线形时间排序算法
2021/10/13 22:14:19
本文主要是介绍特殊有序集的线形时间排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
计数排序算法O(m+n)
桶排序算法O(m+n)
思想:给全集的每一个元素键值设相应的桶,将元素按键值对号入桶,让同一个桶内的元素保有被输入时的相应顺序‘然后利用全集的有序性,按键值的顺序收集各相应的桶中的元素。
基数排序
最高位优先法(MSD):先对最高位关键字k1(如花色)排序,将序列分成若干子序列,每个子序列有相 同的k1值;然后让每个子序列对次关键字k2(如面值) 排序,又分成若干更小的子序列;依次重复,直至就 每个子序列对最低位关键字kd排序;最后将所有子序列依次连接在一起成为一个有序序列
最低位优先法(LSD):从最低位关键字kd起进行排序, 然后再对高一位的关键字排序,……依次重复,直至对最高位关键字k1排序后,便成为一个有序序列
MSD与LSD不同特点:
按MSD排序,必须将序列逐层分割成若干子序列,然后对各子序列分别排序
按LSD排序,不必分成子序列,对每个关键字都是整个序列参加排序;并且可不通过关键字比较,而通过若干次分配与收集实现排序
链式基数排序步骤(10进制)
设置10个队列,f[i]和e[i]分别为第i个队列的头指针和尾指针;第一趟分配对最低位关键字(个位)进行,改变记录的指针值,将链表中记录分配至10个链队列中,每个队 列记录的关键字的个位相同;第一趟收集是改变所有非空队列的队尾记录的指针域,令其指向下一个非空队列的队头记录,重新将10个队列链成一个链表;重复上述两步,进行第二趟、第三趟分配和收集,分 别对十位、百位进行,最后得到一个有序序列。
这篇关于特殊有序集的线形时间排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南