🔥Flumina Blog

主题

00:00:00
🔥Flumina2026-08-11 22:37:002026-08-12 01:14:54算法笔记算法笔记C++Algorithm
1452
7.2m
0

1 数组赋初值 ​

1、memset的用法 ​

memset函数的格式为：

cpp
memset(数组名，值，sizeof(数组名))

举例：

cpp
#include<cstring>
int N = 10;
int a;
memset(a, 0, sizeof(a));
memset(a, -1, sizeof(a));

IMPORTANT

memset 按单字节填充内存，而非按 int 变量整体赋值，函数第二个参数仅保留低8位字节，逐字节覆盖内存。由于数值0、-1的二进制补码分别为全0、全1，逐字节填充后，完整的int数值仍为0和-1，因此memset通常用于给整型数组赋初值0和-1。

2、fill的用法 ​

fill函数的格式为：

cpp
#include<algorithm>
int N = 10;
int a[N];
fill(a, a + N , 8);

IMPORTANT

fill支持赋予任何值

2、各种排序时间复杂度对比 ​

cpp
/*对比七种排序算法的时间复杂度*/

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
using namespace std::chrono;

const int MAXN = 1e7 + 10;
int n;
int nums[MAXN];  // 原始输入数组（每次复制用）
int arr[MAXN];   // 工作数组
int temp[MAXN];  // 归并排序辅助数组
void InsertSort(int start, int end) {
  for (int i = start + 1; i <= end; i++) {
    if (nums[i] < nums[i - 1]) {
      int j = i - 1, temp = nums[i];
      while (j >= start && nums[j] > temp) {
        nums[j + 1] = nums[j];
        j--;
      }
      nums[j + 1] = temp;
    }
  }
}
void ShellSort(int start, int end) {
  int k = 3, gap = 1;
  while (gap <= n) { gap = gap * k + 1; }
  gap /= k;
  while (gap >= 1) {
    for (int i = start + gap; i <= end; i++) {
      if (nums[i] < nums[i - gap]) {
        int j = i - gap, temp = nums[i];
        while (j >= start && nums[j] > temp) {
          nums[j + gap] = nums[j];
          j -= gap;
        }
      }
    }
    gap /= k;
  }
}
void BubbleSort(int start, int end) {
  bool flag = true;
  for (int i = start; i < end; i++) {
    flag = false;
    for (int j = end; j > i; j--) {
      if (nums[j] < nums[j - 1]) {
        flag = true;
        swap(nums[j], nums[j - 1]);
      }
    }
    if (!flag) { break; }
  }
}
void QuickSort(int start, int end) {
  if (start >= end) { return; }
  int pivot = nums[start + ((end - start) >> 1)];
  int i = start - 1, j = end + 1;
  while (i < j) {
    while (nums[++i] < pivot);
    while (nums[--j] > pivot);
    if (i < j) { swap(nums[i], nums[j]); }
  }
  QuickSort(start, j);
  QuickSort(j + 1, end);
}
void SelectSort(int start, int end) {
  for (int i = start; i < end; i++) {
    int k = i;
    for (int j = i + 1; j <= end; j++) {
      if (nums[j] < nums[k]) { k = j; }
    }
    if (k != i) { swap(nums[i], nums[k]); }
  }
}
// 大顶堆
void HeapAdjust(int k, int end) {
  int temp = nums[k];
  for (int i = 2 * k + 1; i <= end; i = 2 * i + 1) {
    if (i < end && nums[i] < nums[i + 1]) { i++; }
    if (nums[i] < temp) {
      break;
    } else {
      nums[k] = nums[i];
      k = i;
    }
  }
  nums[k] = temp;
}
void BuildHeap(int start, int end) {
  for (int i = (end - 1) / 2; i >= start; i--) { HeapAdjust(i, end); }
}
void HeapSort(int start, int end) {
  BuildHeap(start, end);
  for (int i = end; i > start; i--) {
    swap(nums[i], nums[start]);
    HeapAdjust(start, i - 1);
  }
}

void Merge(int l1, int r1, int l2, int r2) {
  int i = l1, j = l2;
  int k = 0;
  while (i <= r1 && j <= r2) {
    if (nums[i] < nums[j]) {
      temp[k++] = nums[i++];
    } else {
      temp[k++] = nums[j++];
    }
  }
  while (i <= r1) { temp[k++] = nums[i++]; }
  while (j <= r2) { temp[k++] = nums[j++]; }
  for (int i = 0; i < k; i++) { nums[l1 + i] = temp[i]; }
}
void MergeSort(int start, int end) {
  if (start < end) {
    int mid = start + ((end - start) >> 1);
    MergeSort(start, mid);
    MergeSort(mid + 1, end);
    Merge(start, mid, mid + 1, end);
  }
}
// 验证数组是否有序
bool isSorted(int* a, int n) {
  for (int i = 1; i < n; i++) {
    if (a[i] < a[i - 1]) return false;
  }
  return true;
}

// 打印数组（调试用）
void printArray(const char* name, int* a, int len) {
  printf("%s: ", name);
  for (int i = 0; i < min(len, 20); i++) { printf("%d ", a[i]); }
  if (len > 20) printf("...");
  printf("\n");
}
// 测试单个排序算法并计时
template <typename Func>
void testSort(const char* name, Func sortFunc, bool printResult = false) {
  copy(nums, nums + n, nums);  // 每次从原始备份复制

  auto start = high_resolution_clock::now();
  sortFunc(0, n - 1);
  auto stop = high_resolution_clock::now();

  auto duration = duration_cast<microseconds>(stop - start);
  double timeMs = duration.count() / 1000.0;

  printf("%-12s: %8.3f ms", name, timeMs);
  if (isSorted(nums, n)) {
    printf(" [OK]\n");
  } else {
    printf(" [FAILED]\n");
  }

  if (printResult) { printArray("Sorted", nums, n); }
}

int main() {
  srand(time(0));  // 随机种子

  cout << "请输入数组长度 N (建议 <= " << MAXN - 10 << "): ";
  cin >> n;

  if (n <= 0 || n >= MAXN) {
    cerr << "N 超出范围！\n";
    return 1;
  }

  // 随机生成数组
  cout << "\n正在生成 " << n << " 个随机数...\n";
  for (int i = 0; i < n; i++) {
    nums[i] = rand() % 10000;  // 0~9999
  }

  // 可选：打印前几个数
  // printArray("Original", nums, n);

  cout << "\n开始测试各排序算法耗时...\n\n";

  // 分别测试每种排序
  testSort("InsertSort", InsertSort);
  testSort("ShellSort", ShellSort);
  testSort("BubbleSort", BubbleSort);
  testSort("QuickSort", QuickSort);
  testSort("SelectSort", SelectSort);
  testSort("HeapSort", HeapSort);
  testSort("MergeSort", MergeSort);

  cout << "\n测试完成。\n";

  return 0;
}

3、c++中的最大值 ​

代码：

cpp
#include <iostream>  
#include <climits>  
using namespace std;
const int N = 1e8 + 5;
int a[N];
int main() {
    cout << "有符号整数的最大值: " << INT_MAX << endl;
    cout << "无符号整数的最大值: " << UINT_MAX << endl;
    cout << "长整型整数的最大值: " << LONG_MAX << endl;
    cout << "无符号长整数的最大值: " << ULONG_MAX << endl;
    cout << "有符号长长整数的最大值: " << LLONG_MAX << endl;
    cout << "无符号长长整数的最大值: " << ULLONG_MAX << endl;
    return 0;
}
/*
有符号整数的最大值: 2147483647
无符号整数的最大值: 4294967295
长整型整数的最大值: 2147483647
无符号长整数的最大值: 4294967295
有符号长长整数的最大值: 9223372036854775807
无符号长长整数的最大值: 18446744073709551615
*/

对于要想在主函数外边定义固定长度的数组，长度为 const int N = 1e8 + 5，这是最大值了。

4、cout 输出浮点数 ​

c++中使用cout输出浮点数默认保留6位有效位数。

5、C++中 一个类中定义常量 ​

cpp
class Solution {
public:
    static constexpr int N = 8002;
    static int arr[N];
    void Method() {}
}

6、配置vscode ​

对于C/C++项目，要实现函数的开括号 { 与函数声明在同一行。这是最灵活和项目友好的方式。

  1. 在你的项目根目录创建 .clang-format 文件。
    • 你可以直接在 VS Code 中右键点击项目文件夹，选择“新建文件”，并命名为 .clang-format。
  2. 编辑 .clang-format 文件，添加以下内容：

第一种风格：

# .clang-format

# 指定语言风格
Language: Cpp

# 设置缩进宽度
IndentWidth: 4

# 设置制表符宽度
TabWidth: 4

# 使用空格而不是制表符 (可选)
UseTab: Never

# 最重要的设置：控制大括号的放置
BreakBeforeBraces: Attach # 这是关键！将开括号 { 附着在上一行末尾

# 其他常见选项 (可根据喜好调整)
AllowShortFunctionsOnASingleLine: Inline
IndentCaseLabels: true

第二种风格：

BasedOnStyle: Google
BreakBeforeBraces: Attach
AllowShortFunctionsOnASingleLine: All
AllowShortBlocksOnASingleLine: true

7、C++输入输出加速 ​

cpp
// 在 main 函数开头加入
ios::sync_with_stdio(false);
cin.tie(nullptr);
最近更新