排序

简介:

定义:

将一组杂乱无章的数据按一定规律顺次排列起来

目的:

便于查找

内部排序:

若待排序都在内存中,则称为内部排序

外部排序:

若待排序记录一部分在内存,一部分在外存,则称为外部排序。

注意:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。


排序算法的好坏如何衡量?

时间效率—–排序速度(比较次数与移动次数)

空间效率—–占内存辅助空间的大小

稳定性——A和B的关键字相等,排序后A、B的先后次序保持不变,则称为这种排序算法是稳定的。


排序算法分类

(1)依据原则来分类

  1. 插入排序

  2. 交换排序

  3. 选择排序

  4. 归并排序

  5. 基数排序

(2)按所需的工作量分类

  1. 简单的排序方法,其时间复杂度为O(n*n)

  2. 先进的排序方法,其时间复杂度为O(nlog2n);

  3. 基数排序,其时间复杂度为O(d*n)

待排序记录的存储方式

    #define MAXSIZE 20  //设记录不超过20个

    typedef int KeyType; //设关键字为整数型

    Typedef struct{      //定义每个记录(数据元素)的结构

    KeyType Key;          //关键字

    InfoType otherinfo;   //其他数据项

    }RedType;

    Typedef struct{              //定义顺序表的结构

    RedType r【MAXSIZE+1】;  //存储顺序表的向量

    int length;   //顺序表的长度

    }SqList;
目录
相关文章
|
算法 搜索推荐 调度
排序的介绍
排序的介绍
|
2月前
排序1
排序1
16 0
|
6月前
|
存储 搜索推荐
排序的总结
排序的总结
|
存储 搜索推荐 算法
排序相关问题
排序相关问题
65 1
|
搜索推荐
7-207 排序
7-207 排序
58 0
|
存储 缓存 算法