北斗卫星导航系统 (BeiDou navigation satellite system, BDS) 是我国自行研制的全球卫星导航系统，是继美国全球卫星定位系统 (global positioning system, GPS) 和俄罗斯全球卫星导航系统 (global navigation satellite syste, GLONASS) 之后第3个成熟的卫星导航系统，可全天候、全天时为各类用户提供高精度、高可靠的定位、导航和授时服务，以及短报文通信能力^[1]。2012年12月27日，北斗导航业务正式对亚太地区提供无源定位、导航、授时服务。预计到2020年左右，北斗卫星导航系统将完成星座部署，对全球地区提供服务。

在北斗卫星导航系统正式提供服务之前，需要对北斗的性能进行评估，以便正式对外公布性能参数^[2-6]。最简单的方式就是将接收机放置在已知点上，采集数据计算该点的坐标，并将计算出的坐标跟已知点坐标做比较，生成误差序列数据，然后对这个误差序列数据进行统计^[7-9]。统计指标包括均方根值 (RMS)、平均值、95%分位数等指标。其中，RMS和平均值按照公式计算即可，95%分位数比较复杂，需要对误差序列数据取绝对值，然后按照从小到大顺序排列，最后将95%处的数据选为95%分位数，排序是主要问题。

针对排序问题，一般思路是：将数据导入到内存中，进行数据排序，将数据存入文件。但是对北斗定位性能评估存在严重问题。该评估需要大量测站的长期观测数据。假如全国有10个测站在进行连续观测，采样率是1 Hz，连续观测一年时间，需要评估的类型有单频、双频等10类，使用的是double类型的数据，那么这些数据如果全部导入内存后，占用的空间为10×10×365×86 400×8 Byte=23.5 GB，对于32位系统的普通计算机，访问2 G以上的内存非常困难，并且一般设备也没有这么大的物理内存，为了评估一个指标使用大型计算机，从经济上不现实。

随着北斗卫星导航系统的建设，观测站增多，数据量也飞速增加，读取存储在磁盘中的海量误差序列数据文件非常耗费时间，算法上应尽量设计仅读取一遍误差序列数据。

1 常用排序算法

常用的排序算法有很多种，各种算法都有自己的优缺点，下面选取几种有代表性的阐述排序算法的基本思路。

1) 插入排序。以直接插入排序为例，将数据与有序表 (长度为n) 中的数据比较后插入到其位置，使之保持有序，生成新的有序表 (长度为n+1)。

从该算法的描述可以看出，需要将所有数据读入内存进行比较，消耗巨大的内存。如果不将数据读入内存，将数据存储在磁盘文件中，需要反复将有序表写入文件，然后读取文件，操作文件的次数与误差序列数据的个数是一样的，其读写文件操作耗费的时间惊人。

2) 交换排序。将较大的数据向序列的后部移动, 较小的数据向前移动。以冒泡法排序为例，该算法同样需要将数据读入内存中，算法复杂度较高，为O(n²)。

3) bit位排序^[10]。这是一种经典的排序算法，将待排序序列中的数据对应的bit置为1。该算法存储空间较小，效率非常高，但是该算法要求待排序序列中不能有重复的情况。北斗定位误差序列无法满足这个要求。

4) 计数排序。对于给定的输入序列中的每一个元素x，确定值小于x的元素的个数。将x直接存放到最终的输出序列的正确位置上。对北斗定位误差序列百分数求取中，该算法需要对所有元素求取一次位置，计算时间较长。

此外还有并行排序、合并排序、分配排序和使用数据库等方法，这些方法要么占用内存大，要么需要反复读取文件，造成计算时间较长等问题，完全无法适应北斗定位性能评估中的海量数据问题。

2 计数器排序算法 2.1 算法基本思路

以平面定位误差统计为例，统计95%的第N个数的计算公式为：

$ N = {\rm{INT}}\left( {0.95 \times {\rm{COUNT}}} \right) $

(1)

式中，INT表示取整；COUNT表示误差序列中数据的个数。

研究误差序列的特点可以发现，误差序列都是正数 (因为取绝对值)，总体上都是有概略上限的，如北斗卫星导航系统的平面定位误差一般都小于1 000 m，可以根据这两个特点来设计排序算法。

排序算法的基本思路如图 1所示，图 1表示只有正向的半坐标轴，误差序列都落在该半坐标轴上。d₀表示坐标原点0，d_n表示误差数据序列概略上限，将区间[d₀, d_n]均分成n份，对应节点分别标注成d_i，i=1, 2, …, n，半坐标轴被划分成了n个封闭区间[d_i, d_i+1]和1个半开区间 (d_n, +∞)。图上黑点表示误差序列中的数据，根据定义所有黑点都会落在某一个区间，每一个区间定义一个计数器。然后逐一判断误差序列数据中的每一个数据落在哪一个区间，对应的计数器加1。最后根据计数器记录的个数确定95%的数据位于哪一个区间，并取该区间的中间数作为95%的值，写成伪代码。

由于95%的值一定位于计算的区间内，所以该算法计算的最大误差ε是半个区间的大小为：

$ \varepsilon = \left( {{d_{i + 1}} - {d_i}} \right)/2 $

(2)

需要说明的是，95%的值不能位于第n+1个区间，即半开区间[d_n, +∞)，所以在设计误差序列概略上限时，应尽量设计准确。此外，由于95%是一个输入参数，所以可以较容易地改为50%、68%等，所以上面方法同时也可以解决中位数、其他分位数 (如68%) 等问题。

2.2 算法特点

关于计数器排序方法的特点总结如下：

1) 占用内存空间极少。以引言中的假设为例，以1 cm为区间大小，概略上限为1 000 m，那么将分为100 000个区间，针对10种测试类型数据，其占用的内存空间为100 001×10×8 Byte=7.6 MB，7.6 MB的内存对于普通计算机而言微不足道，相对于原先的23.5 GB下降剧烈。

如果考虑北斗定位精度的实际情况，将概略上限设为50 m，以1 dm为区间大小，那么占用的内存空间仅仅为501×10×8 Byte=39.1 kB。

2) 精度损失完全可以忽略。根据算法精度评估公式，对于上面的1 cm区间大小，其统计误差小于0.5 cm，这对于北斗卫星导航系统定位精度评估来讲是完全可以忽略的。

3) 仅需读取原始文件一次。根据算法描述，仅仅需要读取存储误差序列数据的原始数据文件一次就可以了，这是所有算法中的最低要求，因为无论什么排序算法，都需要至少读取一次原始数据文件。

4) 算法损失精度和区间灵活可变。上面算法阐述中，算法设计时将区间平均分配，如果知道误差序列的先验信息，可以按照误差序列数据特点进行设计，比如，在误差序列数据密集的位置多设置区间，在数据稀疏的地方减少区间设置个数。

3 实验分析

为验证计数器排序法的效果，选取3组数据进行计算，分别为北京站和喀什站的静态数据和郑州地区跑车实验的动态数据。平面定位误差序列的概略上限设为20 m，区间宽度设为1 cm。3组数据的平面定位误差序列图如图 2(a)、图 3(a)和图 4(a)所示，区间计数器计数柱状图如图 2(b)、图 3(b)和图 4(b)所示。柱状图显示了各个区间上的数据个数。

利用计数器排序法计算得到的分位数与真实的分位数的误差如表 1所示，无论是98%、68%还是50%分位数，误差都在5 mm以内，这对于北斗卫星导航系统的精度而言完全可以忽略不计。

3组数据不同方法占用的内存比较如图 5所示。很明显，计数器法占用的内存要少于传统方法，而且计数器法不会随着数据量的变大而变化。

由于测试数据量较少，仅为2~4 h的时间，下面比较在测试时间较长情况下的内存差异。如图 6所示，以10个测站为例。传统方法的内存大小随着数据量的变大而变大，当数据量累积到100 d时，内存大小已经达到将近7 G大小，这是无法接受的。与之形成鲜明对比的是，计数器法的内存一直不变，保持在150 kB左右。这说明计数器排序法能够较好地求取不同的分位数，且内存占用量并没有变大。

4 结束语

本文针对北斗卫星导航系统定位精度评估中遇到的排序问题，充分利用误差序列数据有概略上限的特点，提出了计数器排序算法。计数器排序算法将坐标轴划分为n个封闭区间和1个半开区间，并判断误差序列数据隶属的区间，同时利用对应的计数器计数。计数器排序算法具有占用内存空间极少，精度损失可以完全忽略，读取原始文件仅需一次，算法损失精度和区间灵活可变的特点，解决性能评估中的求解95%分位数的问题。由于95%是一个输入参数，所以可以较易改为50%、68%等，同时也可以解决中位数、其他分位数等问题。