数据结构-实验四 排序算法的实现

学院

计算机科学与教育软件学院

年级、专业、班

网络161

姓名

卟咚君

学号

1606100***

实验课程名称

数据结构实验

成绩

实验项目名称

实验四排序算法的实现

指导老师

**

一、实验目的

加强对多种排序算法的理解

二、使用仪器、器材

微机一台

操作系统：WinXP

编程软件：C++

三、实验内容及原理

实验内容：用随机函数生成16个2位正整数（10~99），从复杂度为O(n2) 的插入排序、选择排序、冒泡（双向冒泡）和复杂度为O(nlog2n) 的堆排序、快速排序、归并排序等多种排序算法各选1种实现，输出排序中间过程、统计关键字的比较次数和记录的移动次数。

思路：用随机函数rand() % 90 + 10生成16个2位正整数（10~99），使用时间复杂度为O(n2)

的冒泡排序对生成16个2位正整数进行排序。冒泡排序：在每一轮的排序中，通过相邻的两个数的比较, 根据需要决定是否将两个数互换位置, 然后将比较往前(或往后)推进. 这一轮循环结束后最值将会置于顶端。使用时间复杂度为O(nlog2n)的快速排序对生成16个2位正整数进行排序。快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。另外还可以使用基数排序对生成16个2位正整数进行排序。基数排序（radix sort）属于“分配式排序”,基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(d(n+rd))，其中d为所采取的基数，而r为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。在本次实验内容中，使用d=2,r=10,使用基数排序解决本次实验内容问题的时间复杂度为O(n),比前面的两种算法都要快和稳定。

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

const int maxn = 10000 + 10;

/*

*冒泡排序

*在每一轮的排序中，通过相邻的两个数的比较, 根据需要决定是否将两个数互换位置, 然后将比较往前(或往后)推进. 这一轮循环结束后最值将会置于顶端

*/

int cnt_compare, cnt_move;

void bubblesort(int *arrayVal, int length) {

    int i, j;

    int temp;

    for (i = 0; i<length - 1; i++) {

         bool flag = false;  //减枝，标记数组的元素是否在下一轮比较中发生交换，如果没有可以提前结束排序

         for (j = i + 1; j<length; j++) {

             cnt_compare++;

             if (arrayVal[i]>arrayVal[j]) {

                  cnt_move++;

                  flag = true;

                  temp = arrayVal[i];  //置换位置

                  arrayVal[i] = arrayVal[j];

                  arrayVal[j] = temp;

             }

         }

         if (!flag)

             break;

    }

}

/*

*快速排序：

*基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

*/

void quickSort(int a[], int left, int right) {

    int i = left;

    int j = right;

    int temp = a[left];

    if (left >= right) return;

    while (i != j) {

         while (i<j&&a[j] >= temp) {

             cnt_compare++;

             j--;

         }

         if (j>i) {

             cnt_move++;

             a[i] = a[j];                      //a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位　

         }

         while (i<j&&a[i] <= temp) {

             i++;

             cnt_compare++;

         }

         if (i<j) {

             cnt_move++;

             a[j] = a[i];

         }

    }

    a[i] = temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys　　

    quickSort(a, left, i - 1);//递归左边

    quickSort(a, i + 1, right);//递归右边

}

/*

*基数排序（radix sort）属于“分配式排序”,基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

*/

int get_numpos(int num, int pos) {   //返回num的第pos位为数字

    int temp = 1;

    for (int i = 1; i <= pos - 1; i++)

         temp *= 10;

    return (num / temp) % 10;

}

void RadixSort(int *arrayVal, int lenght) {   //基数排序，arrayVal为要排序数组的指针，lenght是数组的元素的个数

    int Max = 0;

    for (int i = 0; i<lenght; i++)    //找出数组最大的元素

         Max = max(Max, arrayVal[i]);

    int l = 0;

    while (Max) {                  //算出最大的位数

         l++;

         Max /= 10;

    }

    int **temp = new int*[12];   //动态申请二位数组

    for (int i = 0; i <= 9; i++)

         temp[i] = new int[lenght]; //开辟列

    for (int i = 1; i <= l; i++) {

         for (int j = 0; j <= 9; j++)

             memset(temp[j], 0, sizeof(temp[j]));    //桶中进行初始化

         for (int j = 0; j<lenght; j++) {

             int a = get_numpos(arrayVal[j], i);     //取出arrayVal[j]的i位数

             temp[a][++temp[a][0]] = arrayVal[j];   //temp[a][0]为键值为a的桶中的元素的个数，将取出的arrayVal[j]加入桶中

         }

         int top = 0;

         for (int j = 0; j <= 9; j++) {

             for (int z = 1; z <= temp[j][0]; z++) {

                  arrayVal[top++] = temp[j][z];

             }

         }

    }

    for (int i = 0; i <= 9; i++)

         delete[] temp[i];

    delete[] temp;

    return;

}

int main() {

    time_t t;

    srand((unsigned)time(&t));  //由时间确定随机序列，执行一次

    int n, a[maxn];

    cout << "请输入数组的元素的个数：";

    cin >> n;

    // 冒泡排序

    for (int i = 0; i < n; i++) {   //(1)随机函数生成100~999的数据存入单链表中

         a[i] = rand() % 90 + 10;

    }

    cout << "***************************" << endl << "          原数组数据：";

    for (int i = 0; i<n; i++)

         printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    cout << "冒泡排序后的数组数据：";

    cnt_compare = 0; cnt_move = 0;

    bubblesort(a, n);

    for (int i = 0; i<n; i++)

         printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    cout << "关键字的比较次数:" << cnt_compare << "          移动次数:" << cnt_move << endl;

    // 快速排序

    for (int i = 0; i < n; i++) {   //(1)随机函数生成100~999的数据存入单链表中

         a[i] = rand() % 90 + 10;

    }

    cout << "***************************" << endl << "          原数组数据：";

    for (int i = 0; i<n; i++)

         printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    cnt_compare = 0; cnt_move = 0;

    quickSort(a, 0, n - 1);

    cout << "快速排序后的数组数据：";

    for (int i = 0; i<n; i++)

         printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    cout << "关键字的比较次数:" << cnt_compare << "          移动次数:" << cnt_move << endl;

    //基数排序

    for (int i = 0; i < n; i++) {   //(1)随机函数生成100~999的数据存入单链表中

         a[i] = rand() % 90 + 10;

    }

    cout << "***************************" << endl << "          原数组数据：";

    for (int i = 0; i<n; i++)

         printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    RadixSort(a, n);

    cout << "基数排序后的数组数据：";

    for (int i = 0; i<n; i++)

         printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    return 0;

}

• 实验过程原始数据记录

（1）用随机函数rand() % 90 + 10生成16个2位正整数（10~99），分别为67，60，88，97，17，75，36，61，87，35，29，13，25，13，27，31。

（2）使用冒泡排序算法进行排序，排序后的结果为13，13，17，25，27，29，31，35，36，60，61，67，75，87，88，97。在这次排序中，关键字的比较次数为120次，数组的元素移动的次数为87次。

（3）用随机函数rand() % 90 + 10生成16个2位正整数（10~99），分别为69，20，41，84，31，29，47，52，63，30，87，39，33，74，99，87。

（4）使用快速排序算法进行排序，排序后的结果为20，29，30，31，33，39，41，47，52，63，69，74，84，87，87，99。在这次排序中，关键字的比较次数为42次，数组的元素移动的次数为16次。

（5）用随机函数rand() % 90 + 10生成16个2位正整数（10~99），分别为32，19，83，51，16，52，27，54，47，44，70，55，78，75，24，54。

(6）使用基数排序算法进行排序，排序后的结果为16，19，24，27，32，44，47，51，52，54，54，55，70，75，78，83

五、实验结果及分析

时间复杂度为O(n2)的冒泡排序：在每一轮的排序中，通过相邻的两个数的比较, 根据需要决定是否将两个数互换位置, 然后将比较往前(或往后)推进. 这一轮循环结束后最值将会置于顶端。

时间复杂度为O(nlog2n)的快速排序对：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

时间复杂度为O(d(n+rd))的基数排序：基数排序（radix sort）属于“分配式排序”,基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(d(n+rd))，其中n个记录，每个记录含d个关键字，每一趟分配的时间复杂度为O(n)，每一趟收集的时复杂度为O(rd)，整个排序需要进行d次分配和收集，所以时间复杂度为O(d(n+rd))。在某些时候，基数排序法的效率高于其它的稳定性排序法。在本次实验内容中，d=2,r=10 ,使用基数排序解决本次实验内容的时间复杂度为O(n),比前面的两种算法都要快和稳定。

通过本次实验，对多种排序算法的有了更深刻的理解，明白了各种排序算法的实现的思想以及一些优化的策略，在不同的排序要求中，使用不同的排序算法的效果也是不一样的，比如说，在数据无法分割成更小的关键字的时候，一般使用时间复杂度为O(nlog2n)的排序算法，而在一些数据可以分割的更小的关键字比较时和知道各级关键字的主次关系和各级关键字的取值范围，并且对排序的要求很高的时候，使用基数排序有更好的效率，比如说，在2009年的国家队算法论文中罗穗骞《后缀数组——处理字符串的有力工具》的使用到的倍增思想求后缀数组的排序中，需要的子模块排序中使用的就是基数排序。