几种基本排序算法的实现

1、·数据结构实验报 告实验题目：几种基本排序算法的实现：耀班级：计嵌 151学号：1513052017Word 资料·一、实验目的实现直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等6 种常用部排序算法，比较各算法的比较次数和移动次数。二、数据结构设计(1) 设计待排序记录的存储结构。(2) 设计待排序数据的存储结构。(3) 输入：待排序数据的数据个数和数据可由键盘输入，也可由程序生成伪随机数，以菜单方式选择上述排序方法中的一个，并指明输出第几趟排序的结果。(4)输出：各趟排序结果或指定趟的排序结果，以及对应的关键字比较次数和移动次数。三、算法设计与 N-S

2、 图算法设计：编写一个主函数main() ，在主函数中设计一个简单的菜单，分别调用6 种部排序算法。为了对各种排序算法的性能进行比较，算法中的主要工作是在已知算法的适当位置插入对关键字的比较次数和移动次数的计数操作。为Word 资料·此，可设立一个实现排序算法中的关键字比较的函数； 设立一个实现排序算法中的关键字移动的函数； 设立一个实现排序算法中的关键字交换的函数，从而解决比较次数和移动次数的统计问题。数据的输入也可以通过菜单选择输入方式： 键盘输入或由伪随机数程序生成数据，以便随时更换排序数据， 并按照不同要求对排序数据进行排序，输出排序的结果以及对应的关键字比较次数和移动次数。

3、对于测试数据，算法中可以考虑几组数据的典型性，如正序，逆序和不同程度等，以取得直观的感受，从而对不同算法进行比较。四、程序清单#include<iostream>using namespace std;void showMenu()cout << "*菜单*" << endl;cout << "1.直接插入排序" << endl;cout << "2.冒泡排序" << endl;cout << "3.简单选择排序" &l

4、t;< 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 << &quo

5、t; 建立顺序表 " << endl << "请输入顺序表的长度 " << endl;Word 资料·cin >> n;sl.length = n;sl.key = new intsl.length + 1;cout << " 请输入数据： " << endl;for (int i = 1; i <= sl.length; i+)cin >> sl.keyi;void Copy(SqList &L1,SqList &L2)L2.l

6、ength = 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; +j)cout << L.keyj << "t"cout << endl;void InsertSort(SqList & L)/ 对顺序表 L作直接插入排序int k = 0;int compare_Time

7、, 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+;L.keyj + 1 = L.keyj;/记录后移Word 资料·move_Time+;L.keyj + 1

8、 = 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 c

9、ompare_Time, move_Time;compare_Time = move_Time = 0;for (int i = 1; i<L.length; i+)/用i控制比较趟数共 n-1 趟int t;for (int j = 1; j <= L.length - i; j+)compare_Time+;if (L.keyj>L.keyj + 1)t = L.keyj;L.keyj = L.keyj + 1;L.keyj + 1 = t;move_Time+;k+;cout << " 第" << k << &qu

10、ot;趟排序结果： " OutPut(L);cout << " 比较次数为： " << compare_Time << endl;cout << " 移动次数为： " << move_Time << endl;int SelectMinKey(SqList& L, int n, int &compare_Time)int min = n;int minkey;/ 最小值Word 资料·minkey = L.keyn;for (int i = n +

11、 1; i <= L.length; i+)if (L.keyi<minkey)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中选择最

12、小的记录并将其地址赋给jif (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 &

13、lt;< endl;int Partition(SqList& L, int low, int high,int &compare_Time,int &move_Time)Word 资料·/ 交换顺序表 L中子表 keylow-keyhigh中的记录，枢轴记录到位， 并返回其所在位置，/ 此时在它之前（后）的记录均不大（小）于它int pivotkey;L.key0 = L.keylow;/用子表的第一个记录作枢轴记录pivotkey = L.keylow;/关键字while (low<high)/从表的两端交替向中间扫描compare_Time+

14、;while (low<high&&L.keyhigh >= pivotkey) -high;L.keylow = L.keyhigh;move_Time+;/将比枢轴小的记录移至低端while (low<high&&L.keylow <= pivotkey) +low;L.keyhigh = L.keylow;/将比枢轴大的记录移至高端move_Time+;L.keylow = L.key0;/枢轴记录到位return low;/ 返回枢轴位置void QSort(SqList& L, int low, int high,int

15、 &k,int &compare_Time,int &move_Time)int mid;/ 接收枢轴位置if (low<high)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

16、, compare_Time, move_Time);/ 对高子表进行排序void QuitSort(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;Word 资料·cout << " 移动次数为： " << mo

17、ve_Time << endl;void ShellInsert(SqList &L, int dk, int &compare_Time, int &move_Time)/ 对顺序表进行一趟希尔插入排序for (int i = dk + 1; i <= L.length; i+)if (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

18、_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+)ShellInsert(L, dltak, compare_Time, move_Time);cout << " 第" << k+1 << &qu

19、ot;趟排序结果： " 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;fo

20、r (int j = 2 * s; j <= m; j *= 2)if (j<m&&L.keyj <= L.keyj + 1)/找到值相对较大的孩子结点，并依次向下筛选j+;Word 资料·compare_Time+;if (rc>L.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

21、 compare_Time = 0, move_Time = 0;for (i = L.length / 2; i>0; i-)/ 把 L.key1.L.length 调整为大顶堆 HeapAdjust(L, i, L.length, compare_Time, move_Time);for (i = L.length; i>1; -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

22、 << " 第" << 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 <&l

23、t; "Please enter your choice: "cin >> choice;while (choice != 0)switch (choice)Word 资料·case 1:InsertSort(sq); cout << "最终结果： "OutPut(sq); break;case 2:BubbleSort(sq); cout << "最终结果： "OutPut(sq); break;case 3:SelectSort(sq); cout << "最终结果： "OutPut(sq); break;