算法：快速排序

题目：

给定一个无序整数数组arr，请使之有序。

思路：

找到一个数p，把arr分成两部分，左边部分所有数都小于或等于p,右边部分所有数都大于或等于p。然后对左右两部分继续应用此规则。如何找数p? 首先让p等于arr[0]，然后两个指针l、r从左右两边同时遍历，左边遇到大于p的数，停下，右边遇到小于p的数，停下，然后交换l、r。重复这个动作，直到l、r相遇。然后arr[0]和arr[l]交换。此时数组被p分为左右两部分，左边的数都小于p，右边的数都大于p。

代码：

class QuickSort {
public:
    void quickSort(vector<int>& arr,int left, int right) {
        if (left < right) {
            int l = left, r = right;
            while (l < r) {
                while (l < r && arr[left] <= arr[r]) {
                    r--;
                }
                while (l < r && arr[left] >= arr[l]) {
                    l++;
                }
                int tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
            }
            int tmp = arr[l];
            arr[l] = arr[left];
            arr[left] = tmp;
            quickSort(arr, left, l - 1);
            quickSort(arr, l+1, right);
        }
    }
};