算法---4.快速排序

1. 快速排序
中间partition的过程就是一个swap的过程，
保存key
右/左->左/右           -->整个过程是一个swap，但这儿是个单向的赋值
key->左/右

第1趟按arr[0],分成左右两部分
左部分与右部分再按上述过程递归

1.2 代码

#include <stdio.h>
#include <stdlib.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
#define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))

int dump_arry(int* arr, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        //printf("%d=%d ", i, arr[i]);
        printf("%d  ", arr[i]);
    }
    printf("\n");
    return 0;
}

int partition(int* arr, int low, int high)
{
    int i, j;
    int pivotkey;
    if(low >= high)
        return 0;
    pivotkey = arr[low];    //以第一个数据为基准分为左小右大的两部分
    while(low < high)
    {
        while( (low<high) && (arr[high]>=pivotkey) )
            high--;
        arr[low] = arr[high];
        dump_arry(arr, 10);

        while( (low<high) && (arr[low]<=pivotkey) )
            low++;
        arr[high] = arr[low];
        dump_arry(arr, 10);
    }
    arr[low] = pivotkey;
    dump_arry(arr, 10);
    return low;
}

int quick_sort(int* arr, int low, int high)
{
    int pivotloc = partition(arr, low, high);
    dbmsg("pivotloc=%d", pivotloc);
    if(low < high)   //以第一个数据为基准分为左小右大的两部分，这样一直分一直分，直到low
    {
        dbmsg("left");
        quick_sort(arr, low, pivotloc-1);
        dbmsg("right");
        quick_sort(arr, pivotloc+1, high);
    }
    return 0;
}
int main ( int argc, char *argv[] )
{
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int len = sizeof(arr)/sizeof(int);
    dbmsg("len=%d", len);
    dbmsg("before quick:");
    dump_arry(arr, len);
    quick_sort(arr, 0, len-1);
    dbmsg("after quick:");
    dump_arry(arr, len);
    return EXIT_SUCCESS;
}

1.3 运行结果

quick.c:main[52]: before quick:
49  38  65  97  76  13  27  49  55  4

4  38  65  97  76  13  27  49  55  4
4  38  65  97  76  13  27  49  55  65
4  38  27  97  76  13  27  49  55  65
4  38  27  97  76  13  97  49  55  65
4  38  27  13  76  13  97  49  55  65
4  38  27  13  76  76  97  49  55  65
4  38  27  13  76  76  97  49  55  65
4  38  27  13  76  76  97  49  55  65
4  38  27  13 49 76  97  49  55  65    -->按49分成左右两部分
4  38  27  13  49  76  97  49  55  65    -->49的left再4分成左右两部分
4  13  27  13  49  76  97  49  55  65
4  13  27  13  49  76  97  49  55  65
4  13  27 38 49  76  97  49  55  65
4  13  27  38  49  76  97  49  55  65
4  13  27  38  49  65  97  49  55  65
4  13  27  38  49  65  97  49  55  97
4  13  27  38  49  65  55  49  55  97
4  13  27  38  49  65  55  49  55  97
4  13  27  38  49  49  55  49  76  97
4  13  27  38  49  49  55  49  76  97
4  13  27  38  49  49  55  65  76  97
4  13  27  38  49  49  55  65  76  97

quick.c:main[55]: after quick:
4  13  27  38  49  49  55  65  76  97

1.4 性能
O(nlogn)
1.5 代码打包
quick.rar  (下载后改名为quick.tar.gz)