实习六：部排序.docVIP

实验报告 题目：内部排序算法比较 一．需求分析 对以下6种常见的内部排序算法进行比较：起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。 待排序表的表长不小于100；其中的数据要用伪随机数产生；至少要用5组不同的输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数。 最后要对结果作出简单分析，包括对各组数据的出结果波动大小的解释。 测试数据有随机数产生器产生。 二．详细设计 #include ctime #include cmath #include cstdio #include cstring #include iostream #include algorithm #define LT(a, b) (++cmp_num, ((a) (b))) #define MAX_SIZE 10000 #define MAXV 1000000 using namespace std; typedef int KeyType; typedef struct _RedType { KeyType key; } RedType; typedef struct _SqList { RedType r[MAX_SIZE + 1]; int length; } SqList; typedef SqList HeapType; typedef void SortProc(SqList L, int cmp_num, int move_num); void InsertSort(SqList L, int cmp_num, int move_num) { // 对顺序表L作直接插入排序 cmp_num = move_num = 0; for (int i = 2; i = L.length; ++i) if (LT(L.r[i].key, L.r[i - 1].key)) { int j; L.r[0] = L.r[i]; L.r[i] = L.r[i - 1]; for (j = i - 2; LT(L.r[0].key, L.r[j].key); --j) L.r[j + 1] = L.r[j], move_num++; L.r[j + 1] = L.r[0]; move_num += 3; // 关键字交换记为3次移动 } } void BubbleSort(SqList L, int cmp_num, int move_num) { // 对顺序表L作起泡排序 cmp_num = move_num = 0; for (int i = 1; i L.length; ++i) for (int j = L.length - 1; j = i; j--) if (LT(L.r[j + 1].key, L.r[j].key)) { L.r[0] = L.r[j + 1]; L.r[j + 1] = L.r[j]; L.r[j] = L.r[0]; move_num += 3; } } void SelectSort(SqList L, int cmp_num, int move_num) { // 对顺序表L作简单选择排序 cmp_num = move_num = 0; for (int i = 1; i L.length; ++i) { int m = i; for (int j = i + 1; j = L.length; j++) if (LT(L.r[j].key, L.r[m].key)) m = j; swap(L.r[i], L.r[m]); move_num += 3; } } void QSort(SqList L, int low, int high, int cmp_num, int move_num) { // 对顺序表L中的子序列L.r[low..high]作快速排序 if (low high) { int l = low, r = high; KeyType base = L.r[low].key; L.r[0] = L.r[low]; while (l r) { while (l r !LT(L.r[r].key, base)) r--; L.r[l] = L.r[r]; while (l r !LT(base, L.r[l].key)) l++; L.r[r] = L.r[l]; move_num += 2; } L.r[l]