05-算法模板/01-排序算法

选择排序

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

#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;
}

冒泡排序

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

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]);

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

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;
}

插入排序

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

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]);

计数排序

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

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 << " ";

地精排序

int pos = 1;
while (pos != n)
{
    if (a[pos] <= a[pos + 1])
        pos++;
    else
    {
        swap(a[pos], a[pos + 1]);
        if (pos != 1)
            pos--;
    }
}

STL sort

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

自定义比较函数

bool cmp(int a, int b)
{
    return a > b; // 降序
}

对结构体排序

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 小在前
}

时间复杂度

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