526互联

归并,基数排序及排序分析

发布时间 2023-08-19 17:19:31作者: harper886

归并,基数排序及排序分析

归并排序

将两个或两个以上的有序子序列"归并"为一个有序的序列.

image-20230819120711306

归并排序的演示

归并需要logn趟

image-20230819121010302

如何将两个有序序列合成一个有序序列?

使用前面学的两个线性表的合并

image-20230819121138748

image-20230819121218364

在同一个有序序列里面的合并操作

image-20230819121541364

归并排序算法分析

image-20230819121715670

归并排序方法的比较

image-20230819121752587

基数排序

基本思想:分配+搜集

也叫桶排序或箱排序.

按每个关键字进行排序

image-20230819163916438

第一趟按个位分配,然后按个位进行收集.

image-20230819164242479

第二趟按十位分配,然后按十位进行收集.

image-20230819164406583

第三趟按百位分配,然后按百位进行收集.

image-20230819164656568

排序结束

基数排序算法分析

image-20230819165020502

基数排序例子

基数排序不是基于比较的

image-20230819165422838

image-20230819165442863

各种排序方法的比较

1. 时间性能

image-20230819165745085

image-20230819165922579

2. 空间性能

image-20230819170106089

3. 排序的稳定性

image-20230819170248574

4. 排序方法的时间复杂度的下限

image-20230819170440121