十种经典排序算法精粹(c语言版本)

红太狼 2022-03-07 00:22 170阅读 0赞

下面给出这段时间我苦心研究验证过的十种经典排序算法的C语言版本，即下面的排序算法：

插入排序，shell排序，冒泡排序，快速排序，选择排序，堆排序，归并排序，桶排序，基数排序和计数排序。整理出来以作备忘，不足之处，欢迎大家批评指正！其中计数排序分别给出了不稳定和稳定两种排序算法，测试时，使用随机生成大数组和随机手动输入的方法来测试。

//description: 这里给出了c语言版本的10种排序算法
    //refer: 参考自Weiss的教材及网上资料
    //compile: gcc -g sort_demo.c -o sort_demo
    //author: tao_627@aliyun.com
    //date: 2019-03-12
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    void swap(int arr[], int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    
    
    void insert_sort(int arr[], int n){
        int i,j,t;
        //遍历未排序集，默认第一个元素(i=0)是有序集内的
        for(i=1; i<n; i++){
            t=arr[i];
            //在有序集内从后往前逐个比较，将大的元素逐个后移一位
            for(j=i; j>0 && t<arr[j-1]; j--)
                arr[j]=arr[j-1];
            arr[j]=t;
        }
    }
    
    
    void shell_sort(int arr[], int n){
        int i,j,t,gap;
        for(gap=n/2; gap>0; gap/=2){
            for(i=gap; i<n; i++){
                t=arr[i];
                for(j=i; j>=gap && t<arr[j-gap]; j-=gap)
                    arr[j] = arr[j-gap];
                arr[j]=t;
            }
        }
    }
    
    
    void bubble_sort(int arr[], int n){
        int i,j,t;
        for(i=0; i<n-1; i++){
            for(j=0; j<n-1-i; j++){
                if(arr[j]>arr[j+1])
                    swap(arr, j, j+1);
            }
        }
    }
    
    void quick_sort(int arr[], int left, int right){
        int i,j,pivot;
        if(left>right)
            return;
    
        pivot=arr[left];
        i=left;
        j=right;
        while(i!=j){
            while(arr[j]>=pivot && i<j)
                j--;
            while(arr[i]<=pivot && i<j)
                i++;
            if(i<j)
                swap(arr, i, j);
        }
        swap(arr, left, i);
    
        quick_sort(arr, left, i-1);
        quick_sort(arr, i+1, right);
    }
    
    void select_sort(int arr[], int n){
        int i,j,min;
        for(i=0; i<n-1; i++){
            min=i;
            for(j=i+1; j<n; j++){
                if(arr[min]>arr[j])
                    min=j;
            }
            if(min!=i)
                swap(arr, min, i);
        }
    }
    
    #define LeftChild(i) (2*(i) + 1)
    
    //构建以arr[i]为根的最大堆
    void heap_adjust(int arr[], int i, int n){
        int child,t;
        for(t=arr[i]; LeftChild(i)<n; i=child){
            child=LeftChild(i);
            //如果存在右子节点且右子节点值更大，选右子节点
            if(child!=n-1 && arr[child+1]>arr[child])
                child++;
            if(t<arr[child])
                arr[i]=arr[child];//如果子节点值更大，赋给父节点
            else
                break;
        }
        //当前的i值一直在变化
        arr[i]=t;
    }
    
    void heap_sort(int arr[], int n){
        int i;
        //构建n个元素组成的最大堆
        for(i=n/2; i>=0; i--)
            heap_adjust(arr, i, n);
        for(i=n-1; i>0; i--){
            swap(arr, 0, i);
            heap_adjust(arr, 0, i);
        }
    }
    
    //lb=start of left half, le=end of left half;
    //rb=start of right half, re=end of right half;
    void merge(int arr[], int tmp_arr[], int lb, int rb, int re){
        int i, le, total, tmp;
    
        le=rb-1;
        tmp=lb;
        total=re-lb+1;
    
        while(lb<=le && rb<=re){
            if(arr[lb]<=arr[rb])
                tmp_arr[tmp++]=arr[lb++];
            else
                tmp_arr[tmp++]=arr[rb++];
        }
    
        while(lb<=le)
            tmp_arr[tmp++]=arr[lb++];
        while(rb<=re)
            tmp_arr[tmp++]=arr[rb++];
    
        //copy tmp_array back
        for(i=0; i<total; i++, re--)
            arr[re]=tmp_arr[re];
    }
    
    void msort(int arr[], int tarr[], int left, int right){
        int center;
        if(left<right){
            center=(left+right)/2;
            msort(arr, tarr, left, center);
            msort(arr, tarr, center+1, right);
            merge(arr, tarr, left, center+1, right);
        }
    }
    
    void merge_sort(int arr[], int n){
        int* tmp_arr = malloc(n * sizeof(int));
        if(tmp_arr != NULL){
            msort(arr, tmp_arr, 0, n-1);
            free(tmp_arr);
        }else{
            printf("No enough memory space for temp array!!!");
            exit(-1);
        }
    }
    
    #define BUCKET_DEPTH (10)
    
    typedef struct bucket {
        int node[BUCKET_DEPTH]; //假设每个桶最多装10个相同元素
        int count; //该桶中当前元素个数
    } bucket;
    
    void bucket_sort(int arr[], int n){
        int max, min, num, pos;
        int i,j,idx;
    
        //统计待排序数组的最大值和最小值
        max=min=arr[0];
        for(i=1; i<n; i++){
            if(max<arr[i])
                max=arr[i];
            if(min>arr[i])
                min=arr[i];
        }
    
        //计算桶的个数,每个桶至多10个元素
        num=(max-min+1)/BUCKET_DEPTH+1;
        bucket* pb=(bucket*)malloc(sizeof(bucket)*num);
        if(pb==NULL){
            printf("No enough memory space for allocate bucket array!!!");
            exit(-1);
        }
        memset(pb, 0, sizeof(bucket)*num);
    
        //将数组中的数据放入所属的桶内
        for(i=0; i<n; i++){
            //计算该元素所在的桶索引
            idx=(arr[i]-min+1)/BUCKET_DEPTH;
            //判断是否有足够的位置
            if(pb[idx].count>BUCKET_DEPTH){
                printf("FATAL: bucket [%d] has no enough space to store item!!!", pb[idx].count);
                exit(-1);
            }
            //放元素进桶内
            pb[idx].node[pb[idx].count++]=arr[i];
        }
    
        pos=0;
        //按顺序逐个输出桶内的元素，桶内元素采用快速排序
        for(i=0; i<num; i++){
            //仅对非空的桶执行快速排序
            if(pb[i].count>0)
                quick_sort(pb[i].node, 0, pb[i].count-1);
    
            for(j=0; j<pb[i].count; j++){
                arr[pos++]=pb[i].node[j];
            }
        }
    
        free(pb);
    }
    
    //判断一个整数是几位数
    int get_num_digit(int num){
        int count=0;
        while(num!=0){
            num /= 10;
            count++;
        }
        return count;
    }
    
    //提取指定整数位上的数字
    int get_pos_digit(int num, int pos){
        int multiple=1, i;
        for(i=0; i<pos-1; i++){
            multiple *= 10;
        }
        return (num/multiple)%10;
    }
    
    #define RDX_WIDTH 10
    #define MAX_NUM_LEN 32
    
    void radix_sort(int arr[], int n){
        //分别为0-9的序列空间
        int* rdx_arr[RDX_WIDTH];
        int i, k, pos;
        for(i=0; i<RDX_WIDTH; i++){
            //每个桶最多顺序存放n个数(注意数组是有顺序的)
            rdx_arr[i]=(int*)malloc(sizeof(int) * (n+1));
            //索引为0处记录这个数组的个数
            rdx_arr[i][0]=0;
        }
    
    
        //找到这个数组的最大数及其位数
        int max=arr[0];
        for(i=0; i<n; i++){
            if(max<arr[i])
                max=arr[i];
        }
    
    
        int max_dig_num=MAX_NUM_LEN;
        int dig_num=get_num_digit(max);
        //确定当前最多需要几位数的循环
        if(dig_num<max_dig_num)
            max_dig_num=dig_num;
        //printf("max number:%d, max digit number of max number:%d\n", max, max_dig_num);
    
        //从最低有效位开始遍历，一直到第高有效位
        for(pos=1; pos<=max_dig_num; pos++){
            //printf("digit position [%d]:\n", pos);
            //分配到不同的桶里
            int digit, idx=0;
            for(i=0; i<n; i++){
                //数位从1开始
                digit = get_pos_digit(arr[i], pos);
                rdx_arr[digit][0]++;
                idx = rdx_arr[digit][0];
                rdx_arr[digit][idx]=arr[i];
                //printf("%d, pos %d, digit %d, entry index %d, number in radix bucket %d\n", arr[i], pos, digit, idx, rdx_arr[digit][idx]);
            }
    
            //收集并重新排序数组同时清空每个桶内数组
            int j=0;
            for(i=0; i<RDX_WIDTH; i++){
                //跳过那些空桶
                if(rdx_arr[i][0]==0)
                    continue;
                //printf("bucket [%d], entry number:%d\n", i, rdx_arr[i][0]);
                //输出每个桶内的数据
                for(k=1; k<=rdx_arr[i][0]; k++){
                    arr[j++]=rdx_arr[i][k];
                    //打印出该位数对应的桶内的数字
                    //printf("%d ", rdx_arr[i][k]);
                }
                //printf("\n");
                //让桶内数据清空，以免影响下个数位的排序
                for(k=0; k<=n; k++)
                    rdx_arr[i][k]=0;
            }
            /*
            printf("\n");
            //打印出本次排序的数组
            for(i=0; i<n; i++)
                printf("%d ", arr[i]);
            printf("\n-------------------\n");
            */
        }
    
        //释放内存
        for(i=0; i<RDX_WIDTH; i++)
            free(rdx_arr[i]);
    }
    
    
    //非稳定计数排序算法
    void count_sort(int arr[], int n){
        int max, min, range, i;
    
        //统计该数组的最大值和最小值
        max=min=arr[0];
        for(i=1; i<n; i++){
            if(max<arr[i])
                max=arr[i];
            if(min>arr[i])
                min=arr[i];
        }
    
        //申请辅助计数数组，并初始化
        range=max-min+1;
        int* parr=(int*)malloc(sizeof(int) * range);
        if(parr==NULL){
            printf("FATAL: no enough memory space to allocate counting array!!!");
            exit(-1);
        }
        memset(parr, 0, sizeof(int) * range);
    
        //统计数组中每个元素出现的次数
        for(i=0; i<n; i++)
            parr[arr[i]-min]++;
    
        //输出排序数组
        int idx=0;
        for(i=0; i<range; i++)
            while(parr[i]--){
                arr[idx++]=i+min;
            }
    
        //释放资源
        free(parr);
    }
    
    //稳定性计数排序算法
    void count_sort_v2(int arr[], int n){
        int max, min, range, i;
    
        //统计该数组的最大值和最小值
        max=min=arr[0];
        for(i=1; i<n; i++){
            if(max<arr[i])
                max=arr[i];
            if(min>arr[i])
                min=arr[i];
        }
    
        //申请辅助计数数组，并初始化
        range=max-min+1;
        //printf("max:%d, min:%d, range:%d\n", max, min, range);
    
        int* parr=(int*)malloc(sizeof(int) * (range+1));
        if(parr==NULL){
            printf("FATAL: no enough memory space to allocate counting array!!!");
            exit(-1);
        }
        memset(parr, 0, sizeof(int) * (range+1));
    
        //动态分配一个临时数据用来存放排序后的数组数据
        int *tmp;
        if((tmp=(int*)malloc(sizeof(int) * (n+1))) == NULL){
            printf("FATAL: no enough memory space to store sorted array!!!");
            exit(-1);
        }
        memset(tmp, 0, sizeof(int)*(n+1));
    
        //统计数组中每个元素出现的次数
        for(i=0; i<n; i++){
            parr[arr[i]-min]++;
        }
    /*
        for(i=0; i<range; i++)
            printf("%d ", parr[i]);
        printf("\n");
    */
    
        //调整计数数组的值以反映它前面的数组偏移
        for(i=1; i<range; i++)
            parr[i] += parr[i-1];
    /*
        for(i=0; i<range; i++)
            printf("%d ", parr[i]);
        printf("\n");
    */
        //用计数去定位它所在的每个元素(逆序)
        //现在parr包含每个元素在有序数组中的偏移量
        for(i=n-1; i>=0; i--){
            //arr[i]在有序数组中的偏移是parr[arr[i]-min]-1
            tmp[parr[arr[i]-min] - 1] = arr[i];
            parr[arr[i]-min]--;
        }
    /*
        for(i=0; i<n; i++)
            printf("%d ", tmp[i]);
        printf("\n");
    */
        //复制排序数组到原来的数组中
        memcpy(arr, tmp, sizeof(int) * n);
    /*
        for(i=0; i<n; i++)
            printf("%d ", arr[i]);
        printf("\n");
    */
    
        //释放资源
        free(parr);
        free(tmp);
    }
    
    //------------------- test framework------------------------
    
    //生成指定大小的随机数组
    void generate_array(int arr[], int n){
        int i;
        for(i=0; i<n; i++)
            arr[i] = i;
        for(i=0; i<n; i++){
            int j=rand()%(i+1);
            if(i != j)
                swap(arr, i, j);
        }
        //将最后排序的数组打印出来
        /*for(i=0; i<n; i++)
            printf("%d ", i);
        printf("\n"); */
    }
    
    //检查排序之后的数组
    void check_sorted_array(int arr[], int n){
        int i, fail=0;
        for(i=0; i<n; i++)
            if(arr[i] != i){
                fail++;
                printf("sort fails: idx:%d, arr[idx]:%d\n", i, arr[i]);
            }
        printf("check sorted array completed, fail total:%d\n", fail);
    }
    
    //复制指定大小的数组内容
    void copy_array(int lhs[], const int rhs[], int n){
        int i;
        for(i=0; i<n; i++)
            lhs[i] = rhs[i];
    }
    
    
    #define MaxSize 7000
    int Arr1[ MaxSize ] = {};
    int Arr2[ MaxSize ] = {};
    
    int main(){
        int i;
    
        //连续进行10次各种排序算法的测试
        for(i=0; i<10; i++){
            generate_array(Arr2, MaxSize);
            copy_array(Arr1, Arr2, MaxSize);
            insert_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------insert sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            shell_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------shell sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            bubble_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------bubble sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            quick_sort(Arr1, 0, MaxSize-1);
            check_sorted_array(Arr1, MaxSize);
            printf("----------quick sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            select_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------select sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            heap_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------heap sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            merge_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------merge sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            bucket_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------bucket sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            radix_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------radix sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            count_sort(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------count sort ok--------\n");
    
            copy_array(Arr1, Arr2, MaxSize);
            count_sort_v2(Arr1, MaxSize);
            check_sorted_array(Arr1, MaxSize);
            printf("----------count sort2 ok--------\n");
    
        }
    
        return 0;
    }
    
    //--------------------------------------------------
    
    /*
    int main(){
        int i,j,t;
        int a[50], n;
    
        //读入数据
        printf("please input array size(<=50):\n");
        scanf("%d\n", &n);
        for(i=0; i<n; i++)
            scanf("%d", &a[i]);
    
        //使用各种算法排序
        //insert_sort(a, n);
        //shell_sort(a, n);
        //bubble_sort(a, n);
        //quick_sort(a, 0, n-1);
        //select_sort(a, n);
        //heap_sort(a, n);
        //merge_sort(a,n);
        //bucket_sort(a, n);
        //radix_sort(a, n);
        //count_sort(a, n);
        //count_sort_v2(a, n);
    
        //输出排序之后的结果
        for(i=0; i<n; i++)
            printf("%d ", a[i]);
        printf("\n");
    
        //暂停退出，等待用户输入
        getchar();
    
        return 0;
    }
    */

下面是快速排序的运行截图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhb182Mjc_size_16_color_FFFFFF_t_70][]

![20190315195349952.png][]

参考文献

\[1\].Weiss《数据结构与算法分析：c语言描述》(第二版)第七章

\[2\].Kyle Loudon著，肖翔，陈舸译《算法精解--c语言描述》(中文版)p.255

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhb182Mjc_size_16_color_FFFFFF_t_70]: /images/20220307/0c72e72cd3b444b39cc17de77129901b.png
[20190315195349952.png]: /images/20220307/866ab7006e674be682ac91a3a779633e.png