用函数指针实现的快速排序算法

K&R第五章介绍了用函数指针实现的快速排序算法，对其中的代码比较困惑，所以看了下《算法导论》上对快排的介绍。归纳算法如下：

设每次遍历的最左边为low, 最右边为high,数组名为a：

1.每次以最左边的数a[low]为基准数（pivot），从左边第二个数(a[low+1])开始遍历，维护一个i -->j的数列，这些数都比pivot大，直到j到达最右边(high)。

2.此时，i -->high之间的数都比pivot大，low+1 --> i-1之间的数都比pivot小。

3.交换pivot和第i-1个数a[i-1]。

4.对low-->i-1, i-->high之间的数递归调用上面的过程1、2、3

下面这张图说明了快排的原理及过程：

用C实现上面的过程：

#include <stdio.h>

/* declare function pointer */
typedef int(*fp_operation)(int a, int b); //参考我的博文：http://blog.csdn.net/wusuopubupt/article/details/38981631

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

int compare(int a, int b) {
    return (a-b);
}

void my_qsort(int arr[], int low, int high, fp_operation cmp) {
    if(low >= high) {
        return;
    }
    int pivot = arr[low];
    int mid;
    int i, j;
    i = j = low+1;
    while(j <= high) {
    	if((*cmp)(arr[j], pivot) < 0) {
    		swap(&arr[j], &arr[i]);
    		i++;
    	}
    	j++;
    }

    swap(&arr[low], &arr[i-1]);
    mid = i-1;

//    int k = 0;
//    printf("mid: %dn", mid);
//    while(k < 16) {
//    	printf("%d ", arr[k]);
//    	k++;
//    }
//    printf("n");

    my_qsort(arr, low, mid-1, cmp);
    my_qsort(arr, mid+1, high, cmp);
}

int main() {
    int arr[] = {2, 1, 7, 1, 5, 4, 9, 6, 1, 2, 4, 0, 5, 2, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    my_qsort(arr, 0, n-1, (fp_operation)compare);

    int i = 0;
    while(i < n) {
        printf("%d ", arr[i]);
        i++;
    }
    printf("n");

    return 0;
}

github:https://github.com/wusuopubupt/LearningC/blob/master/K%26R/chp5/quick_sort.c

最后

以上就是传统花瓣为你收集整理的用函数指针实现的快速排序算法的全部内容，希望文章能够帮你解决用函数指针实现的快速排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。