33DAI：导入1个版本

2026-05-20T18:12:10Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:32Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 选择排序 ==

每次选出最小的放到前面。

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
using namespace std;
int n, a[1005];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[j] < a[i])
swap(a[j], a[i]);
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
return 0;
}
</syntaxhighlight>

== 冒泡排序 ==

相邻两个比较，大的往后沉。

<syntaxhighlight lang="cpp">
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= n - i; j++)
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
</syntaxhighlight>

优化：如果一轮没有交换，说明已经有序。

<syntaxhighlight lang="cpp">
for (int i = 1; i <= n - 1; i++)
{
bool flag = false;
for (int j = 1; j <= n - i; j++)
if (a[j] > a[j + 1])
{
swap(a[j], a[j + 1]);
flag = true;
}
if (!flag)
break;
}
</syntaxhighlight>

== 插入排序 ==

每次将一个新元素插入到已排序的部分。

<syntaxhighlight lang="cpp">
for (int i = 2; i <= n; i++)
for (int j = i; j >= 2; j--)
if (a[j] < a[j - 1])
swap(a[j], a[j - 1]);
</syntaxhighlight>

== 计数排序 ==

适用于值域较小的整数排序。

<syntaxhighlight lang="cpp">
int cnt[2005] = {0};
for (int i = 1; i <= n; i++)
cnt[a[i]]++;
for (int i = 1; i <= 2000; i++)
for (int j = 1; j <= cnt[i]; j++)
cout << i << " ";
</syntaxhighlight>

== 地精排序 ==

<syntaxhighlight lang="cpp">
int pos = 1;
while (pos != n)
{
if (a[pos] <= a[pos + 1])
pos++;
else
{
swap(a[pos], a[pos + 1]);
if (pos != 1)
pos--;
}
}
</syntaxhighlight>

== STL <code>sort</code> ==

<syntaxhighlight lang="cpp">
sort(a + 1, a + n + 1); // 升序 [1, n]
sort(a + 1, a + n + 1, greater<int>()); // 降序
sort(a + 1, a + n + 1, cmp); // 自定义比较函数
</syntaxhighlight>

=== 自定义比较函数 ===

<syntaxhighlight lang="cpp">
bool cmp(int a, int b)
{
return a > b; // 降序
}
</syntaxhighlight>

=== 对结构体排序 ===

<syntaxhighlight lang="cpp">
struct Student { int score, id; };

bool cmp(const Student &a, const Student &b)
{
if (a.score != b.score)
return a.score > b.score; // 分数高在前
return a.id < b.id; // 分数相同，id 小在前
}
</syntaxhighlight>

=== 时间复杂度 ===

- STL <code>sort</code>：<math>O(n\log n)</math>
- 选择/冒泡/插入：<math>O(n^2)</math>
- 计数排序：<math>O(n + \text{值域})</math>

[[Category:算法模板]]
[[Category:三三文档]]

05-算法模板/01-排序算法 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档