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
27
28
29
30
31
32

#include <iostream>
#include <algorithm>
#include <vector>

void quick_sort(std::vector<int>& nums, int l, int r);
void merge_sort(std::vector<int>& nums, int l, int r);
void select_sort(std::vector<int>& nums);
void insert_sort(std::vector<int>& nums);
void binary_sort(std::vector<int>& nums);
void bubble_sort(std::vector<int>& nums);

int main()
{
  int n;
  scanf("%d", &n);

  std::vector<int> nums(n);
  for (int i = 0; i < n; ++ i)
    scanf("%d", &nums[i]);

  quick_sort(nums, 0, n - 1);
  merge_sort(nums, 0, n - 1);
  select_sort(nums);
  insert_sort(nums);
  binary_sort(nums);
  bubble_sort(nums);

  for (int i = 0; i < n; ++ i)
    printf("%d ", nums[i]);

  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void quick_sort(std::vector<int>& nums, int l, int r)
{
  if (l >= r) return;  // 递归终止条件

  int i = l - 1, j = r + 1, x = nums[(l + r) >> 1]; // 取中间值作为基准
  while (i < j)
  {
    do ++i; while (nums[i] < x); // 找到左侧大于等于 pivot 的元素
    do --j; while (nums[j] > x); // 找到右侧小于等于 pivot 的元素
    if (i < j)
      std::swap(nums[i], nums[j]); // 交换不符合条件的元素
  }

  quick_sort(nums, l, j);   // 递归排序左半部分
  quick_sort(nums, j + 1, r); // 递归排序右半部分
}

 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
27
28

void merge_sort(std::vector<int>& nums, int l, int r)
{
  if (l >= r) return;  // 递归终止条件：子数组长度为1

  int mid = (l + r) >> 1;  // 取中间点
  merge_sort(nums, l, mid);  // 递归排序左半部分
  merge_sort(nums, mid + 1, r);  // 递归排序右半部分

  std::vector<int> tmp(nums.size());  // 临时数组用于合并
  int i = l, j = mid + 1, k = 0;  // i 遍历左半部分，j 遍历右半部分

  // 归并两个有序子数组
  while (i <= mid && j <= r)
  {
    if (nums[i] <= nums[j])
      tmp[k++] = nums[i++];  // 选较小的数加入临时数组
    else
      tmp[k++] = nums[j++];
  }

  // 处理剩余元素
  while (i <= mid) tmp[k++] = nums[i++];
  while (j <= r) tmp[k++] = nums[j++];

  // 复制回原数组
  for (int i = l, k = 0; i <= r; ++i, ++k)
    nums[i] = tmp[k];
}

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include <iostream>
#include <algorithm>
#include <vector>

// 维护小根堆性质 (较大值向下调整)
void big_down(std::vector<int>& nums, int u, int sz)
{
    int t = u;
    if (u * 2 <= sz && nums[t] > nums[u * 2])  // 左子节点较小
        t = u * 2;
    if (u * 2 + 1 <= sz && nums[t] > nums[u * 2 + 1])  // 右子节点较小
        t = u * 2 + 1;

    if (t != u)  // 需要交换
    {
        std::swap(nums[t], nums[u]);
        big_down(nums, t, sz);  // 递归调整
    }
}

// 维护大根堆性质 (较小值向下调整)
void small_down(std::vector<int>& nums, int u, int sz)
{
    int t = u;
    if (u * 2 <= sz && nums[t] < nums[u * 2])  // 左子节点较大
        t = u * 2;
    if (u * 2 + 1 <= sz && nums[t] < nums[u * 2 + 1])  // 右子节点较大
        t = u * 2 + 1;

    if (t != u)  // 需要交换
    {
        std::swap(nums[t], nums[u]);
        small_down(nums, t, sz);  // 递归调整
    }
}

int main()
{
    int n;
    scanf("%d", &n);

    // 下标从1开始存储堆，避免叶子结点边界处理
    std::vector<int> nums(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &nums[i]);
    }

    // 建堆 (从最后一个非叶子节点开始)
    for (int i = n / 2; i >= 1; --i)
    {
        big_down(nums, i, n);
    }

    int sz = n;
    // 堆排序
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", nums[1]);  // 输出堆顶元素
        std::swap(nums[1], nums[sz]);  // 交换堆顶和堆尾元素
        -- sz;  // 缩小堆的范围
        big_down(nums, 1, sz);  // 重新调整堆
    }
    printf("\n");

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void select_sort(std::vector<int>& nums)
{
  for (int i = 0; i < nums.size() - 1; ++i)
  {
    int min_idx = i;  // 记录当前最小值的索引
    for (int j = i + 1; j < nums.size(); ++j)
      if (nums[min_idx] > nums[j])  // 找到更小的元素
        min_idx = j;

    std::swap(nums[i], nums[min_idx]);  // 交换当前元素与最小值
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void insert_sort(std::vector<int>& nums)
{
  for (int i = 1; i < nums.size(); ++ i)  // 从第二个元素开始
  {
    int x = nums[i], j = i;  // 保存当前元素并从当前位置开始向前检查
    while (j >= 1 && x < nums[j - 1])  // 查找插入位置
    {
      nums[j] = nums[j - 1];  // 向右移动元素
      -- j;  // 移动索引
    }
    nums[j] = x;  // 插入当前元素
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void binary_sort(std::vector<int>& nums)
{
  for (int i = 1; i < nums.size(); ++ i)  // 从第二个元素开始
  {
    if (nums[i - 1] < nums[i])  // 如果当前元素比前一个元素大，则跳过
      continue;

    int x = nums[i];  // 保存当前元素
    int l = 0, r = i - 1;  // 设置二分查找的左右边界

    while (l < r)  // 二分查找插入位置
    {
      int mid = (l + r) >> 1;
      if (x < nums[mid])
        r = mid;  // 当前元素小于mid，右边界左移
      else
        l = mid + 1;  // 当前元素大于mid，左边界右移
    }

    for (int j = i - 1; j >= r; -- j)  // 移动元素
      nums[j + 1] = nums[j];
    nums[r] = x;  // 插入当前元素到正确的位置
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void bubble_sort(std::vector<int>& nums)
{
  for (int i = 0; i < nums.size() - 1; ++ i) // 外层循环控制排序的轮数
  {
    bool is_swap = false; // 用于检查是否发生交换
    for (int j = nums.size() - 1; j > i; -- j) // 内层循环进行元素的比较与交换
    {
      if (nums[j] < nums[j - 1]) // 如果前一个元素大于后一个元素
      {
        std::swap(nums[j], nums[j - 1]); // 交换元素
        is_swap = true; // 标记发生了交换
      }
    }

    if (!is_swap) // 如果没有发生交换，说明数组已经有序，可以提前结束
      break;
  }
}