快速排序

快速排序由C.A.R.Hoare（东尼霍尔）在1960年提出。之后又有许多人对此进行改进。如果你对快速排序感兴趣可以去看看东尼霍尔1962年在Computer Journal发表的论文“Quicksort”以及《算法导论》的第七章。

基本思想

通过一次排序将需要排序的数组分割成两部分,一部分的值比另一部分要小。再将这两个部分通过上面的方式排序，以此类推。最后分割成了很小的一部分，直到每个数字。整个排序的过程我们可以通过递归的方式进行。

时间复杂度

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。

Example：演示第一轮排序

5 7 6 4 3 1 9 8 0 2

对上面的数进行排序,先定义一个基准数：5。比较从两边进行，一边是从索引为0的开始，如果遇到比5大的就停下；另一边是从索引为9的开始，如果遇到比5小的就停下。然后交换两遍的数。在第一轮中，从左边开始比较的在遇到7之后就会停下来，因为7比5大；从右边开始的遇到2就会停下来，因为2比5小。然后交换两个人的位置。

5 2 6 4 3 1 9 8 0 7

继续走，6比5大，0比5小，交换

5 2 0 4 3 1 9 8 6 7

继续走，左边的遇到了9，比5大，停下来；右边的经过8，快要和左边的相遇了停下来。这时候当把9和5交换的时候发现排序后5左边并没有都比右边小

9 2 0 4 3 1 5 8 6 7

纠正一下，重新开始，最后一步比较的时候：这时候右边的先到1，发现1比5小停下。等左边的和右边的相遇时。将右边的1和基准数5交换，如下

1 2 0 4 3 5 9 8 6 7

int a[10] = {6,1,2,7,9,3,4,5,10,8};

void quickSort(int left,int right){
    int i,j,t,temp;
    if(left > right){
        return;
    }
    
    temp = a[left];
    i = left;
    j = right;
    
    while (i!=j) {
        while (a[j] > temp && i < j) {
            j--;
        }
        while (a[i] <= temp && i < j) {
            i++;
        }
        
        if(i < j){
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[i];
    a[i] = temp;
    
    quickSort(left, i - 1);
    quickSort(i + 1, right);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    quickSort(0, 9);
    for(int i = 0 ; i < 10;i++){
        printf("%d ",a[i]);
    }
    return 0;
}