肝了三天的实验，压秒提交了实验报告（太南了）。

大概的内容是分析五个基本排序，以不同的规模大小比较不同算法的性能，以及比较实测与理论时间的差异。

实验环境

• 编译环境
  • CLion 2019.3.5
  • MinGW64
• 语言及版本
  • C++20

算法设计

冒泡排序

思路

很基础的算法，不写了。

代码

template <typename T>
void bubble(std::vector<T >& vec) {
    for (int i = 0; i < vec.size() - 1; ++i) {
        bool flag = false;
        for (int j = 0; j < vec.size() - 1 - i; ++j) {
            if (vec[j] > vec[j + 1]) {
                std::swap(vec[j], vec[j + 1]);
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
};

其中flag用来标记是否已经有序：当没有发生交换时，说明vector已经有序，退出排序。

性能分析

最坏情况执行的操作次数为 n(n – 1)/2，最好情况为 n。

时间复杂度为O(n²)。

选择排序

思路

每轮从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

代码

template <typename T>
void select(std::vector<T >& vec) {
    for (int i = 0; i < vec.size() - 1; ++i) {
        // flag为最小值的下标
        int flag = i;
        for (int j = i + 1; j < vec.size(); ++j) {
            if (vec[flag] > vec[j]) {
                flag = j;
            }
        }
        //swap
        if (flag != i) {
            std::swap(vec[i], vec[flag]);
        }
    }
};

性能分析

最好最坏比较情况相同，都为 n(n-1)/2 次。

时间复杂度为 O(n²)。

归并排序

思路

归并排序是建立在两个有序数组合并为一个有序数组的操作上的。假设合并后的数组为r，比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则亦然。如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中。

但正常情况下是没有两个有序的子序列的。这种情况下，将一个无序的数组不断的拆分成有序的数组，再进行合并，最后排列成有序的数组。

代码

template<typename T>
void merge(std::vector<T> &vec, int min, int max) {
    if (min == max) {
        //如果一个数，不用排序
        return;
    } else {
        int middle = (min + max) / 2;
        //将其平分为两个无序序列，分别进行排序
        merge(vec, min, middle);
        merge(vec, middle + 1, max);
        //如果最左边的最大值比左右边的最小值还小，则不用排序
        if (vec[middle] < vec[middle + 1]) {
            return;
        }
        //对两个有序序列进行归并排序
        sort(vec, min, middle + 1, max);
    }
}

该部分函数负责将两个无序的子序列拆分分别排序，再合并成一个有序的序列。

template<typename T>
void sort(std::vector<T> &vec, int min, int middle, int max) {
    std::vector<T> leftVec, rightVec;
    //初始化leftVec, rightVec
    int left_pointer = 0, right_pointer = 0;
    int pointer = min;
    //执行归并操作
    while (left_pointer < leftVec.size() && right_pointer < rightVec.size()) {
        if (leftVec[left_pointer] > rightVec[right_pointer]) {
            vec[pointer++] = rightVec[right_pointer++];
        } else {
            vec[pointer++] = leftVec[left_pointer++];
        }
    }
    //如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中
    while (left_pointer < leftVec.size()) {
        vec[pointer++] = leftVec[left_pointer++];
    }
    //同上，将右边的数抄到大数组中，代码省略
}

该部分为排序函数。

性能分析

参考博客

https://blog.csdn.net/sinat_36306474/article/details/77906344

• 总花费时间 = 分解时间 + 解决问题时间 + 合并时间；
• 分解时间：将vector拆成两部分，时间固定，为O(1)；
• 解决问题时间：将规模为(n)的问题拆成两个(n/2)的问题。时间为2T(n/2)(即解决两次规模为n/2的问题)；
• 合并时间：运行n次合并操作，O(n)。
• 总时间：T(n)=2T(n/2)+o(n)。
• 经计算时间复杂度为 nlogn。

插入排序

思路

每轮排序中，将vector分为两部分：第一部分为已排序后的有序数列，第二部分为待插入的数。通过从后往前遍历找到插入的位置，将所有的数向后移一位，再插入带插入的数。

代码

template<typename T>
void insert(std::vector<T> &vec) {
    for (int i = 1; i < vec.size(); i++) {
        //设置待比较的数，其前面的数列为已排序的数列
        int key = vec[i];
        int j = i - 1;
        //若大于，则退出比较;否则不断将数字向后推移
        while ((j >= 0) && (key < vec[j])) {
            vec[j + 1] = vec[j];
            j--;
        }
        //最后插入待比较的数
        vec[j + 1] = key;
    }
}

性能分析

• 最坏情况：数组完全逆序，比较次数为1 + 2 + … + (n – 1)，为O(n²)。
• 最好情况：数组已经排序，比较次数为1 + 1 + … + 1，为O(n)。

快速排序

思路

标记一个数，将比该数小的数全部移动到该数的左边，比该数大的数都移动到该数右边，再递归的对两个子序列进行该步骤。

代码

具体的快速排序有很多种实现的方式（我好像是写了一个最简单的？）。

template<typename T>
void quick(std::vector<T> &vec, int begin, int end) {
    if (begin < end) {
        int point = sort(vec, begin, end);
        quick(vec, begin, point - 1);
        quick(vec, point + 1, end);
    }
}
template<typename T>
int sort(std::vector<T> &vec, int begin, int end) {
    int key = vec[begin];
    while (begin < end) {
        while (begin < end && vec[end] >= key) {
            end -= 1;
        }
        std::swap(vec[begin], vec[end]);
        while (begin < end && vec[begin] <= key) {
            begin += 1;
        }
        std::swap(vec[begin], vec[end]);
    }
    return begin;
}

性能分析

• 最好情况时间复杂度：O(nlogn)
• 最坏情况时间复杂度：O(n²)
• 平均时间复杂度：O(nlogn)

平行比较

设置n=10, n=100, n=1000, n=10000, n=100000，分别使用五个算法，测试五个算法消耗的时间。

得到的不同类型算法关于n的规模的表格：

取个对数做折线图：

可以看出来规模较大时，O(n²)和O(nlogn)差距还是挺大的。

理论效率和实测比较

这里运用的方法是取当n的值为1000时，各个算法进行比较的操作次数，与实际测量时间取线性关系，推算出理论时间的计算公式。

冒泡排序

选择排序

归并排序

插入排序

快速排序

这里决定差值的原因可能有很多，比较重要的一点是当n的规模较小时，决定操作时间大小的除了比较次数，还有比如调用，交换等操作占用的时间，会使得在n的值较小时，这些无关变量没有远小于比较操作的时间，使得实测的时间远大于理想时间。