数据结构实验3——排序论述.doc

北京邮电大学信息与通信工程学院 第 PAGE 10页 北京邮电大学电信工程学院 第 PAGE 1页 数据结构实验报告 实验名称： 实验3——排序 学生姓名： 满兴源 班 级： 2014211105 班内序号： 15 学 号： 2014210128 日 期： 2015年12月28日 实验要求 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试排序算法的正确性。 2.1 存储结构 顺序存储结构——数组 2.2 关键算法分析 插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕 void Insertsort(int r[], int n) { for (int i = 2; i = n; i++) { if (r[i] r[i - 1]) { int j; r[0] = r[i]; r[i] = r[i - 1]; for (j = i - 2; r[0] r[j]; j--) r[j + 1] = r[j]; r[j + 1] = r[0]; } } 希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序 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 (r[i] r[i - 1]) { r[0] = r[i]; for (j = i - d; j0 r[0]r[j]; j = j - d) r[j + d] = r[j]; r[j + d] = r[0]; } } } 冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止 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 (r[i]r[i + 1]) { r[0] = r[i]; r[i] = r[i + 1]; r[i + 1] = r[0]; pos = i; } } } 快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成 int Partion(int r[], int first, int end) { int i = first; int j = end; int pivot = r[i]; while (i j) { while ((i j) (r[j] = pivot)) j--; r[i] = r[j]; while ((i j) (r[i] = pivot)) i++; r[j] = r[i]; } r[i] = 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 n; i++) { int in