数据结构实验3——排序

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验3排序学生姓名： 满兴源班 级： 2014211105班内序号： 15学 号： 2014210128日 期： 2015年12月28日1 实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到

2、微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试排序算法的正确性。2.1 存储结构 顺序存储结构数组2.2 关键算法分析1. 插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕void Insertsort(int r, int n)for (int i = 2; i <= n; i+)if (ri < ri - 1)int j;r0 = ri;ri = ri - 1;for (j = i - 2; r0 < rj; j-)rj + 1 = rj;rj + 1 = r0;2. 希尔排序：先将

3、整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序void ShellInsert(int r, int n)int j;for (int d = n / 2; d >= 1; d = d / 2)for (int i = d + 1; i <= n; i+)if (ri < ri - 1)r0 = ri;for (j = i - d; j>0 && r0<rj; j = j - d)rj + d = rj;rj + d = r0;3. 冒泡排序：两两比较相邻记录的关键码，如果反序则交

4、换，直到没有反序记录为止void BubbleSort(int r, int n)int pos = n;while (pos != 0)int bound = pos;pos = 0;for (int i = 1; i < bound; i+)if (ri>ri + 1)r0 = ri;ri = ri + 1;ri + 1 = r0;pos = i;4. 快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成int Partion(int r, int first, int end)int i = fir

5、st;int j = end;int pivot = ri;while (i < j)while (i < j) && (rj >= pivot)j-;ri = rj;while (i < j) && (ri <= pivot)i+;rj = ri;ri = pivot;return i;void QSort(int r, int i, int j)if (i <j)int pivotloc = Partion(r, i, j);QSort(r, i, pivotloc - 1);QSort(r, pivotloc + 1,

6、j);5. 选择排序：从待排序的记录序列中选择关键码最小的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止void SelectSort(int r, int n)for (int i = 1; i < n; i+)int index = i;for (int j = i + 1; j <= n; j+)if (rj < rindex)index = j;if (index != i)r0 = ri;ri = rindex;rindex = r0

7、;用户输入数组开始3. 程序运行结果3.1主函数流程图五种排序输出结果结束3.2程序运行框图源代码：#include<iostream>using namespace std;void print(int r, int n)for (int i = 1; i <= n; i+)cout << ri << " "cout << endl;/*插入排序*/void Insertsort(int r, int n)for (int i = 2; i <= n; i+)if (ri < ri - 1)int j;r0

8、 = ri;ri = ri - 1;for (j = i - 2; r0 < rj; j-)rj + 1 = rj;rj + 1 = r0;/*希尔排序*/void ShellInsert(int r, int n)int j;for (int d = n / 2; d >= 1; d = d / 2)for (int i = d + 1; i <= n; i+)if (ri < ri - 1)r0 = ri;for (j = i - d; j>0 && r0<rj; j = j - d)rj + d = rj;rj + d = r0;/*改

9、进的冒泡排序*/void BubbleSort(int r, int n)int pos = n;while (pos != 0)int bound = pos;pos = 0;for (int i = 1; i < bound; i+)if (ri>ri + 1)r0 = ri;ri = ri + 1;ri + 1 = r0;pos = i;/*快速排序*/int Partion(int r, int first, int end)int i = first;int j = end;int pivot = ri;while (i < j)while (i < j) &

10、amp;& (rj >= pivot)j-;ri = rj;while (i < j) && (ri <= pivot)i+;rj = ri;ri = pivot;return i;void QSort(int r, int i, int j)if (i <j)int pivotloc = Partion(r, i, j);QSort(r, i, pivotloc - 1);QSort(r, pivotloc + 1, j);/*简单选择排序*/void SelectSort(int r, int n)for (int i = 1; i <

11、 n; i+)int index = i;for (int j = i + 1; j <= n; j+)if (rj < rindex)index = j;if (index != i)r0 = ri;ri = rindex;rindex = r0;void main()int x;int n = 10;int rr11 ,a11 ;rr0 = -1;cout << "请输入需要排序的数组："for (int i = 1; i <= 10; i+)cin >> x;rri = x;for (int i = 1; i <= 10

12、; i+)ai = rri;Insertsort(rr, n);cout << "插入排序法排序后的数为：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;ShellInsert(rr, n);cout << "希尔排序法排序后的数为：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;BubbleSort(rr, n);cout << &qu

13、ot;冒泡排序法(改进）排序后的数为：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;QSort(rr, 1, n);cout << "快速排序法排序后的数为：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;SelectSort(rr, n);cout << "简单选择排序法排序后的数为：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;4. 总结1.调试时出