10.1几种基本排序算法的实现

数据结构实验报告 实验题目：几种基本排序算法的实现 姓名：    张耀 班级：    计嵌151 学号：    1513052017 一、 实验目的 实现直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等6种常用内部排序算法，比较各算法的比较次数和移动次数。 二、 数据结构 (1) 设计待排序记录的存储结构。 (2) 设计待排序数据的存储结构。 (3) 输入：待排序数据的数据个数和数据可由键盘输入，也可由程序生成伪随机数，以菜单方式选择上述排序中的一个，并指明输出第几趟排序的结果。 (4)输出：各趟排序结果或指定趟的排序结果，以及对应的关键字比较次数和移动次数。 三、 算法设计与N-S图 算法设计： 编写一个主函数main()，在主函数中设计一个简单的菜单，分别调用6种内部排序算法。 为了对各种排序算法的性能进行比较，算法中的主要工作是在已知算法的适当位置插入对关键字的比较次数和移动次数的计数操作。为此，可设立一个实现排序算法中的关键字比较的函数；设立一个实现排序算法中的关键字移动的函数；设立一个实现排序算法中的关键字交换的函数，从而解决比较次数和移动次数的统计问题。 数据的输入也可以通过菜单选择输入方式：键盘输入或由伪随机数程序生成数据，以便随时更换排序数据，并按照不同要求对排序数据进行排序，输出排序的结果以及对应的关键字比较次数和移动次数。 对于测试数据，算法中可以考虑几组数据的典型性，如正序，逆序和不同程度等，以取得直观的感受，从而对不同算法进行比较。 四、 程序清单 #include using namespace std; void showMenu() { cout << "      *  菜单  *      " << endl; cout << "    1.直接插入排序    " << endl; cout << "    2.冒泡排序        " << endl; cout << "    3.简单选择排序    " << endl; cout << "    4.快速排序        " << endl; cout << "    5.希尔排序        " << endl; cout << "    6.堆排序          " << endl; cout << "    7.退出程序        " << endl; } struct SqList{ int * key; int length; }; void CreateSqList(SqList &sl)//type为int { int n; cout << "建立顺序

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

" << endl << "请输入顺序表的长度" << endl; cin >> n; sl.length = n; sl.key = new int[sl.length + 1]; cout << "请输入数据：" << endl; for (int i = 1; i <= sl.length; i++) { cin >> sl.key[i]; } } void Copy(SqList &L1,SqList &L2) { L2.length = L1.length; L2.key = new int[L1.length + 1]; for (int i = 1; i <=L1.length; i++) { L2.key[i] = L1.key[i]; } } void OutPut(SqList &L) { for (int j = 1; j <= L.length; ++j) cout << L.key[j] << "\t"; cout << endl; } void InsertSort(SqList & L) {//对顺序表L作直接插入排序 int k = 0; int compare_Time, move_Time; compare_Time = move_Time = 0; for (int i = 2; i <= L.length; i++) { if (L.key[i] <= L.key[i - 1])//"<"需将L.key[i]插入有序子表 { L.key[0] = L.key[i];//复制为哨兵 L.key[i] = L.key[i - 1]; int j; for (j = i - 2; L.key[0] <= L.key[j]; --j) { compare_Time++; L.key[j + 1] = L.key[j];//记录后移 move_Time++; } L.key[j + 1] = L.key[0];//插入到正确位置 k++; cout << "第" << k << "趟排序结果："; OutPut(L); } compare_Time++; } cout << "比较次数为：" << compare_Time << endl; cout << "移动次数为：" << move_Time << endl; } void BubbleSort(SqList & L) { int k = 0; int compare_Time, move_Time; compare_Time = move_Time = 0; for (int i = 1; iL.key[j + 1]) { t = L.key[j]; L.key[j] = L.key[j + 1]; L.key[j + 1] = t; move_Time++; } } k++; cout << "第" << k << "趟排序结果："; OutPut(L); } cout << "比较次数为：" << compare_Time << endl; cout << "移动次数为：" << move_Time << endl; } int SelectMinKey(SqList& L, int n, int &compare_Time) { int min = n; int minkey;//最小值 minkey = L.key[n]; for (int i = n + 1; i <= L.length; i++) { if (L.key[i]= pivotkey) --high; L.key[low] = L.key[high]; move_Time++;//将比枢轴小的记录移至低端 while (low 0 && L.key[0] <= L.key[j]; j -= dk) { compare_Time++; L.key[j + dk] = L.key[j]; move_Time++; } L.key[j + dk] = L.key[0]; } } void ShellSort(SqList &L, int dlta[], int t) { int compare_Time = 0, move_Time = 0; //按增量序列dl[0]--dl[t-1]对顺序表L作哈希排序 for (int k = 0; k < t; k++) { ShellInsert(L, dlta[k], compare_Time, move_Time); cout << "第" << k+1 << "趟排序结果："; OutPut(L); } cout << "比较次数为：" << compare_Time << endl; cout << "移动次数为：" << move_Time << endl; } void HeapAdjust(SqList& L, int s, int m, int &compare_Time, int &move_Time) {//对顺序表做查找，从值最大的孩子结点向下筛选，找到最大值 int rc = L.key[s]; for (int j = 2 * s; j <= m; j *= 2) { if (jL.key[j]) break;//如果rc最大则推出while循环 L.key[s] = L.key[j];//最大值赋值 s = j;//交换位置 move_Time++; } L.key[s] = rc; } void HeapSort(SqList & L) {//对顺序表L进行堆排序 int value,i; int k = 0; int compare_Time = 0, move_Time = 0; for (i = L.length / 2; i>0; i--)//把L.key[1...L.length]调整为大顶堆 HeapAdjust(L, i, L.length, compare_Time, move_Time); for (i = L.length; i>1; --i) { value = L.key[1]; L.key[1] = L.key[i]; L.key[i] = value; HeapAdjust(L, 1, i - 1, compare_Time, move_Time);//将L.key[1...i-1]重新调整为大顶堆 k++; cout << "第" << k << "趟排序结果："; OutPut(L); } cout << "比较次数为：" << compare_Time << endl; cout << "移动次数为：" << move_Time << endl; } int main() { int choice; SqList sq,sp; CreateSqList(sq); Copy(sq, sp); showMenu(); cout << "Please enter your choice: "; cin >> choice; while (choice != 0) { switch (choice) { case 1: InsertSort(sq); cout << "最终结果："; OutPut(sq); break; case 2: BubbleSort(sq); cout << "最终结果："; OutPut(sq); break; case 3: SelectSort(sq); cout << "最终结果："; OutPut(sq); break; case 4: QuitSort(sq); cout << "最终结果："; OutPut(sq); break; case 5: int *p, n; cout << "请输入增量个数：" << endl; cin >> n; p = new int[n]; cout << "请输入各个增量的值：" << endl; for (int i = 0; i < n; i++) { cin >> p[i]; } ShellSort(sq, p, n); cout << "最终结果："; OutPut(sq); break; case 6: HeapSort(sq); cout << "最终结果："; OutPut(sq); break; case 7: cout << "程序运行结束，退出程序。" << endl; return 0; break; } Copy(sp, sq); showMenu(); cout << "Please enter your choice: "; cin >> choice; } return 0; } 五、 运行与测试 六、 实验

分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析

及体会 通过这次试验主要让我们深入了解了各种排序的不同特点和排序原理，各种排序在时间复杂度和空间复杂度上均各有差异，对于不同的排序案例，我们可以根据他们各自的特点挑选最佳的排序

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

。今后在实际操作中会注意各个排序的特点正确的运用。 2017，加油！