严蔚敏 数据结构第十章 内部排序的具体代码(c++,附测试数据)（Yan Yumin data structure of the tenth chapter of the internal sorting of the specific code (c++, attached to test data)）.doc

严蔚敏 数据结构第十章 内部排序的具体代码(c++,附测试数据)（Yan Yumin data structure of the tenth chapter of the internal sorting of the specific code (c++, attached to test data)） Test data: / * generated EXE file, directly to the test data can be pasted into the DOS window! Ten 32 1187653245782036, 2894 32 1187653245782036, 2894 1187653245782036, 2894 Ten 32 1187653245782036, 2894 Thirty-six * / #includeiostream #define MAXSIZE / / 20 order table length #define LT (a, b) (a b) #define EQ (a, b) (a = b) #define LQ (a, b) (a b) Using namespace std; Typedef int KeyType; / / keyword in this chapter are as integer Typedef char* InfoType; Typedef struct { KeyType key; InfoType otherinfo; }RedType; / / record type Typedef struct { RedType r[MAXSIZE+1]; unit //0 used as sentry Int length; }SqList; / / the order of the table type //******************************************* / / direct insertion sort Void InsertSort (SqList, L) { / / sorted in non descending order from the table, after the forward sequence comparison Int, I, j; For (I = 2; I L.length; + + I) If LT (L.r[i].key, L.r[i-1].key) { L.r[0]=L.r[i]; For (J = I-1; LT (L.r[0].key, L.r[j].key); --j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }//if } //*********************** / / binary insertion sort Void BInsertSort (SqList, L) { Int, I, j; Int, high, low, m; For (i=2; i=L.length; ++i) { L.r[0]=L.r[i]; Low=1; high=i-1; / / search range from 1 to I-1 While (low=high) { M= (low+high) /2; If LT (L.r[0].key, L.r[m].key) high=m-1; Else low=m+1; / / to find the number of L.r[0].key =L.r[m].key, which is different with the binary search. Its also the reason why high+1 is taken underneath }//while bisearch For (j=i-1; j=high+1; --j) L.r[j+1]=L.r[j]; After the end of high+1 / / bisearch position for insertion position L.r[high+1]=L.r[0]; }//for }//BInsertSort //********************************* Typedef int SortData; Void Swap (SortData, a, SortData, b) { SortData temp; Temp=a; A=b; B=temp; } //************************************