sort是不稳定排序

一道题调了一周，今天终于调过了……
题目不算很难写，就是poj1007的DNA sorting，字符串求逆序数然后升序排序。
之前交的代码是这样的：

#include<iostream>
#include<algorithm>
using namespace std;

typedef struct node {
    char str[55];
    int num;
} Node;

bool cmp(Node a, Node b) {
    return a.num < b.num;
}

int main() {
    int n = 0, m = 0;
    while(scanf("%d %d", &n, &m) == 2) {
        Node s[105];
        for(int i = 0; i < m; i++) {
            scanf("%s", s[i].str);
            s[i].num = 0;
            for(int j = 0; j < n - 1; j++) {
                if(s[i].str[j] == 'A') continue;
                for(int k = j + 1; k < n; k++) {
                    if(s[i].str[k] < s[i].str[j]) s[i].num++;
                }
            }
        }
        sort(s, s + m, cmp); // 这里用的是sort排序
        for(int i = 0; i < m; i++) printf("%s\n", s[i].str);
        printf("********************\n");
    }
    return 0;
}

实际上在poj上是可以过的。但是在我的oj上一直会WA一个点。今天终于发现是因为sort排序其实是不稳定的！！！

排序的稳定性

如果排序前后，相等的两个元素的相对位置发生了互换，就称这个排序是不稳定的。

sort

sort排序其实是结合了快速排序、堆排序和插入排序。当元素太少时会用插入排序，深度太大时会使用堆排序。
因为插入排序是稳定的，所以当我只输入5个字符串的时候是不会乱掉的。
但当我输入100个相同字符串，效果如下：

可以从后面那列数字（输入时按顺序标的）看出，此时已经乱掉了。
但是如果我用stable_sort()，效果马上就不一样了：

也可以通过修改sort参数的方法来实现稳定排序：

这样就可以实现当排序因素相等时，把先输入的放在前面了，也就是稳定排序。

快排

快排在选择基准数时是随机的，也就是说如果数组里有两个2，而选择的基准数是后面的2，那前面的2因为大于等于后面的2，就会被放在大数的群体里而被挪到基准2的后面，也就是这两个2的相对位置在排序前后发生了改变，所以称快排是不稳定的。

stable_sort()比sort()略慢。是因为输入数据量小时，sort用插入排序提升了性能，而stabe_sort一直是基于归并排序。