利用稳定排序算法

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int b[1005];
bool cmp(int x, int y)
{
    return a[x] <= a[y];
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = i;
    }
    //用冒泡排序对下标排序
    for (int i = 1; i <= n - 1; i++)
        for (int j = 1; j <= n - 1; j++)
            if (!cmp(b[j], b[j + 1]))
            {
                swap(b[j], b[j + 1]);
            }
    for (int i = 1; i <= n; i++)
        cout << b[i] << " ";
    return 0;
}

利用普通排序算法增加关键字

朴素模式

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int b[1005];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = i;
    }
    //用选择排序对下标排序
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[b[j]] < a[b[i]] || 
                (a[b[j]] == a[b[i]] && b[j] < b[i]))
                swap(b[i], b[j]);
    for (int i = 1; i <= n; i++)
        cout << b[i] << " ";
    return 0;
}

比较函数模式

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int b[1005];
bool cmp(int x, int y)
{
    if (a[x] < a[y])
        return true;
    if (a[x] == a[y] && x < y)
        return true;
    return false;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = i;
    }
    //用选择排序对下标排序
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (!cmp(b[i], b[j]))
                swap(b[i], b[j]);
    for (int i = 1; i <= n; i++)
        cout << b[i] << " ";
    return 0;
}

使用不稳定的sort函数进行排序

#include <bits/stdc++.h>
using namespace std;
int n;
struct Num{
    int a,id;
};
Num arr[1005];
bool cmp(Num x, Num y)
{
    if (x.a != y.a)
        return x.a < y.a;
    else
        return x.id < y.id;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i].a;
        arr[i].id = i;
    }
    sort(arr + 1, arr + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        cout << arr[i].id << " ";
    return 0;
}

使用稳定的 stable_sort 函数进行排序

#include <bits/stdc++.h>
using namespace std;
int n;
struct Num{
    int a,id;
};
Num arr[1005];
bool cmp(Num x, Num y)
{
    return x.a < y.a;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i].a;
        arr[i].id = i;
    }
    stable_sort(arr + 1, arr + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        cout << arr[i].id << " ";
    return 0;
}