概念：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以

递归

进行，以此达到整个数据变成有序

序列

。

特点：

最坏情况

时间复杂度

为o（n

2

）。因为

最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。最好情况：

如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了，

排序的大体如下图所示，假设有1到8代表要排序的数，快速排序会递归log（8）=3次，每次对n个数进行一次处理，所以他的时间复杂度为n*log(n)。

题目：越有序，时间复杂度越高。数据结构中，有一个逆序数的概念。如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个

逆序

。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。

题目中：A8 B17 C11