• 文章
  • 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