快排分析

最难的问题是这样的：他做到的哪个细节是我做不到的？如果她做到的每个细节，我都能做到呢？绝大多数人不敢追问自己、逼问自己的。人们宁愿使蛮力，宁愿身体勤奋，却不愿问更深层的问题
感悟: 最难的问题是我们每个人都心存侥幸，都不愿意在每一个细微处下功夫。对“不厌其烦”这 4 个字不屑一顾。如此一来，就造成了我们思维当中的诸多漏洞。导致我们不断的漏知识，漏技术，漏能力，漏财富……

快速排序无论在空间还是时间都是最好的排序算法之一~
首先快排有几个优点：1 原地排序（不需要额外的空间）2 平均状态下时间复杂度 Nlogn 虽然最坏时依然为 O(n^2)但是几率非常小而且 O(nlgn)中隐含的常数因子也非常小 , 属于高效排序算法 而快排的缺点则是其不稳定性因为前牵扯到空间地址的交换所以快速排序不能保证出现相同元素下的稳定排序效果。

关于快排 pivot 的选取 根据斯坦福算法专项课，我们有三种不同的 pivot 选取方式，并计算相应比较次数，分别为 choose first, choose last, median of three, 还可以进行随机选取，这也是快速排序为什么是一种随机化算法。

首先来看算法导论上的第一种选取 choose last

QUICKSORT(A,p,r)
if(p<r)

    q=PARTITION(A,p,r);
    QUICKSORT(A,p,q-1);
    QUICKSORT(A,q+1,r);

算法的关键部分是 PARTITION 他实现了算法的原址操作。
PARTITION(A,p,r)

x=A[r]
i=p-1
for j=p to r-1
if A[j]<=x
    i++
    exchangea[j] with A[i]

exchage A[i+1]with A[r]
return i+1

以上 PATITION 算法 在左端点左边放一个哨兵也就是 p -1 从左哨兵开始 j 的目的是遍历一遍数组查看是否有小于 A[pivot]的 若有则依次放左边。经过 PARTITION 一遍过后，进入递归。为什么快排可以完成排序功能这个理解重点就在这里，每次 PARTITION 过后就代表有一个数完成排序所以进入递归的是没有完成排序功能的数。从方法上来看 q 点 已完成排序（前面比它小，后边比他大）所以将数组其他部分进入递归 排除 q 点。
每进行完一次 PARTITION 就代表有一个数完成排序，所以如果仅仅要找第 k 大（小）的数 可以将快排稍微改一改 就可以实现而并不需要完全排序之后取第 k 个值
算法如下

//PARTITION 可以不变

int _k =k(第 k 小 / 大);
int k =k;// 这 k 作为变量；QUICKSORT(A，p，r,k)
  if(p<r)
    q=PARTITION(A,p,r，k)
    if(q-p+1<k)QUICKSORT(A,p,q-1,k);
    if(q-p+1>k)QUICKSORT(A,q+1,r,k-(p-l))

// 然后直接查找 A[_k]即可。