C++练习备忘录

1. 保留两位小数输出格式

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{double S = 0;S = (15 + 25) * 20 / 2;cout << fixed << setprecision(2) << S;return 0;
}

2. 设置输出宽度

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{int a, b, c;cin >> a >> b >> c;cout << setw(8) << a << " ";cout << setw(8) << b << " ";cout << setw(8) << c;return 0;
}

3. ASCII码转换

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{char a;cin >> a;cout << int(a);return 0;
}

4. 高精度加法

#include <iostream>
using namespace std;// 字符型转整型
void strtoint(string src, int des[]) {for (int i = 0;i < src.size();i++) {//从[1]开始倒序存整型数字，使得个位对齐des[src.size() - i] = src[i] - '0'; }
}int main()
{	string s1, s2;int a[201] = {0};int b[201] = {0};int ans[201] = {0};cin >> s1 >> s2;/* 字符型转整型，通过反转使得个位对齐s1: 1234s2: 567序列号：01234a:  4321b:  765*/strtoint(s1, a);strtoint(s2, b);// 计算ans数组长度，按最长位+1int a_size = s1.size(), b_size = s2.size();int ans_size = max(a_size, b_size) + 1;// 对位相加得到ans数组for (int i = 1;i <= ans_size;i++) {ans[i] = a[i] + b[i] + ans[i]; // a+b+进位ans[i + 1] = ans[i] / 10; // 进位ans[i] %= 10; // 留个位数}// 去除前导0while (ans[ans_size] == 0 && ans_size > 1)ans_size--;// 倒序打印得最后结果for (int i = ans_size;i >= 1;i--)cout << ans[i];return 0;
}

5. 高精度减法

这里多加了一下a和b大小的判别

#include <iostream>
using namespace std;// 字符型转整型
void strtoint(string src, int des[]) {for (int i = 0;i < src.size();i++) {//从[1]开始倒序存整型数字，使得个位对齐des[src.size() - i] = src[i] - '0';}
}// 比较字符串输入数的大小
bool cmpstring(string str1, string str2) {if (str1.size() != str2.size())return str1.size() > str2.size();elsereturn str1 >= str2;
}int main()
{string s1, s2;int a[201] = { 0 };int b[201] = { 0 };int ans[201] = { 0 };cin >> s1 >> s2;// 保证大数减小数if (cmpstring(s1, s2) == false) {swap(s1, s2);cout << "-";}/* 字符型转整型，通过反转使得个位对齐s1: 1234s2: 567序列号：01234a:  4321b:  765*/strtoint(s1, a);strtoint(s2, b);// 计算ans数组长度int a_size = s1.size(), b_size = s2.size();int ans_size = max(a_size, b_size);// 对位相减得到ans数组for (int i = 1;i <= ans_size;i++) {// 判断够不够减if (a[i] < b[i]) {a[i + 1]--;a[i] += 10;}ans[i] = a[i] - b[i];}// 去除前导0while (ans[ans_size] == 0 && ans_size > 1)ans_size--;// 倒序打印得最后结果for (int i = ans_size;i >= 1;i--)cout << ans[i];return 0;
}

6. 高精度乘法

#include <iostream>
using namespace std;// 字符型转整型
void strtoint(string src, int des[]) {for (int i = 0;i < src.size();i++) {//从[1]开始倒序存整型数字，使得个位对齐des[src.size() - i] = src[i] - '0';}
}int main()
{string s1, s2;int a[101] = { 0 };int b[101] = { 0 };int ans[201] = { 0 };cin >> s1 >> s2;strtoint(s1, a);strtoint(s2, b);// 计算ans数组长度int a_size = s1.size(), b_size = s2.size();int ans_size = a_size + b_size;/*序列号：5	 4	  3	   2	  1a4b1 a3b1 a2b1  a1b1a4b2	a3b2 a2b2 a1b2得：ans[i + j - 1] += a[i] * b[j]*/for (int i = 1;i <= a_size;i++) {for (int j = 1;j <= b_size;j++) {ans[i + j - 1] += a[i] * b[j];ans[i + j] += ans[i + j - 1] / 10;ans[i + j - 1] %= 10;}}// 去除前导0while (ans[ans_size] == 0 && ans_size > 1)ans_size--;// 倒序打印得最后结果for (int i = ans_size;i >= 1;i--)cout << ans[i];return 0;
}

7. 冒泡排序

• 时间复杂度：O($n^2$)
• 空间复杂度：O($1$)
• 稳定性：稳定

代码：

void bubbleSort(vector<int>& nums) {int n = nums.size();for (int i = 0; i < n-1; i++) {bool swapped = false;for (int j = 0; j < n-i-1; j++) {if (nums[j] > nums[j+1]) {swap(nums[j], nums[j+1]);swapped = true;}}// 如果一轮遍历没有发生交换，说明序列已经有序，提前结束排序if (!swapped) break;}}

例题：

#include <iostream>
#include <vector>
using namespace std;int BubbleSort(vector<int>& a,int n) {int swapped_num = 0;for (int i = 0;i < n - 1;i++) {// 判断是否提前结束bool swapped = false;for (int j = 0;j < n - 1 - i;j++) {if (a[j] > a[j + 1]) {swap(a[j], a[j + 1]);swapped_num++;swapped = true;}}// 如果内层循环没有再交换说明剩下的已经是有序的了，可提前结束if (swapped == false)break;}return swapped_num;
}int main()
{int n;int swapped_num;cin >> n;// 长度为变量，使用动态数组vector<int> a(n);for (int i = 0;i < n;i++)cin >> a[i];swapped_num = BubbleSort(a, n);cout << swapped_num;return 0;
}

8. 选择排序

• 时间复杂度：O($n^2$)
• 空间复杂度：O($1$)
• 稳定性：不稳定（对于[20,20,5]这种情况，第一个20会和5交换，从而到第二个20的后面。改变了相等值的前后顺序，故不稳定）

代码：

void SelectSort(vector<int>& a) {int n = a.size();for (int i = 0;i < n;i++) {int minIndex = i;for (int j = i + 1;j < n;j++) {if (a[j] < a[minIndex])minIndex = j;}swap(a[i], a[minIndex]);}
}

9. 插入排序

• 时间复杂度：O($n^2$)
• 空间复杂度：O($1$)
• 稳定性：稳定

代码：

void InsertSort(vector<int>& a) {for (int j = 1;j < a.size();j++) { //构造无序区for (int i = 0;i < j;i++) { //构造有序区if (a[j] < a[i]) {// 后移插入int tmp = a[j];for (int k = j - 1;k >= i;k--) {a[k + 1] = a[k];}a[i] = tmp;break; // 跳出有序区的循环}}}
}

10. 希尔排序（减小增量排序）

• 时间复杂度：最坏O($n^2$)、最好O($n$)、平均O($n^{1.5}$)
• 空间复杂度：O($1$)
• 稳定性：不稳定（例如：[20,20,10,30]排序后第一个20与10交换位置，故不稳定）

代码：

void ShellInsert(vector<int>& a, int start, int gap) {for (int j = start+gap;j < a.size();j+=gap) { //构造无序区for (int i = start;i < j;i+=gap) { //构造有序区if (a[j] < a[i]) {// 后移插入int tmp = a[j];for (int k = j - gap;k >= i;k-=gap) {a[k + gap] = a[k];}a[i] = tmp;break; // 跳出有序区的循环}}}
}void ShellSort(vector<int>& a) {for (int gap = a.size() / 2;gap >= 1;gap /= 2) {for (int i = 0;i < gap;i++) {ShellInsert(a, i, gap);}}
}

11. 计数排序

计数排序（Counting Sort）算法。这是一种非基于比较的排序算法，特别适用于对整数进行排序，尤其是当输入数据范围不是很大时，其性能表现非常出色。（简化版的桶排序）

• 时间复杂度：最坏O($n+k$)（其中 n 是待排序数组的元素数量，k 是输入数据中最大元素的值）
• 空间复杂度：O($k$)
• 稳定性：稳定

void CountSort(vector<int>& a) {// 1.找最大值int max = a[0];for (int i = 0;i < a.size();i++) {if (a[i] > max)max = a[i];}// 2.根据最大值开辟新数组vector<int> countArr(max + 1, 0);// 3.将原数据放入新数组中并计数for (int i = 0;i < a.size();i++) {countArr[a[i]]++;}// 4.按照下标依次取出计数数组中的下标a.clear();for (int i = 0;i < max + 1;i++) {while (countArr[i]) {a.push_back(i);countArr[i]--;}}
}

12. 桶排序

桶排序 （Bucket sort）是计数排序的升级版

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

• 时间复杂度：O($n+k$)
• 空间复杂度：O($n+k$)
• 稳定性：取决于桶内的排序是否稳定

void BucketSort(vector<int>& a) {// max_element 返回的是迭代器，因此需要解引用才能得到实际值int max = *max_element(a.begin(), a.end());int min = *min_element(a.begin(), a.end());// 求需要桶的数量（默认a.size为桶的容量）int bucketNum = ((max - min + 1) / a.size())+1;vector<vector <int>> Bucket(bucketNum);// 把元素放入对应的桶里for (int i = 0;i < a.size();i++) {int index = (a[i] - min + 1) / a.size();Bucket[index].push_back(a[i]);}// 对桶内元素进行排序(任意排序都行)for (int i = 0;i < Bucket.size();i++) {sort(Bucket[i].begin(), Bucket[i].end());}// 将各桶中元素按顺序遍历取出a.clear();for (int i = 0;i < Bucket.size();i++) {for (int j = 0;j < Bucket[i].size();j++) {a.push_back(Bucket[i][j]);}}
}