快排

快速排序算法是二分法的一种典型的应用，其平均时间复杂度为O(nlogn)

快排有两种操作方式，第一种为交换法，第二种为赋值法，我个人觉得赋值法比较容易理解所以这里就仅讲解赋值法。

先看代码：

 1 int mySort(vector<int>& arr, int l, int r)
 2 {
 3     int pivot = arr[l];
 4     while (l < r)
 5     {
 6         while (l<r && arr[r]>pivot) r--;
 7         swap(arr[r], arr[l]);
 8         while (l < r && arr[l] < pivot) l++;
 9         swap(arr[r], arr[l]);
10     }
11     arr[r] = pivot;
12     return r;
13 }
14
15 void quickSort(vector<int>& arr, int l, int r)
16 {
17
18     if (l < r)
19     {
20         //每次以第一个数作为锚点，然后进行排序，最后返回锚点所在位置的下标
21         //然后以该下标为界进行二分，递归求解
22         int pivotIndex = mySort(arr, l, r);
23         //二分
24         quickSort(arr, l, pivotIndex - 1);
25         quickSort(arr, pivotIndex + 1, r);
26     }
27 }
28
29
30 int main()
31 {
32     vector<int> arr = { 5,9,1,3,6,10,4,2 };
33     quickSort(arr, 0, 7);
34     return 0;
35 }

算法思想：

每次调用quicksort函数时都对数组进行排序，返回锚点的位置。

如图，首先以左边第一个数作为锚点，注意当我们以左边第一个数作为锚点时我们就要先从右边开始查找第一个小于锚点的数

找到一个小于锚点的数就立刻进行交换，然后再从左边开始找大于锚点的数，

 如图先找到2，将2与arr[left]进行交换，然后从左边开始找到9与arr[right]进行交换，