**操作环境：**win8.1+vs2015 说明：1、对直接插入排序、折半排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序的简单测试（生成5000个随机数测试执行时间）； 2、采用文件分离。
//file name:sort.h#PRagma once#ifndef SORT_H#define SORT_H#define OK 1#define ERROR 0#define OVERFLOW -1#define MAXSIZE 5000 //待排序元素个数typedef int Status;/*函数返回值类型*/typedef int KeyType, InfoType;/*关键字类型和其他数据项的类型*/typedef struct { KeyType key; InfoType otherinfo = 0;}RedType;typedef struct { RedType *r; int length;}SqList;typedef struct { double CostTime = 0.0; unsigned long MoveCount = 0; unsigned long CompareCount = 0;}RunCondition, *pRunCondition;Status InitSqList(SqList*);/*构造一个空顺序表*/Status CreateSqList(SqList*);/*输入数据元素个数，随机产生整数样本*/Status CopySqList(SqList, SqList*);Status OutputSqList(SqList);/*输出排序后的数据*/int LT(KeyType, KeyType);/*判断元素e1是否小于e2*/void Swap(RedType*, RedType*);/*交换两元素*/Status isEmpty(SqList);Status InsertSort(SqList*, pRunCondition);/*直接插入排序*/Status BInsertSort(SqList*, pRunCondition);/*折半排序*/Status ShellInsert(SqList*, int,pRunCondition);/*一趟希尔排序*/Status ShellSort(SqList*, int*, int,pRunCondition);/*希尔排序*/Status BubbleSort(SqList*, pRunCondition);/*冒泡排序*/int Partition(SqList*, int, int,pRunCondition);/*一趟快速排序*/void QSort(SqList*, int, int,pRunCondition);Status QuickSort(SqList*, pRunCondition);/*快速排序*/Status SelectSort(SqList*, pRunCondition);/*选择排序*/void HeapAdjust(SqList*, int, int,pRunCondition);Status HeapSort(SqList*, pRunCondition);/*堆排序*/Status Merge(SqList*, int, int, int,pRunCondition);void MSort(SqList*, int,pRunCondition);Status MergeSort(SqList*, pRunCondition);/*归并排序*/#endif//file name:sort.cpp#include <stdio.h>#include <math.h>#include <time.h>#include <stdlib.h>#include "sort.h"Status InitSqList(SqList *L)/*构造一个空顺序表*/{ L->r = (RedType*)malloc((MAXSIZE + 1) * sizeof(RedType)); if (!L->r)//分配空间不成功 exit(OVERFLOW); L->length = 0; return OK;}//InitSqListStatus CreateSqList(SqList *L)/*输入数据元素个数，随机产生整数样本*/{ int i; srand((unsigned int)time(NULL)); printf("/nPlease input the number of unsorted data:"); scanf("%d", &L->length); for (i = 1; i <= L->length; ++i) { L->r[i].key = rand(); } printf(">>>>>>>>>>>>>>>>>SUCCESS!/n"); /* printf("/n/nThe unsorted data is:/n"); for (i = 1; i <= L->length; ++i) { printf("%8d", L->r[i]); } */ return OK;}//CreateSqListStatus CopySqList(SqList L_BAK, SqList *L){ int i; if (!L_BAK.length) { printf("The SqList is empty!"); return ERROR; } for (i = 1; i <= L_BAK.length; ++i) { L->r[i].key = L_BAK.r[i].key; L->r[i].otherinfo = L_BAK.r[i].otherinfo; } L->length = L_BAK.length; return OK;}//CopySqListStatus OutputSqList(SqList L)/*输出排序后的数据*/{ int i; printf("/nThe length of SqList is:%d/n", L.length); printf("/n/nThe sorted data is:/n"); for (i = 1; i <= L.length; ++i) { printf("%8d", L.r[i]); } printf("/n"); return OK;}//OutputSqListint LT(KeyType e1, KeyType e2)/*判断元素e1是否小于e2*/{ return (e1 < e2) ? 1 : 0;}//LTvoid Swap(RedType *e1, RedType *e2)/*交换两元素*/{ RedType e; e = *e1; *e1 = *e2; *e2 = e;}//SwapStatus isEmpty(SqList L){ return (L.length) ? OK : ERROR;}/*直接插入排序*/Status InsertSort(SqList *L, pRunCondition cnd)/*直接插入排序*/{ int i, j; if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } for (i = 2; i <= L->length; ++i) { cnd->CompareCount++;//比较次数加1 if (LT(L->r[i].key, L->r[i - 1].key)) { L->r[0] = L->r[i]; L->r[i] = L->r[i - 1]; cnd->MoveCount += 2; for (j = i - 2; LT(L->r[0].key, L->r[j].key); --j) { cnd->CompareCount++; cnd->MoveCount++; L->r[j + 1] = L->r[j]; }//for L->r[j + 1] = L->r[0]; cnd->MoveCount++; }//if }//for return OK;}//InsertSort/*折半插入排序*/Status BInsertSort(SqList *L, pRunCondition cnd)/*折半排序*/{ int i, j, low, high, m; if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } for (i = 2; i <= L->length; ++i) { L->r[0] = L->r[i]; cnd->MoveCount++; low = 1; high = 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; } cnd->CompareCount++; }//while for (j = i - 1; j >= high + 1; --j) { L->r[j + 1] = L->r[j]; cnd->MoveCount++; }//for L->r[high + 1] = L->r[0]; cnd->MoveCount++; }//for return OK;}//BInsertSort/*希尔排序*/Status ShellInsert(SqList *L, int dk,pRunCondition cnd)/*一趟希尔排序*/{ int i, j; for (i = dk + 1; i <= L->length; ++i) { cnd->CompareCount++; if (LT(L->r[i].key, L->r[i - dk].key)) { L->r[0] = L->r[i]; cnd->MoveCount++; for (j = i - dk; j > 0 && LT(L->r[0].key, L->r[j].key); j -= dk) { cnd->MoveCount++; cnd->CompareCount++; L->r[j + dk] = L->r[j]; }//for L->r[j + dk] = L->r[0]; cnd->MoveCount++; }//if }//for return OK;}//ShellInsertStatus ShellSort(SqList *L, int *dlta, int t,pRunCondition cnd)/*希尔排序*/{ int k; if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } for (k = 0; k < t; ++k) { ShellInsert(L, dlta[k], cnd); }//for return OK;}//ShellSort/*冒泡排序*/Status BubbleSort(SqList *L, pRunCondition cnd)/*冒泡排序*/{ int i, j; if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } for (i = 1; i < L->length; ++i) { for (j = 1; j <= L->length - i; ++j) { cnd->CompareCount++; if (!LT(L->r[j].key, L->r[j + 1].key)) { Swap(&L->r[j], &L->r[j + 1]); cnd->MoveCount += 3; } }//for }//for return OK;}//BubbleSort/*快速排序*/Status QuickSort(SqList *L, pRunCondition cnd)/*快速排序*/{ if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } QSort(L, 1, L->length,cnd); return OK;}//QuickSortvoid QSort(SqList *L, int low, int high, pRunCondition cnd){ int pivotloc; if (low < high) { pivotloc = Partition(L, low, high, cnd); QSort(L, low, pivotloc - 1, cnd); QSort(L, pivotloc + 1, high, cnd); }//if}//QSortint Partition(SqList *L, int low, int high, pRunCondition cnd)/*一趟快速排序*/{ KeyType pivotkey; L->r[0] = L->r[low]; pivotkey = L->r[low].key; while (low < high) { while (low < high&&L->r[high].key >= pivotkey) { --high; cnd->CompareCount++; }//while; L->r[low] = L->r[high];//1次 while (low < high&&L->r[low].key <= pivotkey) { ++low; cnd->CompareCount++; }//while L->r[high] = L->r[low];//1次 cnd->MoveCount += 2; }//while L->r[low] = L->r[0]; cnd->MoveCount += 3; return low;}//Partition/*选择排序*/Status SelectSort(SqList *L, pRunCondition cnd)/*选择排序*/{ int i, j, min; if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } for (i = 1; i < L->length; ++i) { min = i; for (j = i + 1; j <= L->length; ++j) { cnd->CompareCount++; if (LT(L->r[j].key, L->r[min].key)) { min = j; }//if }//for if (min != i) { Swap(&L->r[i], &L->r[min]); cnd->MoveCount += 3; }//if }//for return OK;}//SelectSort/*归并排序*/Status MergeSort(SqList *L, pRunCondition cnd)/*归并排序*/{ int len; if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } for (len = 1; len < L->length; len *= 2) { MSort(L, len, cnd); }//for return OK;}//MergeSortvoid MSort(SqList *L, int len, pRunCondition cnd){ int i; for (i = 1; i + 2 * len - 1 <= L->length; i += 2 * len) { Merge(L, i, i + len - 1, i + 2 * len - 1, cnd); }//for if (i + len - 1 < L->length) { Merge(L, i, i + len - 1, L->length,cnd); }//if}//MSortStatus Merge(SqList *L, int low, int mid, int high, pRunCondition cnd){ int i = low, j = mid + 1, k = 0; SqList L1; L1.r = (RedType*)malloc((high - low + 1) * sizeof(RedType)); if (!L1.r) { exit(OVERFLOW); }//if while (i <= mid&&j <= high) { cnd->CompareCount++; cnd->MoveCount++; L1.r[k++] = LT(L->r[i].key, L->r[j].key) ? L->r[i++] : L->r[j++]; }//while while (i <= mid) { cnd->MoveCount++; L1.r[k++] = L->r[i++]; }//while while (j <= high) { cnd->MoveCount++; L1.r[k++] = L->r[j++]; }//while for (k = 0, i = low; i <= high; k++, i++) { cnd->MoveCount++; L->r[i].key = L1.r[k].key; }//for return OK;}//Merge/*堆排序*/Status HeapSort(SqList *L, pRunCondition cnd)/*堆排序*/{ int i; if (isEmpty(*L) == ERROR) { printf("Empty SqList!/n"); return ERROR; } for (i = L->length / 2; i > 0; --i) { HeapAdjust(L, i, L->length, cnd); }//for for (i = L->length; i > 1; --i) { Swap(&L->r[1], &L->r[i]); cnd->MoveCount += 3; HeapAdjust(L, 1, i - 1, cnd); }//for return OK;}//HeapSortvoid HeapAdjust(SqList *L, int s, int m, pRunCondition cnd){ int j; RedType rc = L->r[s]; for (j = 2 * s; j <= m; j *= 2) { if (j < m&<(L->r[j].key, L->r[j + 1].key)) { ++j; }//if if (!LT(rc.key, L->r[j].key)) { break; }//if L->r[s] = L->r[j]; s = j; cnd->MoveCount++; cnd->CompareCount += 2; }//for L->r[s] = rc; cnd->MoveCount += 2;}//HeapAdjust//file name:sort_main.cpp#include <stdio.h>#include <math.h>#include <time.h>#include <stdlib.h>#include <conio.h>#include "sort.h"#if 0int main(){ SqList L, L_BAK; RunCondition rCnd[9];/*记录比较次数、移动次数，运行时间*/ int t,select, flag = 1; int dlta[MAXSIZE]; clock_t start, finish; InitSqList(&L); InitSqList(&L_BAK); CreateSqList(&L_BAK); /*产生希尔排序的增量序列dlta[0..t]*/ t = 0; dlta[0] = (int)(L_BAK.length / 2); while (dlta[t] > 1) { dlta[t + 1] = dlta[t] / 2; ++t; } while(flag){ CopySqList(L_BAK, &L); printf("Please select:/n"); printf("1.InsertSort/n"); printf("2.BInsertSort/n"); printf("3.ShellSort/n"); printf("4.BubbleSort/n"); printf("5.QuickSort/n"); printf("6.SelectSort/n"); printf("7.HeapSort/n"); printf("8.MergeSort/n"); printf("9.Exit/n"); scanf("%d", &select); switch (select) { case 1: printf("/nNow is in InsertSort..."); start = clock(); InsertSort(&L, &rCnd[1]); finish = clock(); rCnd[1].CostTime = (double)(finish - start); break; case 2: printf("/nNow is in BInsertSort..."); start = clock(); BInsertSort(&L, &rCnd[2]); finish = clock(); rCnd[2].CostTime = (double)(finish - start); break; case 3: printf("/nNow is in ShellSort..."); start = clock(); ShellSort(&L, dlta, t + 1, &rCnd[3]); finish = clock(); rCnd[3].CostTime = (double)(finish - start); break; case 4: printf("/nNow is in BubbleSort..."); start = clock(); BubbleSort(&L, &rCnd[4]); finish = clock(); rCnd[4].CostTime = (double)(finish - start); break; case 5: printf("/nNow is in QuickSort..."); start = clock(); QuickSort(&L, &rCnd[5]); finish = clock(); rCnd[5].CostTime = (double)(finish - start); break; case 6: printf("/nNow is in SelectSort..."); start = clock(); SelectSort(&L, &rCnd[6]); finish = clock(); rCnd[6].CostTime = (double)(finish - start); break; case 7: printf("/nNow is in HeapSort..."); start = clock(); HeapSort(&L, &rCnd[7]); finish = clock(); rCnd[7].CostTime = (double)(finish - start); break; case 8: printf("/nNow is in MergeSort..."); start = clock(); MergeSort(&L, &rCnd[8]); finish = clock(); rCnd[8].CostTime = (double)(finish - start); break; default: flag = 0; printf("Press any key to exit!/n"); getch(); }//switch printf("/n"); OutputSqList(L, rCnd[select]); }//while return 0;}#endifStatus Test();int main(){ Test(); getch(); return 0;}Status Test(){ SqList L, L_BAK; RunCondition rCnd[9];/*记录比较次数、移动次数，运行时间*/ int t, select = 0, flag = 1; int dlta[MAXSIZE]; clock_t start, finish; InitSqList(&L); InitSqList(&L_BAK); CreateSqList(&L_BAK); /*产生希尔排序的增量序列dlta[0..t]*/ t = 0; dlta[0] = (int)(L_BAK.length / 2); while (dlta[t] > 1) { dlta[t + 1] = dlta[t] / 2; ++t; } while (flag) { if (select >= 0 && select < 8) { CopySqList(L_BAK, &L); } select++; switch (select) { case 1: printf("/nNow is in InsertSort..."); start = clock(); InsertSort(&L, &rCnd[1]); finish = clock(); rCnd[1].CostTime = (double)(finish - start); break; case 2: printf("/nNow is in BInsertSort..."); start = clock(); BInsertSort(&L, &rCnd[2]); finish = clock(); rCnd[2].CostTime = (double)(finish - start); break; case 3: printf("/nNow is in ShellSort..."); start = clock(); ShellSort(&L, dlta, t + 1, &rCnd[3]); finish = clock(); rCnd[3].CostTime = (double)(finish - start); break; case 4: printf("/nNow is in BubbleSort..."); start = clock(); BubbleSort(&L, &rCnd[4]); finish = clock(); rCnd[4].CostTime = (double)(finish - start); break; case 5: printf("/nNow is in QuickSort..."); start = clock(); QuickSort(&L, &rCnd[5]); finish = clock(); rCnd[5].CostTime = (double)(finish - start); break; case 6: printf("/nNow is in SelectSort..."); start = clock(); SelectSort(&L, &rCnd[6]); finish = clock(); rCnd[6].CostTime = (double)(finish - start); break; case 7: printf("/nNow is in HeapSort..."); start = clock(); HeapSort(&L, &rCnd[7]); finish = clock(); rCnd[7].CostTime = (double)(finish - start); break; case 8: printf("/nNow is in MergeSort..."); start = clock(); MergeSort(&L, &rCnd[8]); finish = clock(); rCnd[8].CostTime = (double)(finish - start); break; default: flag = 0; printf("Press any key to show the result!/n"); getch(); }//switch printf("/nThe sort spend:%.2lf s/nMove count:%ld/tCompare count:%ld/n", rCnd[select].CostTime/CLOCKS_PER_SEC, rCnd[select].MoveCount, rCnd[select].CompareCount); printf("-------------------------------------------/n/n"); }//while OutputSqList(L); return OK;}新闻热点
疑难解答
