首页 > 代码库 > 排序概述

排序概述

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下:
输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn
输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1.被排序对象--文件
被排序的对象--文件由一组记录组成。
记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录,称为关键字项。该数据项的值称为关键字(Key)。
注意:
     在不易产生混淆时,将关键字项简称为关键字。
2.排序运算的依据--关键字
    用来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。
     关键字的选取应根据问题的要求而定。
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用"准考证号"作为关键字。若要按照考生的总分数排名次,则需用"总分数"作为关键字。

衡量排序算法的指标:

  • 时间复杂度:主要分析关键字的比较次数和记录的移动次数;
  • 空间复杂度:分析排序算法中需要多少辅助内存;
  • 稳定性:若两个记录A和B的关键字值相等,但排序后A、B的先后次序保持不变,则称这种算法是稳定的;反之就是不稳定的。

分类

  • 内部排序:排序过程不需要借助外部存储器(如磁盘等),所有排序都是在内存中完成;
  • 外部排序:排序过程需要借助于外部存储器,特别是数据量非常大时;
    • 外部排序最常用的算法就是多路归并排序,即将源文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序,接下来再对多个有序的子文件进行归并排序。

排序算法