快速排序-白红宇

参考：

http://www.cnblogs.com/skywang12345/p/3596746.html

下面上代码：

#include
     
      using namespace std;void quicksort(int *arr, int left, int right){    if(left < right)    {        int i = left;        int j = right;        int temp = arr[i];        while(i < j)        {            while(i < j && arr[j] > temp)            {                j--;            }            if(i < j)            {                arr[i] = arr[j];//  arr[i++] = arr[j];                i++;            }            while(i < j && arr[i] < temp)            {                i++;            }            if(i < j)            {                arr[j] = arr[i]; // arr[j--] = arr[i];                j--;            }        }        arr[i] = temp;        quicksort(arr, left, i-1);        quicksort(arr, i+1, right);    }}int main(){    int arr[] = {
   30, 20, 40, 20, 10, 40, 60, 50,90,70, 70};    int count = sizeof(arr)/sizeof(int);    cout << "Before:" << endl;    for(int i = 0; i < count; i++)    {        cout << arr[i] << " ";    }    cout << endl;    quicksort(arr, 0, count - 1);    cout << "After:" << endl;    for(int i = 0; i < count; i++)    {        cout << arr[i] << " ";    }    cout << endl;}

分析：

以数组int arr[] = {4, 5, 2 ,6, 1, 3};进行分析：

初始化 i=0，j=5， temp = arr[0];

红色加粗的表示在下一次将会被覆盖的位置。

循环次数		退出while条件	当前数组	对应的操作
1	i=0,j=5 <-	3 < temp	3 5 2 6 1 3	arr[0]=arr[5], i++ (arr[i++]=arr[j])
2	i=1,j =5 ->	5 > temp	3 5 2 6 1 5	arr[5]=arr[1],j-- (arr[j--]=arr)
3	i=1,j=4 <-	1 < temp	3 1 2 6 1 5	arr[1]=arr[4], i++ (arr[i++]=arr[j])
4	i=2,j=4 ->		3 1 2 6 1 5	i++ （因为2小于temp，直接i++）
5	i=3,j=4, ->	6 > temp	3 1 2 6 6 5	arr[4]=arr[3]; j-- (arr[j--]=arr)
6	i=3,j=3		3 1 2 4 6 5	arr[3] = temp

第一次循环之后数组变成了这样 3 1 2 4 6 5，I,j的值都是3。

arr[3]左边的全部小于arr[3]，arr[3]右边的全部大于arr[3]

然后对两边分别进行排序；

quicksort(arr, 0, 2);

quicksort(arr, 4, 5);