• 文章
  • Borland C++ 排序算法
由 发布
2014 年 7 月 7 日（最后更新：2014 年 7 月 7 日）

Borland C++ 排序算法

评分：4.3/5（110 票）
*****
引言

您是否曾经对那些对大量项目进行排序的软件程序感到好奇？我们在日常的计算机任务中理所当然地使用它们，但究竟是什么让它们发挥作用呢？许多软件包都实现了自己的算法来处理这项工作。我开发了一种自己的方法来处理这项重要的任务，我将在本文中详细解释它是如何工作的。

我的问题概述

1996 年，我使用过程式 C 编程为一个客户开发一个库存系统，用于排序大量项目——大约 8,000 到 10,000 个。当时我使用的排序程序是我在 20 世纪 90 年代初创建的，只能排序多达 1,500 个项目。这个 Borland C 字母排序代码列在我的网站上。

在 20 世纪 90 年代中期，大多数基于 IBM PC 的计算机运行的是 Intel 486、Intel Pentium、AMD K-5 等。然而，它们的性能以及当时的硬盘似乎都需要费力才能处理像我的应用程序所需的如此大规模的排序任务。我不得不从我 20 世纪 90 年代初的过程式 C 排序代码背后的基本 编程思路开始，并想办法扩展它，以便它可以处理更大的数据文件。如果我尝试设计新的排序程序，使其大部分工作都在机械硬盘上完成，那将引发新的问题。尝试在磁盘上排序大型数据文件会因为硬盘机械移动部件的缓慢而导致速度大幅下降。客户肯定会反对速度变慢，我将被打回原形，从更可接受的东西开始。

对于大型数据文件来说，显然在硬盘上执行排序是行不通的。我想到的唯一其他选择是在内存中进行大部分工作。通过将数据处理集中在内存中，我可以避开机械硬盘的缓慢世界，并获得更快的速度。这一点尤其重要，因为当时的处理能力较低。将工作转移到内存中的另一个重要原因是，在磁盘上进行大量工作可能会因为磁盘上存在任意数量的扇区错误而导致灾难性问题。这会给排序过程带来麻烦，并导致输出文件损坏。当然，在内存中集中工作也可能发生这种情况，但发生的可能性较小。

向前推进

我将很快开始讨论我的算法如何工作的“细节”。这个用于排序作业的新且改进的字母排序代码后来被改编到 Borland C++ 中，我包含了代码片段以及图表来帮助说明逻辑流程。请注意，一些 C++ 变量被称为“非持久”变量，而“top”和“bott”变量被称为“持久”变量。这是因为“非持久”变量在处理过程中会被完全重置为新值，而“持久”变量在不同时间会被递增或递减，但永远不会重置。此外，您会注意到我将我使用的各种数据结构称为“grid”、“name”和“stor”，它们是常规数据结构。它们根据我使用的内存小型模式，在 64K 数据段的边界内分配。这是为了区分它们与远内存数据结构“s”、“s1”和“s2”。该算法是在二进制固定宽度文本文件上执行的。我在我的 应用程序开发中使用它们，因为它们易于处理。该算法也可以轻松调整以处理二进制可变宽度（分隔符）文本文件。

主要目标：更大的排序容量

现在我已经决定将大部分处理集中在内存中，我必须找到一种方法来实现它，以便它可以为大量项目分配容量。在 Borland C/C++ 中，有 6 种内存模式可供选择：tiny、small、medium、compact、large 和 huge。我一直使用 small 内存模式，因为它是默认模式，而且我从 1990 年开始接触 C 编程以来就习惯于处理它。在 small 内存模式下，代码和数据段各有 64K 的可用内存。为了对大量项目进行排序，我需要比 64K 数据段大得多的内存空间，该数据段还必须包含各种其他数据结构。

我决定使用堆的远端，或者称为“远内存”。要进行设置，我首先包含了一个必要的 C++ 头文件，用于分配远内存。

1
2
3
4
 

// alloc.h is needed for far memory data structures.
#include <alloc.h>


然后，我在排序代码的开头附近声明了 3 个远内存指针，如下所示。

1
2
3
4
5
6
 

// declare far memory pointers.
unsigned long int far *s;
unsigned long int far *s1;
unsigned long int far *s2;


我分配了它们，以便处理多达 16,000 个项目。

1
2
3
4
5
6
 

// allocate far memory.
s = ( unsigned long int far * ) farmalloc(65000L);
s1 = ( unsigned long int far * ) farmalloc(65000L);
s2 = ( unsigned long int far * ) farmalloc(65000L);


我设置 3 个远内存数据结构的原因是，它们都需要用来处理使用我创建的新排序算法的数据。这给了我处理多达 16,000 个项目的空间。我可以分配更多数据记录，但这足以完成手头的工作。

为数据文件中的每个项目分配数值权重

处理过程首先将数学公式应用于二进制固定宽度文本文件中的每个项目的开头的四个字符。考虑以下“10”的数值序列。

10,000,000 1,000,000 100,000 10,000 1,000 100 10 1

接下来，从上述数值序列中删除以下“10”的幂。

1,000,000
10,000
100
10

更新后的数值序列中剩下这些“10”的幂。

10,000,000 100,000 1,000 1

给定项目中的每个字符的 ASCII 码范围为 32 到 126。每个 ASCII 码都被“映射”到 0 到 94 范围内的数值。从给定项目开头算起的每个前四个字符的数值将从左到右乘以更新后的数值序列。

这是我在编程中用于为每个项目分配数值权重的数学公式。

（10,000,000 X 第 1 个字符的数值）+
（100,000 X 第 2 个字符的数值）+
（1,000 X 第 3 个字符的数值）+
（1 X 第 4 个字符的数值）

这个数量等于该项目的数值权重。考虑以下示例：

“SMITHSON”

“S” = 第 1 个字符
“M” = 第 2 个字符
“I” = 第 3 个字符
“T” = 第 4 个字符
“H” = 第 5 个字符
“S” = 第 6 个字符
“O” = 第 7 个字符
“N” = 第 8 个字符

第 1 个字符 S 的 ASCII 码为 83，根据算法对应数值 51。
第 2 个字符 M 的 ASCII 码为 77，根据算法对应数值 45。
第 3 个字符 I 的 ASCII 码为 73，根据算法对应数值 41。
第 4 个字符 T 的 ASCII 码为 84，根据算法对应数值 52。

现在，让我们将此示例中的数值代入数学公式，得出上述项目的数值权重。

（10,000,000 X 51）+（100,000 X 45）+（1,000 X 41）+（1 X 52）= 514,541,052

这个数学公式是我自己想出来的，我认为它是一个为每个项目分配数值权重的不错方法。这是程序中执行此任务的代码的片段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 

.
.
.
.
.
// open the data file "job_part.txt" for initial processing.
infile.open("job_part.txt", ios::in | ios::binary);      
inn = infile.rdbuf();                                 

// initialize far memory data structure position variables.
// "top" is the first sequential item and “bott” is number
// of items less 1, or the last sequential item. "top" and
// "bott" are what i call persistent item markers in the far
// memory data structures. this is because they are never reset
// to their original values during the entire processing sequence.
// “top” is incremented and “bott” is decremented during processing
// to assist in facilitating the overall sorting.
top = 0;                  
bott = number_of_items - 1;       
// initialize the record counter variable, “aa”.      
aa = 0;                     

	// <----- start of processing loop "a".

	// this will calculate the highest and lowest numerical weights
	// for all items.
	do {                      

		// <----- start of processing loop "b".

		// this will generate numerical weights for the items. get a
		// character from the current file pointer position and prepare
		// for further processing.
		inn -> seekpos(fileoffset, ios::in);
		first_four_numbers = 0;
		do {                      
		// convert the character to uppercase for subsequent comparison.
		kh = infile.readByte();      
		khchar[0] = kh;             
		strupr(khchar);           
		kh = khchar[0];
		// assign numerical value range of 0 to 94 to variable “var1”
		// that i have mapped to the ascii character code range of 32 to 126.
		if( kh <= 32 ) var1 = 0;
		if( kh == 33 ) var1 = 1;
		if( kh == 34 ) var1 = 2;
		if( kh == 35 ) var1 = 3;
		if( kh == 36 ) var1 = 4;
		if( kh == 37 ) var1 = 5;
		if( kh == 38 ) var1 = 6;		.
.
.
.
.
		if( kh == 119 ) var1 = 87;
		if( kh == 120 ) var1 = 88;
		if( kh == 121 ) var1 = 89;
		if( kh == 122 ) var1 = 90;
		if( kh == 123 ) var1 = 91;
		if( kh == 124 ) var1 = 92;
		if( kh == 125 ) var1 = 93;
		if( kh == 126 ) var1 = 94;
			// multiply the numeric variable "var1" for first character
			// of item by 10,000,000 and add to total for this item in
			// far memory data structure "s".
			if( first_four_numbers == 0 ) *(s+aa) = *(s+aa) + ( var1 * 10000000 );    
				// multiply the numeric variable "var1" for second character
				// of item by 100,000 and add to total for this item in far
				// memory data structure "s".
				if( first_four_numbers == 1 ) *(s+aa) = *(s+aa) + ( var1 * 100000 );      
					// multiply the numeric variable "var1" for third character
					// of item by 1,000 and add to total for this item in far
					// memory data structure "s".
					if( first_four_numbers == 2 ) *(s+aa) = *(s+aa) + ( var1 * 1000 );        
						// multiply the numeric variable "var1" for fourth character
						// of item by 1 and add to total for this item in far memory
						// data structure "s".
						if( first_four_numbers == 3 ) *(s+aa) = *(s+aa) + ( var1 * 1 );           
                                                     
			// ( first item character numerical value X 10,000,000 ) + 
			// ( second item character numerical value X 100,000 ) + 
			// ( third item character numerical value X 1,000 ) + 
			// ( fourth item character numerical value X 1 ) = numerical 
			// weighted value for the item. this accumulated numerical
			// value is stored in far memory data structure "s" for the
			// corresponding item's sequential position in the data file.

					// the first 4 characters of each item are subjected to the
					// above math formula. they are given a numerical weighting,
					// which will later be used to segment the actual sorting process
					// into "top1" and "bott1" processing regions. in other words,
					// the sorting process is performed in a compartmentalized fashion.

		// <----- end of processing loop "b".

		first_four_numbers++;
		} while( first_four_numbers < 4 );                                      

// as we are moving from the top to the bottom of the data
// file, keep track of the lowest primary and highest primary
// accumulated numerical values as they are stored in far memory
// data structure "s". the value extremes (highest and lowest)
// are assigned to the primary high “up1” and primary low “low1”
// variables, respectively.                                                     
if( aa == 0 ) {                                        
low1 = *(s+aa);                                     
up1 = *(s+aa);                                   
}
if( *(s+aa) < low1 ) low1 = *(s+aa);               
if( *(s+aa) > up1 ) up1 = *(s+aa);                 
                                                     
	// move to next record of the data file "job_part.txt". the constant
	// record length in this case is “RECORDLENGTH” and fixed field width (SDF format).                                                 
	aa++;
	fileoffset = fileoffset + RECORDLENGTH;                      

	// <----- end of processing loop "a".

	} while( aa < number_of_items );

infile.close();                                     
.
.
.
.
.


在将此数学公式应用于数据文件中的所有项目后，就可以知道最低和最高的数值权重了。所有数值权重都将存储在远内存数据结构“s”的相应位置，这些位置与其在未排序数据文件中的顺序位置相对应（参见图 1）。




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 

.
.
.
.
.
// if the lowest primary “low1” and highest primary “up1” variables are not equal,
// meaning there are records to be sorted, then proceed with processing.
if ( low1 != up1 ) {      

	// initialize high "main" processing loop exit variable "qqq" to stay within
	// the processing loop.                            
	qqq = 0;                    
	// initialize low "main" processing loop exit variable "sss" to stay within
	// the processing loop.
	sss = 0;                    

		// <----- start of “main” processing loop.

		// the "main" processing loop will redefine "top1" and "bott1" pairs of
		// processing regions until all items are sorted.
		do {                      
                            
		// assign primary high variable "up1" to secondary low variable "low2".
		low2 = up1;               
		// assign primary low variable "low1" to secondary high variable "up2".
		up2 = low1;               

		// the loop that follows will set boundaries and numerical values for
		// processing regions "top1" and "bott1". each of these processing regions
		// can handle up to 150 items with the same numerical weighting as calculated
		// above on the first 4 characters of the item. i need to mention that there
		// is a highly unlikely possibility that the algorithm could malfunction if a
		// specific numerical weight that has been assigned to a "top1" or "bott1"
		// processing region exceeds 150 items. this is because it would exceed the row
		// depth of the 2 dimensional “grid” conventional data structure which is heavily
		// used for sorting and insertion operations in the "top1" and "bott1" processing
		// regions. i have used this algorithm in many of my programs and have never seen
		// this happen. 

		// initialize item loop counting variable "ii" to 0.
		ii = 0;                     
		// initialize upper processing region "top1" non-persistent processing region.
		top1 = 0;                   
		// initialize lower processing region "bott1" non-persistent processing region.
		bott1 = 0;                  
		// initialize the start of upper processing region "start" non-persistent item
		// marker with "top" persistent item marker.
		start = top;                
		// initialize the start of lower processing region "finish" non-persistent item
		// marker with "bott" persistent item marker.                            
		finish = bott;              

			// <----- start of processing loop "c".                            

			do {                      

				// if the numerically weighted value for the given item in far memory data
				// structure “s” for index “ii” is equal to the lowest primary variable
				// “low1” and the high “main” processing loop exit variable “qqq” is set to
				// stay within the “main” processing loop, then assign the sequential file
				// position value for the given item “ii” to far memory data structure “s1”
				// in the array position denoted by the “top” persistent item marker.
				if( *(s+ii) == low1 && qqq == 0 ) {     
				*(s1+top) = ii;                      
				// next, increment the “top” persistent item marker and “top1” non-persistent
				// item marker by 1 each.
				top++;                               
				top1++;                              
				}

				// if the numerically weighted value for the given item in far memory data
				// structure “s” for index “ii” is equal to the highest primary variable “up1”
				// and the low “main” processing loop exit variable “sss” is set to stay within
				// the processing loop, then assign the sequential numerical file position value
				// for the given item “ii” to far memory data structure “s1” in the array position
				// denoted by “bott” persistent item marker.
				if( *(s+ii) == up1 && sss == 0 ) {    
				*(s1+bott) = ii;                     
				// next, decrement the “bott” persistent item marker and increment “bott1” non-persistent
				// item marker by 1 each.                                       
				bott--;                                
				bott1++;                              
				}

				// if the numerically weighted value for the given item in far memory data structure “s”
				// is greater than the lowest primary variable “low1” and is less than the lowest secondary
				// variable “low2”, then assign numerically weighted value for the given item for index “ii”
				// in far memory data structure “s” to the lowest secondary variable “low2”.
				if( *(s+ii) > low1 && *(s+ii) < low2 ) low2 = *(s+ii);    
                                                                
				// if the numerically weighted value for the given item in far memory data structure “s” is
				// less than the highest primary variable “up1” and is greater than the highest secondary
				// variable “up2”, then assign numerically weighted value for the given item for index “ii”
				// in far memory data structure “s” to the highest secondary variable “up2”.                                                               
				if( *(s+ii) < up1 && *(s+ii) > up2 ) up2 = *(s+ii);      
                                                                
			// increment item counting variable "ii" by 1 and loop sequentially through the data file until
			// the item counting variable is at the end. this looping routine will set the records of the
			// same numerically weighted value to be processed for sorting in processing region "top1" and
			// the same for processing region "bott1". the “start” non-persistent item marker is the beginning
			// of the “top1” processing region and “start+top1” is the end. the “finish” non-persistent item
			// marker is the end of the “bott1” processing region and “finish-bott1+1” is the beginning. 

			// <----- end of processing loop "c".                                                                

			ii++;                    
			} while( ii < number_of_items );           
                           
					// first, set the variable “r” equal to 0. if the secondary low variable “low2” and the
					// secondary high variable “up2” are equal and the low "main" processing loop exit variable
					// “sss” is set to stay within the "main" processing loop, then set the low "main" processing
					// loop exit variable “sss” to attempt to exit the "main" processing loop. also, set the
					// variable “r” equal to 1 so the very next logic structure will not be evaluated.
					r = 0;
					if( low2 == up2 && sss == 0 ) {     
					sss = 1;                            
					r = 1;
					}

					// if the variable “r” is still set to 0, then evaluate the next logic structure which is
					// described as follows. if the secondary low variable “low2” and the secondary high
					// variable “up2” are equal and the low "main" processing loop exit variable “sss” is set
					// to attempt to exit the "main" processing loop, then set the high "main" processing loop
					// exit variable “qqq” to attempt to exit the "main" processing loop.
					if( low2 == up2 && r == 0 && sss == 1 ) qqq = 1;        
                                                      
					// if the secondary low numerically weighted variable “low2” is greater than the secondary
					// high numerically weighted variable “up2”, then set the low "main" processing loop exit
					// variable “sss” and the high "main" processing loop exit variable “qqq” to both exit the
					// "main" processing loop, which will cease the redefinition of successive “top1” and “bott1”
					// processing regions.
					if( low2 > up2 ) {             
					qqq = 1;                       
					sss = 1;
					}

					// next, assign secondary low weighted variable “low2” to primary low weighted variable “low1”.
					low1 = low2;                 
					// next, assign secondary high weighted variable “up2” to primary high weighted variable “up1”.
					up1 = up2;                   
					.
					.
					.
					.
					.


在上面的代码块中，首先要检查最低和最高数值权重是否相等。这会将第一个主变量“low1”与最高主变量“up1”进行比较。如果它们相等，则处理将中止，因为所有项目将具有相同的数值权重。这意味着所有项目的开头的 4 个字符都相同。这种情况非常罕见，因为它们几乎已经排序好了，遇到这样的数据文件的可能性非常小。最终，要排序的原始数据文件将保持不变，并且不会在最后被重建。如果它们不相等，第一个主变量“low1”和最高主变量“up1”将代表两组不同的数值加权项，因此处理将继续进行“主”处理循环的启动。

两个远内存处理区域的故事：“TOP1”和“BOTT1”

程序围绕一个“do-while 循环”运行，我称之为“主”处理循环。我使用 2 个远内存区域来促进排序过程，我称之为“top1”和“bott1”处理区域。每次通过“主”处理循环，这两个区域都会被反复重新定义。这就是驱动排序过程的“分段机制”。

这两个处理区域实际上都以数值变量开始。它们后来演变成处理区域。首先，它们都被初始化为 0。然后，“top1”会为远内存数据结构“s”中对应最低主变量“low1”（当前最低数值权重）的每个项目递增 1。接下来，“bott1”会为远内存数据结构“s”中对应最高主变量“up1”（当前最高数值权重）的每个项目递增 1。这在上面的代码中完成。此外，“主”处理循环退出变量“qqq”和“sss”在两个处理区域都需要重新定义来处理未排序的项目时，不能设置为退出“主”处理循环。换句话说，“qqq”必须设置为 0，这样“top1”才能将其正在定义的处理区域中的当前最低数值权重包括在内。并且“sss”必须设置为 0，这样“bott1”才能将其正在定义的处理区域中的当前最高数值权重包括在内。

在之前的代码中还要注意的一点是我用来表示项目的两个标记：“start”和“finish”。“start”被赋值为“top”中的值，而“finish”被赋值为“bott”中的值。“start”是一个“非持久”项目标记，用于表示“top1”处理区域的项目计数或深度。“finish”是一个“非持久”项目标记，用于表示“bott1”处理区域的项目计数或深度。“top”和“bott”都是“持久”项目标记，它们与“top1”和“bott1”一起递增。（参见图 7 和图 8，以了解“top1”和“bott1”处理区域的视觉表示。）




重新定义过程完成后，“top1”处理区域将包含对应于当前最低数值的项目的区域。对于“bott1”处理区域也是如此，但其数值对应于当前最高的数值。“top1”和“bott1”处理区域将用于实际的排序过程，我在本文中不深入探讨具体细节。要了解更多信息，您可以参考文章开头的“改进的字母排序代码”超链接。排序完成后，程序将围绕“主”处理循环循环，然后继续重新定义新的“top1”和“bott1”处理区域。（参见图 2）。




这两个处理区域将在空间上彼此靠近，随着它们从“主”处理循环的每次传递中重新定义，它们会向远内存数据结构“s”的中心移动。每个新的“top1”处理区域的数值将高于其前一个“top1”区域。每个新的“bott1”处理区域的数值将低于其前一个“bott1”区域。请参考图 3、4、5 和 6，以直观地说明算法的进展，因为 successive “top1” 和 “bott1” 处理区域在每次通过“主”处理循环时都会被重新定义。







注意图 6 中，当 successive “top1” 和 “bott1” 处理区域的处理到达远内存数据结构“s”的中间时会发生什么。“top1”处理区域中最低数值最小的区域与“bott1”处理区域中最高数值最小的区域相邻。此时处理将停止，因为没有更多要排序的项目了。“主”处理循环将退出，然后将排序后的新项目位置数组存储在远内存数据结构“s1”中，并写入新数据文件。（参见图 9 和图 10）。







在这里，我想谈谈“主”处理循环可能在数据写回新排序数据文件之前退出的方式。随着处理在中途的远内存数据结构“s”中接近尾声，它不一定以偶数对的最终“top1”和“bott1”处理区域结束。它也可以通过“top1”或“bott1”处理区域之一将其“主”处理循环退出变量设置为尝试退出“主”处理循环来接近完成。更具体地说，“top1”处理区域可以将其“主”循环退出变量“qqq”设置为 1，这意味着没有更多的“top1”区域可以重新定义。“bott1”处理区域可以将其“主”循环退出变量“sss”设置为 0，这意味着还有一个“bott1”区域可以重新定义和排序。反之亦然。

一个可能有助于阐明逻辑流程的比喻

我知道这个叙述可能对一些读者来说很难理解，我想引用一段美国历史来帮助大家更好地理解我的算法是如何工作的。

在 19 世纪后期，美国将注意力转向了国家建设。通过连接北美大陆东西海岸的横贯大陆铁路成为国家优先事项。这是美国第一条横贯大陆铁路的开始。

两大铁路公司，联合太平洋铁路公司和中央太平洋铁路公司，牵头完成了这项雄心勃勃而艰巨的任务。中央太平洋铁路公司从加利福尼亚州萨克拉门托向东修建铁路，而联合太平洋铁路公司则从内布拉斯加州奥马哈向西修建。

东西两端的两个团队都孜孜不倦地工作了七年。1868 年 4 月 28 日，联合太平洋铁路公司的建筑工队（由华工和爱尔兰工人组成）在一天内铺设了十英里长的铁轨，这是因为他们打赌 10,000 美元可以做到。1869 年 5 月 10 日，工程在犹他州普罗蒙特里角完工。联合太平洋铁路公司的 119 号机车和中央太平洋铁路公司的 60 号朱庇特号机车面对面停靠，中间只隔着一根枕木的宽度。在金钉仪式上，三枚钉子被钉入连接两段铁路：一枚金钉、一枚银钉和一枚金银铁混合钉。美国东西海岸之间的旅行时间从 4 到 6 个月缩短到仅 6 天的火车旅行！

现在，当您仔细思考时，我的算法的进展与美国第一条横贯大陆铁路的建设非常相似。随着算法的进行，它开始类似于两支工作队伍逐渐向分配的远内存空间的中间部分推进，这就像一片等待“排序建筑劳工”到达的长区域。 “top1”和“bott1”处理区域就像“两支建筑队伍”，它们开始在分配的内存空间的相对两端进行“排序工作”。它们各自努力对具有相同数值的项进行排序，如前所述，同时不断地彼此靠近。程序循环经过“主”处理循环并定义了新的“top1”和“bott1”处理区域后，过程会重复。最后，“金钉仪式”发生在“top1”和“bott1”处理区域彼此相邻时，位于分配的远内存段的中间附近——如果我可以用犹他州普罗蒙特里角来比喻，希望大家能更好地理解我的算法。

一个潜在问题和解决方案

在这里，我想详细介绍我的算法的一个潜在问题以及一个建议的解决方案。二维“grid”常规数据结构广泛用于“top1”和“bott1”处理区域中的项目操作。它被设计为容纳多达 150 个具有相同数值的项。您需要注意二维“grid”常规数据结构提供的行深度，以便它和其他常规数据结构结合起来不会超出所使用的 small 内存模式的 64K 数据段。如果“top1”或“bott1”处理区域中的项目超过 150 个，就会出现问题。算法不会中止或发生故障，而是只会包含处理区域中的前 150 个项目。我从未真正尝试解决这个潜在的失误，因为它发生的可能性非常小。要触发这个故障，需要有超过 150 个“Smith”或“Jones”。这可能会在选民登记验证数据文件中发生，该文件可能包含大量同姓氏。

一个好的纠正方法是声明第四个远内存数据结构，其大小与前三个相同。它将替换并执行二维“grid”常规数据结构的作用，但它将始终足够大，可以容纳特定数值的所有项目。这是因为它将被分配来容纳整个数据文件中的项目数量。

拒绝冗余、浪费速度的代码

现在，你们中的许多人可能想知道该算法的速度。我用一个包含 10,959 个零件号的二进制固定记录宽度文本文件对其进行了测试。在 Gateway Pentium 4 塔式 CPU 上，使用旧的 6 GB Quantum Bigfoot 硬盘，处理花费了略多于 3 秒钟。当在具有 2.4 GHz AMD V160 处理器的 Dell M5030 笔记本电脑上运行时，大约花费了 1 秒钟。在“do-while”循环处理中有一些区域可以重新设计或消除，这应该会进一步提高处理速度，因为达到相同结果所需的工作量更少。在 1996 年完成这项工作后，它似乎在合理的时间内工作，所以我没有回去尝试进一步优化它。在这里，我将通过选择一些代码区域来详细说明，这些区域可以进行改进以获得更高的处理速度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 

	.
	.
	.
	.
	.	
		// convert the character to uppercase for subsequent comparison.
		kh = infile.readByte();      
		khchar[0] = kh;             
		strupr(khchar);           
		kh = khchar[0];
		// assign numerical value range of 0 to 94 to variable “var1”
		// that i have mapped to the ascii character code range of 32 to 126.
		if( kh <= 32 ) var1 = 0;
		if( kh == 33 ) var1 = 1;
		if( kh == 34 ) var1 = 2;
		if( kh == 35 ) var1 = 3;
		if( kh == 36 ) var1 = 4;
		if( kh == 37 ) var1 = 5;
		if( kh == 38 ) var1 = 6;
		.
.
.
.
.
		if( kh == 119 ) var1 = 87;
		if( kh == 120 ) var1 = 88;
		if( kh == 121 ) var1 = 89;
		if( kh == 122 ) var1 = 90;
		if( kh == 123 ) var1 = 91;
		if( kh == 124 ) var1 = 92;
		if( kh == 125 ) var1 = 93;
		if( kh == 126 ) var1 = 94;
	.
	.
	.
	.
	.


这段测试 ASCII 字符 32 到 126 的代码可以用 C++ 函数“atoi()”替换。它将消除许多重复的条件“if-then”逻辑结构比较，并将字符转换为整数。然后可以使用这个新的整数值来计算每个项目数值权重的数学公式。这里是另一个可以提高速度的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 

	.
	.
	.
	.
	.
		// set processing loop “2” counter variable “ii” to the non-persistent "start" item
		// marker denoting the beginning of the "top1" processing region.
		ii = start;           
       
		// <----- start of processing loop "2".                               

		do {                       

		// retrieve and calculate file stream position offset of the item for processing loop
		// “2” counter "ii" in the far memory data structure “s1”.
		far_memory_contents_2 = *(s1+ii);               
		far_memory_contents_2 = far_memory_contents_2 * RECORDLENGTH;    
                                 
		// use calculated file stream position offset "far_memory_contents_2" to retrieve all
		// characters of the item except the first 4 characters into the "name" conventional
		// data structure. compare this to the 2 dimensional "grid" conventional data structure
		// set at lower index counter "lowx". if they are equal and high processing loop “1”
		// exit variable "qqqx" is set to stay within processing loop "1", then assign the
		// sequential item position in far memory data structure "s1" for	 processing loop “2”
		// counter variable “ii” to far memory data structure "s2" for non-persistent index
		// marker "topx". next, increment non-persistent index marker "topx" by 1.
		r = 0;
		inn -> seekpos(far_memory_contents_2 + 4, ios::in);                          
		for(v = 0; v < FIELDLENGTH - 4; v++) name[v] = infile.readByte();  
		strupr(name);                                             
                                                            
		for(v = 0; v < FIELDLENGTH - 4; v++) {                          
		if( name[v] != grid[v][lowx] ) r = 1;                           
		}                                                         
                                                            
		if( r == 0 && qqqx == 0 ) {                                 
		*(s2+topx) = *(s1+ii);                                    
		topx++;
		}

		// retrieve and calculate file stream position offset of the item for processing loop
		// “2” counter "ii" in the far memory data structure “s1”.
		far_memory_contents_2 = *(s1+ii);              
		far_memory_contents_2 = far_memory_contents_2 * RECORDLENGTH;   
                                
		// use calculated file stream position offset "far_memory_contents_2" to retrieve all
		// characters of the item except the first 4 characters into the "name" conventional
		// data structure. compare this to the 2 dimensional "grid" conventional data structure
		// set at higher index counter "upx". if they are equal and low processing loop “1” exit
		// variable "sssx" is set to stay within processing loop "1", then assign the sequential
		// item position in far memory data structure "s1" for processing loop “2” counter variable
		// “ii” to far memory data structure "s2" for non-persistent index marker "bottx". next,
		// decrement non-persistent index marker "bottx" by 1.
		r = 0;
		inn -> seekpos(far_memory_contents_2 + 4, ios::in);                          
		for(v = 0; v < FIELDLENGTH - 4; v++) name[v] = infile.readByte();  
		strupr(name);                                             
                                                            
		for(v = 0; v < FIELDLENGTH - 4; v++) {                          
		if( name[v] != grid[v][upx] ) r = 1;                            
		}                                                         
                                                            
		if( r == 0 && sssx == 0 ) {                                 
		*(s2+bottx) = *(s1+ii);                                   
		bottx--;
		}

		// increment processing loop “2” counter variable “ii” by 1. processing loop “2” counter
		// variable “ii” cycles through the non-persistent "start+top1" depth for the "top1"
		// processing region.
		ii++;                              

		// <----- end of processing loop "2".

		} while( ii < start + top1 );            	.
	.
	.
	,
	.


在代码的“top1”和“bott1”处理部分，有一个由处理循环“2”包围的代码块。有两个地方计算了两次“far_memory_contents_2”文件流位置偏移量。然后它被用于将数据检索到“name”常规数据结构中，以便在二维“grid”常规数据结构的两个不同行中进行比较操作。它只需要计算一次就可以达到相同的结果。事实上，“name”常规数据结构只需要在每个处理循环“2”循环中检索一次数据，而不是两次。

结论

我已将此排序算法用于许多 C++ 应用程序中，通常用于对要预览为报告的零件号或客户名称进行排序。它已被证明是可靠且快速的。我也将其改编用于对数字和日期进行排序。如果您想了解更多关于我的 开发人员技能，请访问我的 软件开发人员网站。此外，请务必查看我的 计算机维修服务和我的 “修复我的电脑” 技术提示。


参考文献

http://www (dot) accelerationwatch (dot) com/promontorypoint (dot) html

http://en (dot) wikipedia (dot) org/wiki/Promontory,_Utah

http://www (dot) history (dot) com/topics/transcontinental-railroad