快速排序

快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，

其基本思想為：

任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

將區間按照基準值劃分為左右兩半部分的常見方式有：

1. hoare版本
2. 挖坑法
3. 前后指針版本

遞歸方式

如果當中元素個數多于一個，則進行快排

//從右側位置開始選擇
//給兩個指針，一個放在最左邊，一個放在最右邊，左邊找比key大的，找到停下，右邊找小的，找到停下，然后把這兩個進行交換
//兩個相遇后，當前的位置元素，與最后元素交換，也就是與key交換

//begin從前往后找比基準值大的元素，找到停下
while (begin<end&&array[begin]<=key){ //比key小或者等于往后走，大停下來,找到大的,如果本身序列最大的數在最后一個，begin會越界，則必須保證begin<end

//end從后往前找比基準值小的元素，找到停下來
//找到小的
//如果兩個不在同一個位置
//兩個交換

//end和begin相遇，把他們當前指向的數與key進行交換

挖坑法

前后指針版本
基準值取數組最后一個元素
cur開始遍歷數組，如果當前cur里的值小于基準值，pre往后走一步，兩個在同一個位置，不再同一位置進行交換。如果cur的值大于基準值，cur一個人往前走。

最好場景：數據越隨機，越亂越好O（n log2 n）
最差的場景：接近有序O（n*n）
三數取中法降低最差場景

之前的操作要做一些改動

遞歸轉化成循環