第八章排序 基本概念 排序是计算机程序设计中的一种重要运算,其功能是将 个数据元素或记录)的任意序列,重新排列成一个按关键字有 序的序列 排序的确切定义为:设含有n个记录的序列为R,R2…,R} 其相应的关键字序列为{1K2…K,需确定一种排列 PH2使其相应的关键字满足如下的非递减关系 {Kn≤K2≤…≤Km},或非递增关系{n≥K2≥…≥Km 即使原来的序列R,R2…,R}成为一个按关键字有序的序列 {Rn1,R2…Rmn},这样的一种操作称为排序 定义中的关键字K可以是记录R(=1,2,…,n)主关键字 此时任何一个记录的无序序列经排序后得到的结果是唯一的第 八 章 排 序 基本概念 排序是计算机程序设计中的一种重要运算, 其功能是将一 个数据元素(或记录)的任意序列, 重新排列成一个按关键字有 序的序列. 排序的确切定义为: 设含有n个记录的序列为 R1 ,R2 ,  ,R n  其相应的关键字序列为 K1 ,K2 ,  ,K n  , 需确定一种排列 p1, p2,  , pn, 使其相应的关键字满足如下的非递减关系 K p1  K p2  K pn , 或非递增关系 K p1  K p2  K pn 即使原来的序列 R1 ,R2 ,  ,R n  成为一个按关键字有序的序列 R p1 ,R p2 ,  ,R pn , 这样的一种操作称为排序. 定义中的关键字 Ki 可以是记录 R (i 1,2, ,n) i =  主关键字 此时任何一个记录的无序序列经排序后得到的结果是唯一的