7.2 定义

给出排序问题的形式化描述:设给定的一个记录表 (R0,R1,,Rn1)(R_0, R_1, \cdots, R_{n-1}),其中每个记录 RiR_i 都有一个关键字 KiK_i 与其对应。而且,在关键字上存在一个次序关系 ( << ),对于任意两个关键字值 xxyy,总有 x=yx = yx<yx < yy<xy < x 之一存在。这个次序关系满足传递性,即对于任意三个关键字值 xxyyzz,如果 x<yx < yy<zy < z,则有 x<zx < z。排序问题就是寻找一个置换,使得对于任意一个 ii0<in10 < i \leq n-1,都有 Kσ(i1)Kσ(i)K_{\sigma(i-1)} \leq K_{\sigma(i)}。于是,所期望的记录排列次序就是 (Rσ(0),Rσ(1),,Rσ(n1))(R_{\sigma(0)}, R_{\sigma(1)}, \cdots, R_{\sigma(n-1)})

由于在一个表中可能出现多个相同的关键字值,所以置换的结果不是唯一的。在某些应用中,希望能够找到唯一的具有如下性质的置换 σs\sigma_s

  1. [有序性] 对于任意 ii0<in10 < i \leq n-1,都有 Kσ(i1)Kσ(i)K_{\sigma(i-1)} \leq K_{\sigma(i)}
  2. [稳定性] 在输入表中,如果 i<ji < jKi=KjK_i = K_j,那么,在排序后的结果中,记录 RiR_i 排在记录 RjR_j 的前面。

  3. 能够产生上述置换 σs\sigma_s 的排序方法称为 「稳定的 stable」。稳定性只是用于区别各种排序方法的一个判断标准。此外,还可以根据排序场所和所使用的排序方法来区分不同的排序。这里排序场所指的是在什么地方进行排序。所以,

  4. 「内部排序 internal sort」 是指在表的规模足够小,能够全部放在内存中进行排序的方法。而当被排序的数据信息规模足够大,不能全部放入内存时,则需使用
  5. 「外部排序 external sort」,文件必须分段装入内存,直到整个文件被排好为止。

results matching ""

    No results matching ""