亲们，都进来玩排序吧!

Question

使用C#语言开发程序时，对一组5个元素的数据(如：71,11,4,67,39)，为了把改组数组按升序
排序，如果按冒泡排序法，需要比较多少次()
A 6
B 8
C 10
D 16
 
答案是C我的排序过程是这样的：11,71,4,67,39 这是第一次排序
11,4,71,67,39 这是第二次排序
11,4,67,71,39 这是第三次排序
11,4,67,39,71 这是第四次排序
4,11,67,39,71 这是第五次排序
4,11,67,39,71 这是第六次排序
4,11,39,67,71 这是第七次排序亲们，我的排序哪里出错了啊?怎么排出的次数是7次啊? 答案是10次吗?
答案给的是10次，10次是怎么来的啊? 请亲们按照我的这种方式排序出10次，这样就一目了然了。
还有一个问题是：如果下次再碰到这种问排序次数问题的，有没有比较简单的方式?比如有没啥公式的，有的话
请亲们写出公式并且能举出个例子说明一下，这样就是通俗易懂多了。

Answer 1

n个元素冒泡总次数是    T(n) = T(n-1) + (n-1)即：首先顶上n-1个元素冒泡排序，然后用最底下一个元素从下向上冒泡一次就可以了。其实这是最简单的递推公式：
   T(n)    = T(n-1) + (n-1)
   T(n-1)  = T(n-2) + (n-2)
   T(n-2)  = T(n-3) + (n-3)
   ..............
   T(2)    = T(1)   + 1
   T(1)    = 0你把上面都加起来，左右重复的项消除，得到
   T(n) = (n-1) +(n-2) + (n-3) .....+ 1 + 0  = n*(n-1)/2其实因为这是任何一个算法书上最初级的、必定有的公式，通常只要正规学过软件专业的都应该很自然地记住最后的公式。你把5带入n变量，就得到了10。
当然对于这个简单问题也可以摆着手指指头数数，计算对于5个元素，第一趟冒泡要比较 5 个元素，第二趟要比较 4 个，.....，最后 4+3+2+1 于是就是10了。

Answer 2

恩，懂了。总结出这样一个结果：比较N个数的大小并排序的话，要比较N-1遍。第一遍比较N-1次，将最大的数放在最后；第二遍比较N-2次，将第二大的数放在了倒数第二的位置；依次类推，最后一遍只比较两个数的大小，即一次。

Answer 3

再比如说快速排序的元素比较次数，对于n个元素，假设每一次划分都正好是从中间分割，那么
   T(n) = P(n) + T(n/2) 
其中 P(n) 就是划分算法（对n个元素划分为大小两个区间）所需要的比较次数。其实算法复杂度公式都是运用数学归纳法计算出来的，不是摆着手指头数出来的。

Answer 4

嗯不对，是 T(n) = P(n) + 2 * T(n/2)