快速排序（code）

快速排序，实际上，确实需要两个变量，指向数组的首段和尾段，也确实需要一个基准来进行比较，结果就是，让比基准大的，都在基准的右边，比基准小的都在基准的左边，这样再分别对基准左右两端的数组进行快速排序。直到只剩下一个数据。

废话不多说，上例子。

60 80 55 40 42 85

i 指向 最左端，j 指向最右端。基准为60 如下

60   80  55   40   42  85  
i                       j

j 从 右向左，查找第一个比60小的数。查找结果是42, 42去 i 指向的位置。如下

42   80  55   40   null  85  
i                    j

i 从左向右，查找第一个比60大的数。查找结果是80,80去 j 指向的位置。如下

42   null  55   40   80  85  
      i               j

j 继续查找比60小的数。查找结果是40， 40 ，去 i 指向的位置。如下

42   40  55   null   80  85  
      i         j

i 继续查找比60大的数，直到与 j 遇见，都没有找到，因此 将基准60放入 i 和 j共同指向的位置。第一趟结束。如下

42   40  55   60   80  85  
              ij

再一次对 42 40 55 进行如上的操作，对 80 85 也进行如上的操作。如此循环，直至，操作的数组中只有一个元素。

code如下：

int Partition(int arr[],int left,int right){
    int i = left;               //left指向最左边 
    int j = right;          //right指向最右边 
    int key = arr[left];            //基准 为数组第一个元素 
    int temp;
    while(i<j){         // left只能小于right，不可能大于right 
        while(i<j&&arr[j]>key){ //我们需要找比key小的数，所以，只有当比key大的时候，j才移动。 
            j--;
        }
        printf("%d,%d\n",i,j);
        if(i<j)
            arr[i++] = arr[j];
        while(i<j&&arr[i]<key){ //我们需要找比key大的数，所以，只有当比key小的时候，j才移动。
            i++;
        } 
        if(i<j)
            arr[j--] = arr[i];
    }
    arr[i] = key;
    return i;
}
void QuickSort(int arr[],int left,int right){
    if(left<right){
        int pivotloc;
        pivotloc = Partition(arr,left,right);
        QuickSort(arr,left,pivotloc-1);
        QuickSort(arr,pivotloc+1,right);
    }
    
}