快速排序的实现

快速排序的核心思想分为两步：

1.选择任何一个数作为基准数，找到这个基准数的位置

2.基准数一侧的数大于另一侧的数，对两侧进行排序，这是分治的思想

写过很多次都不记得，其实没掌握其思想，找到基准数位置必然要把这个数和所有的数都比较一边，大于这个数的数放到这个数的右边，小于这个数的数放到这个数的左边，最后这个数的位置就确定了

例如我们看一个例子：

int array[6] = {3 , 5 , 1, 2, 4, 6};

我们假定基准数为a[0] = 3, 找3的位置打过程如下：

分析可知，算法结构是这样的：

/****************quick_sort.c made by cfmlovers************/#include <stdio.h>#define ARRAYSIZE 4/*find the position*/int partition(int a[], int l, int r){    int  i = l, j = r, temp = a[i];    while(i < j)    {        while(temp < a[j] && i < j)                j--;        if(i < j)            a[i++] = a[j];        while(a[i] < temp && i < j)                i++;        if(i < j)            a[j--] = a[i];    }       a[i] = temp;    return i;}void quick_sort(int a[], int l, int r){    int position;    if(l < r)    {        position = partition(a, l, r);        quick_sort(a, l, position-1);        quick_sort(a, position+1, r);    }}void main(){    int a[ARRAYSIZE], i;    printf("please input 4 numbers\n");    for(i = 0; i < 4; i++)        scanf("%d",&a[i]);    /*quick sort*/    quick_sort(a, 0, ARRAYSIZE-1);    for(i = 0; i < 4; i++)        printf("%d\n", a[i]);}

快速排序的效率取决于基准数所产生的分区，如果分区平衡和归并排序一样，如果分区不平衡，效率甚至和插入排序一样