2023.3.5-复习排序算法

[TOC]

不同的排序算法有不同的算法复杂度。

初级排序算法

学习这些简单的算法的原因在于：

通过它们熟悉一些术语和简单的技巧
这些算法在某些情况下会比复杂算法更加有效。

游戏规则

我们的操作对象是数组元素，其中每个元素都有一个主键。

排序的目的：所有元素的主键按照某种方式进行排列。

对于数组来说，他有index和value。一般来说我们通过改变index的值，使其value升序排序（或是逆序）。

验证正确性：使用assert来确认在排序后数组元素都是有序的。

Select

==不断选择剩下元素中的最小者。==

首先找到数组元素中最小的元素，与数组的第一个元素交换位置。
然后再找到剩下的数组中最小的元素，与数组的第二个元素交换位置。
······
直至整个数组有序。

C++ random库

#include<random>

在random类中，通过一组协作的类来完成随机数的生成：

random-numbers engine
random-numbers distribution

engine可以生成unsigned随机数列，distribution使用engine生成指定类型（指定范围，服从指定概率分布的随机数）。

default_random_engine e;
for(size_t i=0;i<10;i++)cout<<e()<<endl;//调用e()生成下一个随机数


uniform_int_distribution<unsigned> u(0,9)
for(size_t i=0;i<10;i++)cout<<u(e)<<endl;//将u作为随机数源，每个调用返回在指定范围内并服从均匀分布的值

使用engine生成数值序列

随机数发生器：==生成的树看起来是随机的==。

但是对于一个给定的随机数发生器，每次运行程序都会返回相同发的数值序列（假随机）

这也是为什么我们如果使用C语言的rand之前要先srand(0);

vector<unsigned >bad_randVec(){
    default_random_engine e;
    uniform_int_distribution<unsigned >u(0,9);
    vector<unsigned >ret;
    for(size_t i = 0;i<100;i++)
        ret.push_back(u(e));
    return ret;
}
// 但是 每次调用这个函数都会返回相同的 vector
vector<unsigned >v1(bad_randVec());
vector<unsigned >v2(bad_randVec());
// 将会打印输出 equal
cout << ((v1==v2) ? "equal" : "not equal") << endl;