Question

c语言，快速排序，在最坏条件下需要比较的次数为多少

Answer 1

快速排序最坏的情况是初始序列已经有序，第1趟排序经过n-1次比较后，将第1个元素仍然定在原来的位置上，并得到一个长度为n-1的子序列；第2趟排序经过n-2次比较后，将第2个元素确定在它原来的位置上，又得到一个长度为n-2的子序列；以此类推，最终总的比较次数：
C(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2
最坏的情况下，快速排序的时间复杂度为O(n^2)

Answer 2

假设有n个数，n(n+1)/2次