逆序数的题最经典的就是求逆序对数，可以直接冒泡然后记录交换的次数，时间复杂度O(n^2)。也可以用修改版的归并排序来做，时间复杂度会降到O(nlogn)。然后，有一种题是有一队人，每个人都知道自己的身高和前面比自己高的人数，队伍解散后怎么才能恢复队伍？这个题给的信息实际上就是逆序对数，根据逆序对数恢复元素位置，我想到的办法是用类似于插入排序的东西来做。下面有实现代码，现根据身高求出每个人前面比自己高的人数（逆序对数），然后用洗牌算法打乱队伍，最后恢复队伍。
#include
#include
#include
#include
using namespace std;
struct person
{ int id;
float height;
int higher_in_front;
};
// Use merge sort algorithm to calculate the higher person in front.
void calc_higher_in_front(person *begin, person *end, person *scratch)
{ if (begin == NULL || end == NULL || scratch == NULL)
{ return;
}
if (begin == end || begin + 1 == end)
{ return;
}
person *mid = begin + (end - begin) / 2;
calc_higher_in_front(begin, mid, scratch);
calc_higher_in_front(mid, end, scratch);
person *left = begin;
person *right = mid;
person *result = scratch;
while (left != mid || right != end)
{ if (left < mid && (right == end || left->height < right->height))
{ *result++ = *left++;
}
else
{ right->higher_in_front += (mid - left);
*result++ = *right++;
}
}
memcpy(begin, scratch, sizeof(person) * (end - begin));
}
// Shuffle algorithm
void shuffle(person *begin, person *end)
{ if (begin == NULL || end == NULL)
{ return;
}
if (begin == end || begin + 1 == end)
{ return;
}
size_t len = end - begin;
srand((unsigned)time(0));
for (size_t i = 0; i < len; ++i)
{ // Assume (rand() % (len - i)) + i produce random number
// between i and len - 1 equal probability.
swap(begin[i], begin[(rand() % (len - i)) + i]);
}
}
// Rebuild original sequence of person.
void rebuild(person *begin, person *end)
{ struct comp_by_higher_in_front
{ bool operator()(const person &lhs, const person &rhs) const
{ if (lhs.higher_in_front != rhs.higher_in_front)
{ return lhs.higher_in_front < rhs.higher_in_front;
}
else
{ return lhs.height < rhs.height;
}
}
};
sort(begin, end, comp_by_higher_in_front());
person *curr = begin;
while (curr != end)
{ if (curr->higher_in_front != 0)
{ break;
}
++curr;
}
for (; curr != end; ++curr)
{ person *p = begin, key = *curr;
int higher_count = 0;
while (p != curr)
{ if (p->height > key.height)
{ ++higher_count;
if (higher_count > key.higher_in_front)
{ break;
}
}
++p;
}
if (p != curr)
{ memmove(p + 1, p, (curr - p) * sizeof(person));
*p = key;
}
}
}
int main(int argc, char **argv)
{ person p[10];
memset(p, 0, sizeof(p));
for (int i = 0; i < 10; ++i)
{ p[i].id = i + 1;
}
p[0].height = 1.76f;
p[1].height = 1.6f;
p[2].height = 1.7f;
p[3].height = 1.8f;
p[4].height = 1.75f;
p[5].height = 1.5f;
p[6].height = 1.56f;
p[7].height = 1.61f;
p[8].height = 1.55f;
p[9].height = 1.71f;
person *scratch = new person[10];
calc_higher_in_front(p, p + 10, scratch);
shuffle(p, p + 10);
rebuild(p, p + 10);
// After rebuild, the p array should be restored.
return 0;
}