C++算法学习之旅

记录我学习的C++算法
所有的算法使用的C++标准都为ISO/IEC 14882:2011或以上

查找

对分查找

  • 原理

数组必须有序
每趟都从数组最中间的数(如果有小数就取整)与需要查找的数比较,然后继续从前半部分或后半部分取中间的数与需要查找的数比较,直到中间的数为需要查找的数.如果没有则返回-1

  • 时间复杂度:O(log n)

  • 代码

1
2
3
4
5
6
7
8
9
10
11
template <typename T, unsigned size>
unsigned binarySearch(T (&vec)[size], T key) {
unsigned left{0}, right{size - 1};
while (left <= right) {
unsigned mid = (left + right) / 2U;
if (vec[mid] == key) return mid;
else if (vec[mid] < key) left = mid + 1;
else right = mid - 1;
}
return -1;
}

排序

冒泡排序

  • 原理

从后向前两两比较大小,如果数值大(或小)就交换,如果相反则不变,继续比较前面的数与前前面的数
重复此过程(数组大小 - 1)趟

  • 时间复杂度:O(n²)

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T, unsigned size>
void bubbleSort(T (&vec)[size], bool StoL) {
for (unsigned i = 0; i < size; ++i) {
for (unsigned j = size - 1; j > i; --j) {
bool able = StoL ? vec[j] < vec[j - 1] : vec[j] > vec[j - 1];
if (able) {
T temp = vec[j];
vec[j] = vec[j - 1];
vec[j - 1] = temp;
}
}
}
}

选择排序

  • 原理

每次遍历数组找到最小值,然后与(初始下标 + 遍历的次数)位置的数交换
重复此过程(数组大小 - 1)趟

  • 时间复杂度:O(n²)

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename T, unsigned size>
void selctionSort(T (&vec)[size], bool StoL) {
for (unsigned i = 0; i < size; ++i) {
unsigned lim{i};
for (unsigned j = i + 1; j < size; ++j) {
bool able = StoL ? vec[j] < vec[lim] : vec[j] > vec[lim];
if (able) {
lim = j;
}
}
if (lim != i) {
T temp = vec[i];
vec[i] = vec[lim];
vec[lim] = temp;
}
}
}

插入排序

  • 原理

假设(初始下标 + 遍历的次数 - 1)前面的数都是有序的,现在把(初始下标 + 遍历的次数)的数与前面的数比较,如果比较结果大(小),则交换

  • 时间复杂度:O(n²)

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T, unsigned size>
void insertionSort(T (&vec)[size], bool StoL) {
for (unsigned i = 0; i < size; ++i) {
for (unsigned j = i; j > 0; --j) {
bool able = StoL ? vec[j] < vec[j - 1] : vec[j] > vec[j - 1];
if (able) {
T temp = vec[j];
vec[j] = vec[j - 1];
vec[j - 1] = temp;
} else {
break;
}
}
}
}

用模板元获取数组大小

  • 代码
    1
    2
    3
    4
    template<typename T, int size>
    unsigned sizeOfArray(T (&)[size]) {
    return size;
    }

拆分一个8字节类型变量变成两个4字节整型变量

拆分整型

  • 代码
1
2
3
4
5
std::pair<int32_t, int32_t> cutLong(const int64_t &i) {
int32_t high = (int32_t)((uint64_t)i >> 32U);
int32_t low = (int32_t)i;
return std::make_pair(high, low);
}
  • 如何恢复
1
2
3
4
int64_t i = 123456789123456;
std::pair<int32_t, int32_t> mPair = cutLong(i);
int64_t bits = (((uint64_t)mPair.first) << 32U) | (uint32_t)mPair.second;
//bits即为原先的值

拆分实型

  • 代码
1
2
3
4
5
6
std::pair<int32_t, int32_t> cutDouble(const double &d) {
auto bits = *(int64_t *)&d;
auto high = (int32_t)((uint64_t)bits >> 32U);
auto low = (int32_t)bits;
return std::make_pair(high, low);
}
  • 如何恢复
1
2
3
4
5
double d = 123456789.123456;
std::pair<int32_t, int32_t> mPair = cutDouble(d);
int64_t bits = (((uint64_t)mPair.first) << 32U) | (uint32_t)mPair.second;
double realValue = *(double *)&bits;
//realValue即为原先的值

树结构搜索

二叉树

  • 代码
1
2
3
4
5
6
7
class node {
public:
std::string name{};
std::shared_ptr<node> left = nullptr;
std::shared_ptr<node> right = nullptr;
explicit node(std::string name) : name(std::move(name)){};
};

广度优先搜索(BFS)

  • 原理

从根节点开始,沿着树的宽度遍历树的节点。如果搜索到或者未搜索到,则算法中止
一般用队列数据结构来辅助实现BFS算法

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void breadthFirstSearch(const std::shared_ptr<node>& _node, const std::string &keyName) {
std::queue<std::shared_ptr<node>> queue{};
queue.push(_node);
while (!queue.empty()) {
std::shared_ptr<node> mNode = queue.front();
std::cout << mNode -> name << std::endl; // Output search path
queue.pop();
if (mNode -> name != keyName) {
if (mNode -> left != nullptr) {
queue.push(mNode -> left);
}
if (mNode -> right != nullptr) {
queue.push(mNode -> right);
}
} else {
return;
}
}
}

深度优先搜索(DFS)

  • 原理

从根节点开始,沿着树的深度遍历树的节点。如果搜索到或者未搜索到,则算法中止
一般用栈数据结构来辅助实现DFS算法

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void depthFirstSearch(const std::shared_ptr<node> &_node, const std::string &keyName) {
std::stack<std::shared_ptr<node>> stack{};
stack.push(_node);
while (!stack.empty()) {
std::shared_ptr<node> mNode = stack.top();
std::cout << mNode -> name << std::endl; // Output search path
stack.pop();
if (mNode -> name != keyName) {
if (mNode -> right != nullptr) {
stack.push(mNode -> right);
}
if (mNode -> left != nullptr) {
stack.push(mNode -> left);
}
} else {
return;
}
}
}

大数

相加

  • 原理

长度小的字符串补齐 ‘0’,然后两边字符串遍历字符转换数值进行相加,最后长度一定不超过长度大的字符串的长度 + 1

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
std::string add(std::string a, std::string b) {
std::string result, _num = a, _ano_num = b;
unsigned long size = (a.size() >= b.size() ? a.size() : b.size()) + 1;
for (unsigned long i = 0; i < size; ++i) {
if ((a.size() <= b.size() ? a.size() : b.size()) < i) {
a.size() <= b.size() ? _num.insert(0, "0") : _ano_num.insert(0, "0");
}
}
bool enter = false;
for (std::string::reverse_iterator rev_iter_num = _num.rbegin(), rev_iter_ano_num = _ano_num.rbegin(); rev_iter_num != _num.rend() && rev_iter_ano_num != _ano_num.rend(); ++rev_iter_num, ++rev_iter_ano_num) {
int value{};
value = (*(rev_iter_num) - '0') + (*(rev_iter_ano_num) - '0');
if (enter) {
++value;
enter = false;
}
if (value >= 10) {
result.insert(0, std::to_string(value - 10));
enter = true;
} else {
result.insert(0, std::to_string(value));
}
}
if (enter) result.insert(0, "1");
return result;
}

相减

1
//TODO

相乘

1
//TODO

相除

1
//TODO

进制转换

  • 原理

先把原进制的数根据每位乘原进制的位次方,得到原进制的十进制数,然后循环对要转换的进制取余,取到的数放到结果的最后面

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::string decimalConvert(std::string sourceValue, unsigned sourceDecimal, unsigned destDecimal, unsigned fillZero = 0) {
std::string code{"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"}, _value{sourceValue}, _result;
int64_t _dec_value{};
bool negative = sourceValue[0] == '-';
if (negative) {
_value = sourceValue.substr(1, sourceValue.size());
}
int m{};
for (std::string::reverse_iterator _iter = _value.rbegin(); _iter != _value.rend(); ++_iter, ++m) {
_dec_value += code.find(*_iter) * std::pow(sourceDecimal, m);
}
while (_dec_value > 0) {
_result = code[_dec_value % destDecimal] + _result;
_dec_value /= destDecimal;
}
_result = negative ? '-' + _result : _result;
while (fillZero--) {
_result.insert(0, "0");
}
return _result;
}

如有错误 请联系qaralotte@gmail.com
敬请雅正:)