内部排序算法的性能分析
25 / 36
/*SSelectSort.cpp*/ #include \#include \
extern bool TEST_FSC; //外部标识符，演示排序处使用 /*
* 对顺序表L作选择排序 */
SORT_MARK_FSC Status SSelectSort(SqList &L, unsigned long &cmpcount, unsigned long &shftcount, double &timeuse) {
int i, j, k, l=0;
clock_t start, finish; start = clock(); cmpcount = 0; shftcount= 0;
if (TEST_FSC == true)
printf(\排序中 ***\\n\);
for (i = 1; i < L.length; i++) //选择第i小的记录，并交换位置 {
k = i;
for (j = i+1; j <= L.length; j++) //选择第i小的记录 {
if ( LESST(L.r[j].key, L.r[k].key) ) {
k = j; } }
if (k != i) //与第i个记录交换 {
SWAP(L.r[i], L.r[k]); if ( TEST_FSC == true ) {
printf(\第%d躺排序...\, ++l); Output(L); } } }
L.r[0].key = 0; finish = clock();
timeuse = (double)(finish - start) / CLOCKS_PER_SEC; return OK; }
25
内部排序算法的性能分析
26 / 36
/*QuickSort.cpp*/ #include \#include \
extern bool TEST_FSC; //外部标识符，演示排序处使用 int i; //演示次数统计 /*
* 交换顺序表中子表L.r[low..high]的记录，使枢轴记录到位，
* 并返回其所在位置，此时在它之前（后）的记录均不大于(小）于它 */
SUB_SORT_MARK_FSC Status Partition(SqList &L, int low, int high, int &pivot, unsigned long &cmpcount, unsigned long &shftcount) {
MOV(L.r[0], L.r[low]); //用子表的第一个记录作为枢轴记录 while(low < high) //从表的两端交替地向中间扫描 {
while ( (low < high) && MOREQ(L.r[high].key, L.r[0].key)) high--;
MOV(L.r[low], L.r[high]); //将比枢轴记录小的记录移动到低端
while ( (low < high) && LESSQ(L.r[low].key, L.r[0].key)) low++;
MOV(L.r[high], L.r[low]); //将比枢轴记录大的记录移动到高端 }
MOV(L.r[low], L.r[0]); //枢轴记录到位 pivot = low; //返回枢轴记录位置 if ( TEST_FSC == true ) //排序演示输出 {
printf(\第%d躺排序...\, ++i); Output(L); }
return OK; } /*
* 对顺序表L中的子序列L.r[low..high]作快速排序 */
SUB_SORT_MARK_FSC Status QSort (SqList &L, int low, int high,
unsigned long &cmpcount, unsigned long &shftcount) {
int pivotloc;
if (low < high) //长度大于 {
Partition(L, low, high, pivotloc, cmpcount, shftcount);
26
内部排序算法的性能分析
27 / 36
//将L.r[low..high]一分为二 QSort(L, low, pivotloc-1, cmpcount, shftcount); //对低子表递归排序 QSort(L, pivotloc+1, high, cmpcount, shftcount);//对高子表递归排序 }
return OK; } /*
* 对顺序表L作快速排序 */
SORT_MARK_FSC Status QuickSort(SqList &L, unsigned long &cmpcount,
unsigned long &shftcount, double &timeuse) {
clock_t start, finish; start = clock(); cmpcount = 0; shftcount= 0;
if (TEST_FSC == true)
printf(\排序中 ***\\n\); i = 0;
QSort(L, 1, L.length, cmpcount, shftcount);
finish = clock();
timeuse = (double)(finish - start) / CLOCKS_PER_SEC; //计算时间 return OK; }
/*ShellSort.cpp*/ #include
extern bool TEST_FSC; //外部标识符，演示排序处使用 /*
* 产生增量序列，dlta[k] = 2 ^ (t-k+1) -1,1<=k<=t<=[log2(n+1)] */
27
内部排序算法的性能分析
28 / 36
SUB_SORT_MARK_FSC Status ProcDlta(int *&dlta, int &t) {
int k;
t = int((log(double(MAX_SIZE + 1))) / ( log(2.0))); dlta = (int *)malloc( (t+1) * sizeof(int)); for (k = 1; k <= t; k++) {
dlta[k] = int ( pow(2.0, double(t-k+1) ) ) - 1; }
return OK; } /*
* 对顺序表L作一趟希尔插入排序. */
SUB_SORT_MARK_FSC Status ShellInsert (SqList &L, int dk, unsigned long &cmpcount, unsigned long &shtfcount) {
int i, j;
for (i = dk+1; i <= L.length; i++) {
if (LESST(L.r[i].key, L.r[i-dk].key)) //需将L.r[i]插入到有序增量子表 {
MOV(L.r[0], L.r[i]); //暂存在L.r[0]
for (j = i-dk; j>0 && LESST(L.r[0].key, L.r[j].key); j -= dk) {
MOV(L.r[i], L.r[i-dk]); //记录后移，查找插入位置 i -= dk; }
MOV(L.r[i], L.r[0]); //插入 } }
return OK; } /*
* 按增量序列dlta[0...t-1]对顺序表L作希尔排序. */
SORT_MARK_FSC Status ShellSort (SqList &L, unsigned long &cmpcount, unsigned long &shtfcount, double &timeuse) {
int k,j = 0; int *dlta, t;
clock_t start, finish;
28
内部排序算法的性能分析
29 / 36
start = clock(); cmpcount = 0; shftcount= 0;
if (TEST_FSC == true)
printf(\排序中 ***\\n\);
ProcDlta(dlta, t); //产生增量序列 for (k = 1; k <= t; k++)
ShellInsert (L, dlta[k], cmpcount, shtfcount);
//一趟增量为dlta[k]的插入排序 if ( TEST_FSC == true ) //排序演示输出 {
printf(\第%d躺排序...\, ++j); Output(L); }
finish = clock();
timeuse = (double)(finish - start) / CLOCKS_PER_SEC;//计算时间 return OK; }
/*HeapSort.cpp*/ #include \#include \
extern bool TEST_FSC; //外部标识符，演示排序处使用 typedef SqList HeapType; //转换类型 /*
* 已知L.r[s...m]中记录的关键字除L.r[s].key之外均满足堆定义，本函数调整L.r[s] * 的关键字，使H.r[s...m]成为一个大顶堆（对其中记录的关键字而言） */
SUB_SORT_MARK_FSC Status HeapAdjust(HeapType &L, int s, int m,
unsigned long &cmpcount, unsigned long &shftcount) {
int i;
for(i = 2*s; i <= m; i *= 2) //沿key较大的孩子结点向下筛选 {
if (MOREQ(L.r[s].key, L.r[i].key)) //rc应插入在位置s上 break;
if ((i < m) && (LESST(L.r[i].key, L.r[i+1].key)) )
//j为key较大的记录的下表
29