查看“︁05-算法模板/01-排序算法”︁的源代码


== 选择排序 ==

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

<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:三三文档]]