高精度&排序

2025年11月05日 4.3k 字大概 19 分钟

高精度

在此之前，我需要复习一下高精度，昨晚高精度算法写错了好多次。

高精度加法比较简单，将数组反转处理，将进位临时储存，需注意算法结束后还要验证最后进位是否为0。

#include<bits/stdc++.h>
#define int long long
using namespace std;
string add(string a, string b)
{
    int len = max(a.size(), b.size()), jw = 0;
    string c = "";
    while (a.size() < len) a = '0' + a;
    while (b.size() < len) b = '0' + b;
    for (int i = len - 1; i >= 0; i--)
    {
        int t1 = a[i] - '0', t2 = b[i] - '0';
        int t = t1 + t2 + jw;
        jw = t / 10;
        t %= 10;
        char ch = t + '0';
        c = ch + c;
    }
    if (jw != 0) return '1' + c;
    return c;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s1, s2;
	cin >> s1 >> s2;
	cout << add(s1, s2);
    return 0;
}

发现自己高精度乘法解释不清楚，这个高精度乘法题解写的很好，可以参考下。

然后我发现p1009不会做。
不是这高精算法怎么这么智障。
~~于是我决定跳过，之后再看。~~
还是看完了，其实并不难，题解写的很傻逼。
需要定义一个高精度加法，高精度乘以低精度乘法，再调用就好了。

#include <bits/stdc++.h>
using namespace std;
//高精度加法s1 s2 result均为倒叙储存
vector<int> add(vector<int> &s1,vector<int> &s2)
{
    vector<int> c;
    int len = max(s1.size(),s2.size());
    int temp=0;
    for (int i=0;i<len;i++)
    {
        int a,b;
        a=(i<s1.size())?s1[i] : 0;
        b=(i<s2.size())?s2[i] : 0;
        c.push_back((a+b+temp)%10);
        temp=(a+b+temp)/10;
    }
    if (temp>0) c.push_back(temp);
    return c;
}
//高精度乘以低精度乘法
vector<int> mul(vector<int>& a, int b) {
    vector<int> c;
    int temp = 0;
    for (int i = 0; i < a.size(); i++) {
        temp += a[i] * b;      
        c.push_back(temp % 10); 
        temp /= 10;            
    }
    while (temp) {
        c.push_back(temp % 10);
        temp /= 10;
    }
    if (c.empty()) {
        c.push_back(0);
    }
    return c;
}

//主函数调用
int main ()
{
    int n;
    cin>>n;
    vector<int> sum = {0}; 
    vector<int> term = {1};
    for(int i=1;i<=n;i++)
    {
        term = mul(term,i);
        sum = add(sum,term);
    }
    for (int i = sum.size() - 1; i >= 0; i--) {
        cout << sum[i];
    }
    cout << endl;
    return 0;
}

第一版代码编译错误。
我是不是有病
错误在s1.[i]，和结构体搞混了。
改好了就过了

好我们开始学习排序；

排序

计数排序

P1271 【深基9.例1】选举学生会，这道题理论来说是计数排序，我当时直接sort函数逃课了，现在再看一遍。

计数排序事实上是循环读取输入，然后在一个数组中记录每个数读取到的次数，再根据次数输出。

~~比较简单，且时间复杂度很高，感觉没什么用，下一个。~~

oiwiki上写了要计算前缀和，我并不太理解，接下来是gemini的解释：

这是一个非常好的问题！“前缀和”这一步是计数排序从一个简单的“计数”算法变成一个强大的“排序”算法的关键。

简单来说，前缀和的核心作用是：把“计数”转变为“最终位置”。

它解决了两个问题：

定位问题：知道有3个“5”，但我该把它们放在输出数组的哪个具体索引上？

稳定性问题：如果原始数组中有两个“5”（比如一个是 (5, 'a')，一个是 (5, 'b')），如何保证排序后它们的相对顺序不变？

1. 如果没有前缀和（朴素想法）
我们先看看，如果只有第一步“计算每个数出现了几次”，我们会怎么做。

假设待排序数组 A = {1, 4, 1, 2, 4, 3, 1}

步骤 1：计数
我们得到一个“计数数组” C：

C[1] = 3 (有 3 个 ‘1’)

C[2] = 1 (有 1 个 ‘2’)

C[3] = 1 (有 1 个 ‘3’)

C[4] = 2 (有 2 个 ‘4’)

朴素的“排序”：
我们可以遍历 C 数组，然后直接重写 A：

看到 C[1] = 3，就在 A 里写 3 个 ‘1’：A = {1, 1, 1, ...}

看到 C[2] = 1，接着写 1 个 ‘2’：A = {1, 1, 1, 2, ...}

…

最终得到 A = {1, 1, 1, 2, 3, 4, 4}

问题所在：
这确实排序了。但是，如果我们的 A 数组存的不是简单的数字，而是对象呢？
比如 A = {(1, 'a'), (4, 'b'), (1, 'c'), (4, 'd'), (1, 'e')}
我们的 C 数组还是一样：C[1]=3，C[4]=2。
如果用朴素方法，我们只会得到 {1, 1, 1, 4, 4}。我们完全丢失了 ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ 这些附加信息。

我们需要的不是“覆盖”原数组，而是把原数组中的每一个元素，“搬运” 到一个新数组（或最终位置）的正确索引上。

2. 前缀和的作用：计算“位置边界”
前缀和就是用来计算这个“搬运”目标的。

我们换一个例子：A = {2, 5, 3, 0, 2, 3, 0, 3}

步骤 1：计数
C 数组 (索引 0 到 5):

C[0] = 2 (2 个 ‘0’)

C[1] = 0 (0 个 ‘1’)

C[2] = 2 (2 个 ‘2’)

C[3] = 3 (3 个 ‘3’)

C[4] = 0 (0 个 ‘4’)

C[5] = 1 (1 个 ‘5’)

数组 C：{2, 0, 2, 3, 0, 1}

步骤 2：计算前缀和
我们对 C 数组进行累加：

C[0] = 2

C[1] = C[1] + C[0] = 0 + 2 = 2

C[2] = C[2] + C[1] = 2 + 2 = 4

C[3] = C[3] + C[2] = 3 + 4 = 7

C[4] = C[4] + C[3] = 0 + 7 = 7

C[5] = C[5] + C[4] = 1 + 7 = 8

数组 C（前缀和）：{2, 2, 4, 7, 7, 8}

现在，这个前缀和数组 C 的含义变得非常重要：
C[i] 的值 = 原始数组中 小于或等于 i 的元素总个数。

C[0] = 2：有 2 个元素 $\le 0$。

C[2] = 4：有 4 个元素 $\le 2$ (即 ‘0’ 和 ‘2’)。

C[3] = 7：有 7 个元素 $\le 3$ (即 ‘0’, ‘2’ 和 ‘3’)。

C[5] = 8：有 8 个元素 $\le 5$ (即所有元素)。

这就是关键点！

如果有 4 个元素小于或等于 2，那么在排好序的数组（假设 1-based 索引）中，最后一个 ‘2’ 应该放在第 4 位。

如果有 7 个元素小于或等于 3，那么最后一个 ‘3’ 应该放在第 7 位。

C[i] 现在直接告诉了我们：值 i 的元素在排序后，最后一个应该放的“坑位”是第 C[i] 个。

3. 步骤 3：利用前缀和（从后往前）放置元素
我们准备一个和 A 一样大的空数组 B (大小为 8)。
我们从右至左（从后往前）遍历原始数组 A。

A = {2, 5, 3, 0, 2, 3, 0, 3}
C = {2, 2, 4, 7, 7, 8} (前缀和)
B = {_, _, _, _, _, _, _, _}

遍历 A[7] = 3

查找 C[3]，值为 7。

这告诉我们：’3’ 应该放在第 7 个位置（即 0-based 索引的 7-1 = 6）。

B[6] = 3。

重要：我们用掉了一个 ‘3’ 的位置，所以 C[3] 减 1。C[3] 变为 6。

B：{_, _, _, _, _, _, 3, _}

遍历 A[6] = 0

查找 C[0]，值为 2。

位置：2-1 = 1。

B[1] = 0。

C[0] 减 1，变为 1。

B：{_, 0, _, _, _, _, 3, _}

遍历 A[5] = 3 (这是第二个 ‘3’)

查找 C[3]，值现在是 6 (上次用过 ‘3’ 后减 1 了)。

位置：6-1 = 5。

B[5] = 3。

C[3] 减 1，变为 5。

B：{_, 0, _, _, _, 3, 3, _}

遍历 A[4] = 2

查找 C[2]，值为 4。

位置：4-1 = 3。

B[3] = 2。

C[2] 减 1，变为 3。

B：{_, 0, _, 2, _, 3, 3, _}

… 以此类推，直到 A[0]。

遍历 A[2] = 3 (这是第一个 ‘3’)

查找 C[3]，值现在是 5。

位置：5-1 = 4。

B[4] = 3。

C[3] 减 1，变为 4。

B：{_, 0, _, 2, 3, 3, 3, _}

最后我们会得到 B = {0, 0, 2, 2, 3, 3, 3, 5}，排序完成。

总结
前缀和是计数排序的灵魂，它完成了两个核心任务：

精确
定位：C[i] 从“i 的个数”转变成了“小于等于 i 的总数”，这个总数直接映射到了排序后数组的索引（位置）。

保证稳定性：通过从后往前遍历原数组 A，并结合 C[i]-- 操作，我们确保了：

原数组中靠后的重复元素，会先被放入新数组中靠后的“坑位”。

原数组中靠前的重复元素，会后被放入新数组中靠前的“坑位”。

从而保持了它们的相对顺序不变（即“稳定性”）。

我理解了什么意思了，但是怎么这么繁琐。。。
我可能之后还是不记得这个前缀和怎么用，不过至少了解了，先写个代码熟悉一下。

#include <bits/stdc++.h>
using namespace std;
vector<int> count_sort(vector<int> &s1,int n)//需要输入的数组，里面的最大数（默认从0开始排序）
{   
    vector<int> c (n+1,0);//初始化计数数组；
    //遍历计数
    int leng=s1.size();
    for (int i=0;i<leng;i++) c[s1[i]]++;
    //计算前缀和；
    for (int i=1;i<n+1;i++) c[i]+=c[i-1];
    //将c数组里的每一个数替换成前缀和
    
    //定义输出数组
    vector<int> result(leng);
    //利用前缀和（从后往前）放置元素
    for (int i = leng-1;i>=0;--i)
    {
        int num = s1[i];//查找第i元素
        int postion=c[num]-1;//查找这个元素应该放在第几个位置
        /*这就是前缀和的作用，即这个元素和小于这个元素的一共有几个
        那么这个数减一就是应该放在结果数组的位置
        */
        result[postion]=num;
        c[num]--;//用掉了一个数，应该减一

    }
    return result;

}

选择排序

oi wiki的选择排序解释的特别清楚，即找到第i小的数字，并将其与第i位数交换

#include <utility>

void selection_sort(int* a, int n) {
  for (int i = 1; i < n; ++i) {
    int ith = i;
    for (int j = i + 1; j <= n; ++j) {
      if (a[j] < a[ith]) {
        ith = j;
      }
    }
    std::swap(a[i], a[ith]);
  }
}

如果再解释地清楚一点，就是从第i位开始遍历后面的数组，找到其中最小的数字并且与第i位数字交换。
本质上是打擂台，找到最小的数字，排在最前面。

冒泡排序

这个其实更加简单，即循环遍历相邻的两个数，使他们正向排序。
当不再发生交换的时候，排序完成。

void bubble_sort (int *a,int n)
{
    bool switched = true;//switched表示上一轮是否交换
    /*这是个断终止的方法，只要上一轮没有交换说明排序结束*/
    while (switched)
    {
        switched = false;
        for(int i=0;i<n-1;++i)//注意数组越界问题，应当要再减一
        {
            if (a[i] > a[i + 1]) 
            {
                switched = true;
                swap(a[i],a[i+1]);
            }
        }
    }
}

插入排序

把数组分为排序区和非排序区，然后一个个把非排序区的第一个元素插入进排序区。

可数组的插入不是很复杂的吗？？

代码实现如下

void insertion_sort(int arr[], int len) {
  for (int i = 1; i < len; ++i) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

这是gemini的解释，我觉得很形象

它的核心思想是模拟我们玩扑克牌时整理手牌的动作。

🃏 插入排序的核心比喻 (整理手牌)
想象一下，你左手拿着一副已经（部分）排好序的牌，右手刚抽到一张新牌（key）。

你会怎么做？

你从左手中最右边的牌（j）开始，和你的新牌（key）比较。

如果左手的牌（arr[j]）比你的新牌（key）大，你就把这张牌往右移一个位置（arr[j + 1] = arr[j]），腾出它原来的空位。

你继续看左手边下一张牌（j--），重复这个比较。

直到你找到一张比新牌（key）小的牌，或者你已经比较完了所有手里的牌 ( j < 0 )。

这时，你找到了正确的位置，把你手里的新牌（key）插入到刚刚腾出来的那个空位上（arr[j + 1] = key）。

如果基本有序，就可以使用这个插入算法。

不是我看到这里和我说这些算法时间复杂度太差了，不怎么用。

至少下一个排序很有用

快速排序

洛谷P1177就是一道快速排序题，上次我没有做对也没有理解，今天再做一次。

不行了这个gemini讲的太好了,我直接复制就行

您可以把快速排序想象成一个“不断找人站队”的过程。

快速排序的核心思想

正如您资料中提到的，它的核心是 “分治”（Divide and Conquer）。

简单来说，就是：

找一个“基准” (Pivot)： 在队伍里（数组中）随便挑一个人（一个数）当“基准”。
站队 (Partition)： 以这个基准为标准，让所有比他“小”的站到他左边，所有比他“大”的站到他右边。这个基准自己会站在中间的某个位置。
分而治之 (Recurse)： 现在队伍被分成了“左队”和“右队”。我们对“左队”和“右队”分别重复第1步和第2步。
完成： 当所有人都“分无可分”（即每个小队都只剩一个人或0个人）时，整个队伍（数组）就自然排好序了。

详细解释您提供的 C++ 代码

您提供的代码是实现这个过程的经典方法。我们一步一步来看：

1. `Partition` 函数（最关键的“站队”过程）

这个函数的目标是：选定一个基准，并完成“站队”。

template <typename T>
int Partition(T A[], int low, int high) {//这里low是排序的第一个指针， high是最后一个指针
  int pivot = A[low]; // 1. 选择基准：就选第一个元素当基准 (pivot)
                      //    此时 A[low] 这个位置可以看成一个“坑”

  while (low < high) { // 2. 只要左右指针没相遇，就继续
    
    // 3. 从右往左找“小”的
    while (low < high && pivot <= A[high]) --high; 
    A[low] = A[high]; // 4. 找到一个比基准小的，扔到左边的“坑”里。A[high] 成了新“坑”

    // 5. 从左往右找“大”的
    while (low < high && A[low] <= pivot) ++low; 
    A[high] = A[low]; // 6. 找到一个比基准大的，扔到右边的“坑”里。A[low] 成了新“坑”
  }
  
  // 7. 循环结束，low 和 high 相遇了
  A[low] = pivot; // 8. 把一开始存的基准值，放回这个最后的“坑”
  return low;     // 9. 返回基准最后站的位置
}

用一个例子来模拟 Partition：
假设数组是 [5, 2, 8, 1, 9, 4]，low = 0, high = 5。

pivot = A[low]，pivot 存了 5。 A[0] 现在是“坑”。
数组：[坑, 2, 8, 1, 9, 4]
从右往左（high 从 5 开始）找比 5 小的。
- A[5] 是 4。比 5 小。
把 4 扔到左边的“坑” (A[low] 即 A[0])。A[5] 变成新“坑”。
数组：[4, 2, 8, 1, 9, 坑]
从左往右（low 从 0 开始）找比 5 大的。
- A[0] 是 4。
- A[1] 是 2。
- A[2] 是 8。比 5 大。
把 8 扔到右边的“坑” (A[high] 即 A[5])。A[2] 变成新“坑”。
数组：[4, 2, 坑, 1, 9, 8]
从右往左（high 从 5 开始）…
- … A[4] 是 9。
- A[3] 是 1。比 5 小。
把 1 扔到左边的“坑” (A[low] 即 A[2])。A[3] 变成新“坑”。
数组：[4, 2, 1, 坑, 9, 8]
从左往右（low 从 2 开始）…
- A[2] 是 1。
- A[3]… low 和 high 在 3 这个位置相遇了。循环 while (low < high) 结束。
把 pivot (存的 5) 放到 A[low] (即 A[3])。
数组：[4, 2, 1, 5, 9, 8]
返回 low (即 3)。

看，现在数组变成了 [4, 2, 1] （都比5小） | 5 | [9, 8] （都比5大）。 这就是“站队”！

2. `QuickSort` 函数（“分而治之”的递归）

这个函数是“分治”思想的体现，它来“指挥”Partition。

template <typename T>
void QuickSort(T A[], int low, int high) {
  if (low < high) { // 如果队伍里至少有2个人
    // 1. 先站队，并拿到基准最后的位置
    int pivot_pos = Partition(A, low, high); 
    
    // 2. 指挥“左队”去递归排序
    QuickSort(A, low, pivot_pos - 1); 
    
    // 3. 指挥“右队”去递归排序
    QuickSort(A, pivot + 1, high); 
  }
  // 如果 low >= high (队伍里只有1个人或0个人)，自然就是有序的，不用管了。
}

总结

QuickSort 函数是宏观管理者：它负责“分”，决定对哪一段（从 low 到 high）进行排序。
Partition 函数是具体执行者：它负责“治”，在一段里选个基准，把队伍分成“左队”和“右队”。
通过递归，宏观管理者不断地把任务（大队伍）拆分成更小的任务（小队伍），直到任务小到不需要再拆分（队伍里只有一个人），整个排序就完成了。

您提供的资料中提到“不用合并”，就是因为 Partition 这一步已经保证了“左队”所有的数都小于“右队”，所以当两队各自排好序后，合起来自然就是有序的。

后面还有优化算法，我真不想看了，之后有空再看。

归并排序

我草怎么还有。。。
直接放归并的链接吧

总结

其实还有sort函数，要写一个函数作为排序的算法。
我感觉我这样学习效率很低，应该做题，不会的再去查概念。
先去吃个饭，等下学递归的时候改一下学习方法。

高精度&排序

高精度

排序

计数排序

1. 如果没有前缀和（朴素想法）

2. 前缀和的作用：计算“位置边界”

3. 步骤 3：利用前缀和（从后往前）放置元素

总结