在线excel表格助力企业高效管理与数据分析的未来趋势
647
2022-05-29
排序(sorting)
什么是排序
排序的目的是什么?
什么叫内部排序?什么叫外部排序?
排序算法的好坏如何衡量?
排序的分类
内部排序
外部排序
存储方式
各种排序算法比较
排序算法比较
排序算法选择规则
排序(sorting)
什么是排序
将一组杂乱无章的数据按一定规律顺次排列起来。
数据表 (datalist):它是待排序数据对象的有限集合。
主关键字(key): 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据,称为关键字。也称为排序码。
排序的目的是什么?
便于查找!
什么叫内部排序?什么叫外部排序?
若待排序记录都在内存中,称为内部排序;
若待排序记录一部分在内存,一部分在外存,则称为外部排序。
外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。
排序算法的好坏如何衡量?
时间效率——排序速度(比较次数与移动次数)
空间效率——占内存辅助空间的大小
稳定性——A和B的关键字相等,排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。
排序的分类
内部排序
插入排序
直接(折半)插入排序
希尔排序
交换排序
冒泡排序
快速排序
选择排序
归并排序
基数排序
外部排序
借助外部的辅助存储器(比如:硬盘),由于数据是存在外存中,故数据不可随机被存取
存储方式
地址连续的一组存储单元(记录之间的次序关系由存储位置决定,实现排序必须借助移动记录)
静态链表(记录之间的次序关系由指针指示,实现排序不需要移动记录,仅需修改指针)--链表排序
地址连续的一组存储单元,另设一个指示各个记录存储位置的地址向量,在排序过程中不移动记录本身,而移动地址向量中的地址,在排序之后再按照地址向量中的值调整记录的存储位置--地址排序
#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为整型量(int型) typedef struct { // 定义每个记录(数据元素)的结构 KeyType key; // 关键字 InfoType otherinfo; // 其他数据项 } RedType; typedef struct { // 定义顺序表的结构 RedType r[MAXSIZE + 1]; // 存储顺序表的向量 // r[0]一般作哨兵或缓冲区 int length; // 顺序表的长度 } SqList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
各种排序算法比较
(数据不是顺次后移时将导致方法不稳定)
排序算法比较
按平均时间排序方法分为四类
O(n^2)
O(nlogn)
O(n^(1+r))
O(n)
快速排序是基于比较的内部排序中平均性能最好的
基数排序时间复杂度最低,但对关键字结构有要求
为避免顺序存储时大量移动记录的时间开销,可考虑用链表作为存储结构
直接插入排序
归并排序
基数排序
不宜采用链表作为存储结构的
折半插入排序
希尔排序
快速排序
堆排序
排序算法选择规则
n较大时
分布随机,稳定性不做要求,则采用快速排序
内存允许,要求排序稳定时,则采用归并排序
可能会出现正序或逆序,稳定性不做要求,则采用堆排序或归并排序
n较小时
基本有序,则采用直接插入排序
分布随机,则采用简单选择排序,若排序码不接近逆序,也可以采用直接插入排序
数据结构
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。