肝了三天的实验,压秒提交了实验报告(太南了)。
大概的内容是分析五个基本排序,以不同的规模大小比较不同算法的性能,以及比较实测与理论时间的差异。
实验环境
- 编译环境
- 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的值较小时,这些无关变量没有远小于比较操作的时间,使得实测的时间远大于理想时间。