表述

这个集合可能已经存储在计算机的随机存储器(RAM)中,当然也有可能只是存储在文件系统的某个文件上,而文件系统通常叫做二级存储器。这个数据集合也有可能被存档在一个第三级的存储器上,此时在存储器上寻找数据就需要额外的处理时间。而且,这些数据在处理之前需要复制到第二级存储器上。第三级存储器一般包括磁带和光学光碟柜。

数据在随机存储器上一般以两种形式保存:基于指针的存储和基于值的存储。假设有人想排序"eagle"、"cat"、"ant"、"dog"和"ball"这些字符串。使用基于指针的存储,如图4-2所示,一个数组(图中连续的方块)包含了指向实际信息(椭圆中的字符串)的指针,而不是直接将信息存储在数组元素的存储空间里面。使用这种方式,我们能够灵活地存储和排序任意复杂结构的数据。

阅读 ‧ 电子书库
图 4-2 使用指针排序

相反地,基于值的存储将n个元素的数据集合打包存储在固定大小的记录块中,这个固定大小定为s(这种方法比较适合于第二级或者第三级存储器)。图4-3表示了如何使用每个大小为5字节的连续存储块来存储图4-2中的数据。在这个例子中,我们处理的数据是字符串,不过同样也可以是其他的结构化的基于记录的信息。“¬”字符表示字符串的结束。在编码中,长度为s的字符串并不包含终止字符。这个字符串集合中的字符串是紧挨着的,并且可以看做是一个一维的数组B[0,n*s)。注意,B[r*s+c]表示第r个单词的第c个字符(c≥0,r≥0),同样的,这个数据集合的第i个元素(i≥0)是子序列B[i*s,(i+1)*s)。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

阅读 ‧ 电子书库
图 4-3 基于值的排序

在第二级存储器上存储的信息一般都是基于值的连续字节集合。在第二级存储器上保存一个整数值来表示指针,指向一个有序集合存在磁盘文件的偏移量是可行的。本章将要介绍的算法也能够对磁盘上的数据进行排序,只需要简单地实现在磁盘文件之间交换字节的函数即可。但是,因为对第二级存储器的存取操作会增加很多输入输出请求,性能将会大幅下降。

无论是基于指针的存储还是基于值的存储,一个排序算法都使得数据(在两种情况下,方框均表示数据本身)变得有序。为了简单起见,即使是使用基于值的存储时,我们都将使用A[i]来表示第i个元素。