快速排序

快速排序，在实际应用中是表现最好的排序算法，其实际思想来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快排是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

不稳定

O（nlgn）

 1 void swap(int &a, int &b)
 2 {
 3     int temp;
 4     temp = a;
 5     a = b;
 6     b = a;
 7 }
 8 
 9 int partition(int *arr, int left, int right)
10 {
11     int pivotKey = arr[left];
12     int pivotPoint = left;
13     while(left < right)
14     {
15         while(left < right && arr[right] >= pivotKey)//右指针先移动
16             right --;
17         while(left < right && arr[left] <= pivotKey)
18             left ++;
19         swap(arr[left], arr[right]);
20     }
21     swap(arr[pivotPoint], arr[left]);
22     return left;
23 }
24 
25 void quickSort(int *arr, int left, int right)
26 {
27     if(left >= right)
28         return ;
29     int pivotPos = partition(arr, left, right);
30     quickSort(arr, left, pivotPos-1);
31     quickSort(arr, pivotPos+1, right);
32 }