2018-07-13

快速排序算法

快排普通版本：

void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;
            
            if(i < j)
            {
                s[i] = s[j];      
                i++;
            }
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;

            if(i < j){
                s[j] = s[i];
                j--;
            }
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用
        quick_sort(s, i + 1, r);
    }
}

快排优化版本：

void swap(void **a, void **b)
{
    void *tmp = *a;
    *a = *b;
    *b = tmp;
}

//优化版2.0  任何结构都可以进行快速排序
int q_sort(void **s, size_t n, size_t l, size_t r, int (*cmp)(void*, void*))
{
    if( r > n -1 || l > r )
        return -1;
    

    void * x = s[l];    //X是基准值
    size_t i = l, j = r;
    while( i < j ){
        while( i < j && ( cmp(s[j], x) >= 0) )
            j--;
        
        if(i < j){
            swap(&s[i], &s[j]);
            i++;
            x = s[j];          
        }

        while( i < j && ( cmp(s[i], x) < 0 ))
            i++;

        if( i < j ){
            swap(&s[i], &s[j]);
            j--;
            x=s[i];          
        }
    }

    q_sort(s, n, l, i -1, cmp );
    q_sort(s, n, i +1, r, cmp );

    return 0;
}

测试代码：

void Print2(int **a, int n){
    for( int i =0; i < n; i++ ){
        printf("%d, ", *a[i]);
    }
    printf("\n");
}

int cmp(void *a, void *b)
{
    int *a1 = (int*)a;
    int *b1 = (int*)b;
    return *a1 - *b1;
}

int main()
{
    printf("start\n");
    int a[]= {35,72,8,7,22,85,43,31,11,35};
    Print(a,10);
    quick_sort(a,0,9);//注意最后一个参数是n-1!!!!!
    //qk_sort(a,0,9);
    Print(a,10);

    printf("==================================\n");
    int **s = (int**) malloc(10 * sizeof(int*));
    if( s == NULL ){
        printf("malloc failed\n");
        return -1;
    }

    for(int i = 0; i < 10; i++){
        s[i] = (int*) malloc(sizeof(int*));
        *s[i] = 10 - i;
    }

    Print2(s, 10);
    
    q_sort(s, 10, 0, 9, cmp);

    Print2(s, 10);

    for(int i = 0; i < 10; i++){
        free(s[i]);
    }
    free(s);

    return 0;
}