首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构——排序

数据结构——排序

原创
作者头像
ruochen
修改2021-06-29 14:39:32
4460
修改2021-06-29 14:39:32
举报

排序(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;

各种排序算法比较

在这里插入图片描述
在这里插入图片描述

(数据不是顺次后移时将导致方法不稳定)


排序算法比较

  • 按平均时间排序方法分为四类 - O(n^2)undefined - O(nlogn) - O(n^(1+r)) - O(n)
  • 快速排序是基于比较的内部排序中平均性能最好的
  • 基数排序时间复杂度最低,但对关键字结构有要求
  • 为避免顺序存储时大量移动记录的时间开销,可考虑用链表作为存储结构 - 直接插入排序 - 归并排序 - 基数排序
  • 不宜采用链表作为存储结构的 - 折半插入排序 - 希尔排序 - 快速排序 - 堆排序

排序算法选择规则

  • n较大时 - 分布随机,稳定性不做要求,则采用快速排序 - 内存允许,要求排序稳定时,则采用归并排序 - 可能会出现正序或逆序,稳定性不做要求,则采用排序或归并排序
  • n较小时 - 基本有序,则采用直接插入排序 - 分布随机,则采用简单选择排序,若排序码不接近逆序,也可以采用直接插入排序

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 排序(sorting)
    • 什么是排序
      • 排序的目的是什么?
        • 什么叫内部排序?什么叫外部排序?
          • 排序算法的好坏如何衡量?
            • 排序的分类
              • 内部排序
              • 外部排序
            • 存储方式
            • 各种排序算法比较
              • 排序算法比较
                • 排序算法选择规则
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档