# 快速排序 快速排序得名于实际应用的高效率,它几乎是排序最快的算法，入选20世纪十大算法之一。与归并排序一样，快速排序用了分治法的思想，并且都是原址排序。 核心：对于数X，假如你知道假如你知道小于它的个数，大于它的个数，那么你就知道了X的位置。 步骤： 1. 选取一个分界数，大于分界数的放在右边，小于分界数放在左边。 2. 对于分界数左边和右边，分别递归调用步骤1，直到分界数左右边只有一个数，也可以为空 3. 合并得到结果，因为每一次调用，分界数肯定在正确的位置，直到所有递归结束，所有的数就刚好在正确的位置，就不需要花时间抢合并，这就是原址排序 ~~~ Partition(A,p,r)//以A[r]作为分界数，进行划分 x=A[r] i=0 for j=p to r-1 if(A[j]<=x) i=i+1 exchance A[i] with A[j] exchance A[i+1]with A[r] return i+1 QuickSort(A,p,r)//当一个数组，或子数组只有一个元素时，停止递归重排 If p<r q= Partition(A,p,r) QuickSort(A,p,q-1) QuickSort(A,q+1,r) ~~~ **最坏情况：** 当数组划分越多次，调用递归的次数最多，也就是当数组所有的数相等时，运行时间最糟糕。时间复杂度为O（n^2）；特别地：当数组已经排序好，也是最坏情况，而这时插入排序的时间复杂度为O（n）；虽然是这样，但是这种情况却是很少发生，因而其平均性能很好 **最好情况：** 当每次划分都是最平衡的划分,快速排序的性能最好,时间复杂度为O(n*log2(n)),平均运行时间复杂度也为O(n*log2(n))