排序算法性能分析

肝了三天的实验,压秒提交了实验报告(太南了)。

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

实验环境

  • 编译环境
    • 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的值较小时,这些无关变量没有远小于比较操作的时间,使得实测的时间远大于理想时间。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇