排序算法——快速排序

算法思想：

在实际应用当中快速排序确实也是表现最好的排序算法。其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
它采用了一种分治的策略，分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。

举例：

5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。

5,3,8,6,4 首先设置i,j两个指针分别指向两端，将左端元素5赋值给temp，j指针先扫描，4比5小停止,执行a[i]=a[j]

4,3,8,6,4 然后j指针再扫描，遇到8比temp大，此时i停在8，j停在4，执行a[j]=a[i]

4,3,8,6,8此时j往前走直到和i相遇，此时的i就是temp应该放的位置

4,3,5,6,8之后对左右子序列递归排序，最终得到有序序列。

代码：

 1 void quickSort(int* a, int left, int right)
 2 {
 3     int i = left;
 4     int j = right;
 5     int temp = a[left];
 6     if (left >= right)
 7         return;
 8     while (i != j)
 9     {
10         while (i < j&&a[j] >= temp)
11             j--;
12         if (j > i)
13             a[i] = a[j];
14         while (i < j&&a[i] <= temp)
15             i++;
16         if (i < j)
17             a[j] = a[i];
18     }
19     a[i] = temp;//把基准插入
20     quickSort(a, left, i - 1);/*递归左边*/
21     quickSort(a, i + 1, right);/*递归右边*/
22 }