一道题调了一周，今天终于调过了……
题目不算很难写，就是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一直是基于归并排序。