(最新整理)10.1几种基本排序算法的实现

1、(完整)10.1几种基本排序算法的实现(完整)10.1几种基本排序算法的实现 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)10.1几种基本排序算法的实现）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)10.1几种基本排序算法的实现的全部内容。数 据 结 构 实 验 报 告实验题目:几种基本排序算法的实现

2、姓名： 张耀班级： 计嵌151学号： 1513052017一、 实验目的实现直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等6种常用内部排序算法,比较各算法的比较次数和移动次数。二、 数据结构设计(1) 设计待排序记录的存储结构。(2) 设计待排序数据的存储结构。(3) 输入：待排序数据的数据个数和数据可由键盘输入，也可由程序生成伪随机数，以菜单方式选择上述排序方法中的一个，并指明输出第几趟排序的结果。（4)输出:各趟排序结果或指定趟的排序结果，以及对应的关键字比较次数和移动次数。三、 算法设计与ns图算法设计：编写一个主函数main(），在主函数中设计一个简单的菜单,分别调

3、用6种内部排序算法。为了对各种排序算法的性能进行比较，算法中的主要工作是在已知算法的适当位置插入对关键字的比较次数和移动次数的计数操作.为此，可设立一个实现排序算法中的关键字比较的函数；设立一个实现排序算法中的关键字移动的函数;设立一个实现排序算法中的关键字交换的函数，从而解决比较次数和移动次数的统计问题。数据的输入也可以通过菜单选择输入方式：键盘输入或由伪随机数程序生成数据,以便随时更换排序数据，并按照不同要求对排序数据进行排序，输出排序的结果以及对应的关键字比较次数和移动次数。对于测试数据,算法中可以考虑几组数据的典型性，如正序,逆序和不同程度等，以取得直观的感受,从而对不同算法进行比较。

4、四、 程序清单includeiostreamusing 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 sqlistint * key;int length;void createsqlist(sqlist &sl)/type为intint n；cout 建立顺序表”

5、endl 请输入顺序表的长度” endl;cin n；sl。length = n；sl。key = new intsl.length + 1；cout 请输入数据: endl;for (int i = 1； i sl.keyi；void copy(sqlist &l1，sqlist &l2)l2.length = l1。length;l2.key = new intl1.length + 1；for (int i = 1； i =l1。length； i+)l2。keyi = l1.keyi；void output(sqlist &l）for （int j = 1； j = l。length;

6、 +j)cout l。keyj ”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.keyi = l。keyi - 1）/”需将l。keyi插入有序子表l.key0 = l.keyi；/复制为哨兵l.keyi = l。keyi 1;int j;for (j = i 2； l.key0 = l。keyj； -j)compare_time

7、+;l。keyj + 1 = l.keyj；/记录后移move_time+;l.keyj + 1 = l.key0；/插入到正确位置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.length; i+）/用i

8、控制比较趟数共n1趟int t；for (int j = 1; j l.keyj + 1）t = l。keyj；l.keyj = l。keyj + 1；l。keyj + 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.keyn；for (int

9、 i = n + 1; i = l。length； i+）if （l。keyiminkey）minkey = l。keyi；min = i；compare_time+;return min;void selectsort(sqlist l）/对顺序表l作简单选择排序int j;int t；int k = 0；int move_time = 0， compare_time = 0；for （int i = 1； i = l。length; i+)j = selectminkey(l， i, compare_time）；/在l.keyi-l.keyl.length中选择最小的记录并将其地址赋给ji

10、f （i != j)/交换记录t = l.keyi；l。keyi = l.keyj；l。keyj = t；move_time+；compare_time+;k+;cout 第” k ”趟排序结果：; output（l）；cout 比较次数为： compare_time endl；cout ”移动次数为：” move_time endl；int partition(sqlist& l， int low, int high，int &compare_time,int &move_time）/交换顺序表l中子表keylow-keyhigh中的记录,枢轴记录到位，并返回其所在位置，/此时在它之前（后）

11、的记录均不大（小）于它int pivotkey;l。key0 = l。keylow;/用子表的第一个记录作枢轴记录pivotkey = l.keylow;/关键字while (low= pivotkey） -high;l.keylow = l。keyhigh;move_time+;/将比枢轴小的记录移至低端while （lowhigh&l。keylow = pivotkey) +low；l。keyhigh = l。keylow；/将比枢轴大的记录移至高端move_time+;l.keylow = l.key0;/枢轴记录到位return low；/返回枢轴位置void qsort（sqlist

12、 l, int low, int high,int &k,int compare_time，int &move_time）int mid;/接收枢轴位置if （lowhigh)mid = partition（l， low， high，compare_time,move_time);k+;cout 第” k ”趟排序结果：； output（l）；qsort（l， low， mid 1,k,compare_time,move_time）;/对低子表进行排序qsort（l, mid + 1， high, k， compare_time， move_time);/对高子表进行排序void quitso

13、rt（sqlist l）/对顺序表进行快速排序int k = 0;int compare_time = 0, move_time = 0；qsort（l, 1， l.length，k,compare_time,move_time）;cout ”比较次数为：” compare_time endl;cout 移动次数为： move_time endl;void shellinsert(sqlist &l， int dk， int compare_time, int &move_time)/对顺序表进行一趟希尔插入排序for （int i = dk + 1; i = l。length； i+）if

14、(l.keyi = l。keyi - dk）compare_time+；l.key0 = l.keyi；int j；for (j = i dk； j 0 & l.key0 = l.keyj； j -= dk）compare_time+;l.keyj + dk = l.keyj;move_time+；l.keyj + dk = l。key0；void shellsort(sqlist l， int dlta， int t)int compare_time = 0, move_time = 0；/按增量序列dl0-dlt-1对顺序表l作哈希排序for (int k = 0; k t; k+)she

15、llinsert(l, dltak， 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.keys;for （int j = 2 * s； j = m； j = 2）if （jm&l.keyj l.

16、keyj） break；/如果rc最大则推出while循环l.keys = l.keyj;/最大值赋值s = j；/交换位置move_time+；l.keys = rc;void heapsort(sqlist l）/对顺序表l进行堆排序int value,i;int k = 0；int compare_time = 0， move_time = 0;for (i = l。length / 2; i0； i）/把l。key1.l。length调整为大顶堆heapadjust（l, i， l。length, compare_time， move_time)；for (i = l。length；

17、i1; -i）value = l.key1;l.key1 = l.keyi；l。keyi = value;heapadjust(l， 1， i - 1, compare_time， move_time)；/将l.key1。.。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 choic

18、e；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 请输入增量个数：” n;p = new intn；cout ”请输入各个增量的值: endl；for (int i = 0; i pi;shellsort（sq, p， n); cout 最终结果:”;output(sq);