数据结构实验报告-排序

[toc]

一、实验目的

• 学习各种排序的基本原理，并能计算各种排序的时间复杂度
• 能使用c/c++实现快速排序,并记录运行时间

二、实验环境

• 操作系统：Ubuntu 18.04 LTS
• IDE：CLion
• 编译器：g++
• 数据（随机生成）：https://paste.ubuntu.com/p/DbxZ3GFFK8/

三、实验内容

• 用随机函数产生 10000（或更多）个整数（或浮点数），保存在文件（intfile.dat / realfile.dat）中
• 然后将文件中的所有整数（或浮点数）读入一个数组 a。用快速排序算法对上述数组 A中的数据进行排序
• 输出排序过程中元素的比较次数、交换（移动）次数，以及排序过程所消耗的时间（以 s 或 ms 为单位）

四、实验问题

• while循环内交换顺序错误，应该先右–，然后将右边的元素放到左边。对利用key多出来的空位的做法还是不太熟悉。
• while判断时写了等号，导致死循环。

五、数据结构

数组，存放整型待排数据。

六、算法及代码

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

//a数组存储数据，size记录数据个数
int a[10007];
int size;
int compTimes = 0;
int swapTimes = 0;

//随机生成数据
void createdata() {
    string path = "random.txt";
    ofstream f(path);
    srand((unsigned) time(0));
    for (int i = 0; i < 10000; ++i) {
        f << rand() << endl;
    }
}

//从文件中读入数据
void readdata(string path) {
    ifstream f(path);
    for (size = 0; !f.eof(); size++) {
        f >> a[size];
    }
    //尾行总是多读入一个0，所以长度减一
    size--;
}

//快速排序
void quicksort(int left, int right) {
    //当要排的元素只有一个时，不用操作，直接退出
    if (left >= right)
        return;
    int l = left, r = right;
    //最左端的元素为基准元素
    int key = a[left];
    //左边元素都小于基准元素，右边的都大于基准元素，才结束循环
    while (l < r) {
        //右指针移到比基准元素小的元素，用被移动过，没有用的空位的左指针记录
        while (l < r && a[r] >= key)
            r--, compTimes++;
        a[l] = a[r], swapTimes++;
        //同理，左指针移到比基准元素大的元素，用被移动过，没有用的空位的右指针记录
        while (l < r && a[l] <= key)
            l++, compTimes++;
        a[r] = a[l], swapTimes++;
    }
    //最后左右指针位置重合，且左指针的位置实际上是空的，存入基准元素
    a[l] = key;
    //基准元素左右两边分别快排
    quicksort(left, l - 1);
    quicksort(r + 1, right);
}

// 打印当前所有数据
void print() {
    cout << a[0];
    for (int i = 1; i < size; i++) {
        cout << " " << a[i];
    }
    cout << endl;
}

int main() {
    clock_t start, end;
    //createdata();
    string path = "/home/hjy/CLionProjects/数据结构实验-排序/random.txt";
    readdata(path);
    print();
    //记录排序前的时间
    start = clock();
    quicksort(0, size - 1);
    //记录排序之后的时间
    end = clock();
    print();
    cout << "比较次数： " << compTimes << endl;
    cout << "移动次数： " << swapTimes << endl;
    cout << "用时：" <<(double)( end - start )/CLOCKS_PER_SEC<< " s" << endl;
    return 0;
}

七、运行结果

八、实验小结

在这次实验中，我学会了快速排序算法的原理，能使用c++代码实现，并能统计比较次数，交换次数，以及计算时间复杂度。而且，我还学会了用ctime中的clock记录程序运行的时间。收获颇丰。