原理：就是在归并排序上改进，以时间复杂度换空间复杂度，利用元素反转完成排序

具体过程如下：

 

具体操作看代码吧，应该没什么难度，主要是reverse要反转三次

1 typedef int Position; 2  3 void Merge_Sort(Position, Position, int *const, Position *); 4 void Merge(Position, Position, int *const, Position *); 5 void Convert(Position, Position, Position, Position *); 6 void Reverse(Position, Position, Position *); 7 void Swap(Position *, Position, Position); 8  9 void Merge_Sort(Position Left, Position Right, int *const Inverse_Num, Position *A)10 {11     if (Left < Right)12     {13         Position Mid = (Left + Right) / 2;14         Merge_Sort(Left, Mid, Inverse_Num,A);15         Merge_Sort(Mid + 1, Right, Inverse_Num,A);16         Merge(Left, Right, Inverse_Num, A);17     }18 }19 20 void Merge(Position Left, Position Right, int *const Inverse_Num, Position *A)21 {22     Position Mid = (Left + Right) / 2, lpos = Left, rpos = Mid + 1, pos = Left, index = rpos;23 24     while (lpos <= Mid && rpos <= Right)25     {26         while (lpos < rpos && A[lpos] <= A[rpos])27             lpos++;28         index = rpos;29         while (rpos <= Right && A[rpos] < A[lpos])30             rpos++;31         Convert(lpos, index - 1, rpos - 1, A);32         lpos += rpos - index;33     }34 }35 36 void Convert(Position Left, Position Mid, Position Right, Position *A)37 {38     Reverse(Left, Mid, A);39     Reverse(Mid + 1, Right, A);40     Reverse(Left, Right, A);41 }42 43 void Reverse(Position Left, Position Right, Position *A)44 {45     Position i = Left, j = Right;46     while (i < j)47         Swap(A, i++, j--);48 }49 50 void Swap(Position *A, Position i, Position j)51 {52     A[i] ^= A[j];53     A[j] ^= A[i];54     A[i] ^= A[j];55 }

 参考：