C语言所有经典排序方法的实现代码

运行结果正确
还是快速排序难一些。

完整代码

#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include<malloc.h>
void swap(int *a,int *b);
void select_sort(int arr[],int n);
void tra_arr(int arr[],int n);
void insert_sort(int arr[],int n);
void shell_sort(int arr[],int n);
void perc_down(int arr[],int i,int n);
void heap_sort(int arr[],int n);
void merge(int arr[],int temp_arr[],int left_start,int right_start
            ,int right_end);
void m_sort(int arr[],int temp_arr[],int left,int right);
void merge_sort(int arr[],int n);
int get_pri(int arr[],int left,int right);
void q_sort(int arr[],int left,int right);
void quick_sort(int arr[],int n);
int main(){
    int arr[100]={
        10,9,8,7,6,5,4,3,2,1
    };
    select_sort(arr,10);
    printf("\n简单选择排序结果\n");
    tra_arr(arr,10);

    int arr1[100]={
        10,9,8,7,6,5,4,3,2,1
    };
    insert_sort(arr1,10);
    printf("\n插入排序结果\n");
    tra_arr(arr1,10);

    int arr2[100]={
        10,9,8,7,6,5,4,3,2,1
    };
    shell_sort(arr2,10);
    printf("\n希尔排序结果\n");
    tra_arr(arr2,10);

    int arr3[100]={
        10,9,8,7,6,5,4,3,2,1
    };
    heap_sort(arr3,10);
    printf("\n堆排序结果\n");
    tra_arr(arr3,10);

    int arr4[100]={
         10,9,8,7,6,5,4,3,2,1
    };
    merge_sort(arr4,10);
    printf("\n归并排序结果\n");
    tra_arr(arr4,10);

    int arr5[100]={
         10,9,8,7,6,5,4,3,2,1
    };
    quick_sort(arr5,10);
    printf("\n快速排序结果\n");
    tra_arr(arr5,10);

    return 0;
}
void swap(int *a,int *b){
    //在函数内部，如果打算接收的是指针的地址，那就不要加*,
    //如果想要的是值，那就加*,我也很讨厌指针，但是没办法
    int t=*a;
    *a=*b;
    *b=t;
}
//简单选择排序
void select_sort(int arr[],int n){
    int min;
    //这个过程一时半会讲不清楚，看书会清楚一些
    for(int i=0;i<n;i++){
        min=i;

        for(int j=i+1;j<n;j++){
            if(arr[i]>arr[j]){
                min=j;
            }
        }
        //经过上面的里层for，就找到了最小的元素的下表
        swap(&arr[i],&arr[min]) ;
    }
}
//插入排序
void insert_sort(int arr[],int n){
    int temp,j;
    for(int i=1;i<n;i++){
        temp=arr[i];
        for(j=i;j>0&&arr[j-1]>temp;j--){
            //后挪
            arr[j]=arr[j-1];
        }
        //现在就找到空出来的插入位置了
        arr[j]=temp;
    }
}
//希尔排序
void shell_sort(int arr[],int n){
    int in,i,j,temp;
    //本来这个排序是很好理解的，就是这个外层的循环
    //故弄玄虚，你就把他理解成一个简单的，递减的数组就行
    //而且这个2的指数递减的序列的时间复杂度是很坏的
    //最好使用SED或者HIB序列会好很多,这里只是演示
    //两个里层的for就是插入排序,仔细看看就能看懂

    for(in=n/2;in>0;in=in/2){
        for(i=in;i<n;i++){
            temp=arr[i];
            for(j=i;j>=in;j=j-in){
                if(arr[j-in]>temp){
                    //后挪
                    arr[j]=arr[j-in];
                }
                else{
                    //arr[j-in]<temp，说明找到了
                    break;
                }
            }
            //上面执行完，肯定找到了插入位置
            arr[j]=temp;
        }
    }
}
//首先是下滤操作
//i是根，n是heap的规模
//这里的下滤针对最大堆
void perc_down(int arr[],int i,int n){
    int child,temp;
    //仔细想想，其实和插入排序差不多
    //首先把i取出来，把i在堆里面所在的位置空出来
    //这里和原来建堆的下滤又不一样，这里没有设置哨兵
    for(temp=arr[i];(2*i+1)<n;i=child){
        child=2*i+1;
        //如果当前儿子不是最后一个，说明还有右儿子
        //两者取最大
        if(child!=(n-1)&&arr[child]<arr[child+1]){
            child++;
        }
        if(temp<arr[child]){
            arr[i]=arr[child];
        }
        else{
            //当前取出来的值终于大于两个儿子时。
            break;
        }

    }
    //上面轮完之后，肯定找到了一个儿子比我们取出来的值还要小的
    arr[i]=temp;
}
void heap_sort(int arr[],int n){
    int i;
    //建堆
    for(i=n/2;i>=0;i--){
        perc_down(arr,i,n);
    }
    //取最大值放在最后已经舍弃的位置上，下滤剩下的堆
    for(i=n-1;i>0;i--){
        //取最大值放在最后已经舍弃的位置上
        swap(&arr[0],&arr[i]);
        // 滤剩下的堆
        perc_down(arr,0,i);
    }
}
//归并排序
//第一步，写一个将两个已经排好序列的归并
void merge(int arr[],int temp_arr[],int left_start,int right_start
            ,int right_end)
{
    int i,temp_start,elem_num,left_end;
    temp_start=left_start;
    left_end=right_start-1;
    elem_num=right_end-left_start+1;
    //归并的核心
    while(left_start<=left_end&&right_start<=right_end){
        if(arr[left_start]<=arr[right_start]){
            temp_arr[temp_start++]=arr[left_start++];
        }
        else{
            temp_arr[temp_start++]=arr[right_start++];
        }
    }
    while(left_start<=left_end){
        temp_arr[temp_start++]=arr[left_start++];
    }
    while(right_start<=right_end){
        temp_arr[temp_start++]=arr[right_start++];
    }
    //重新拷回去，记住，这里归并的只是原来数组的一部分，所以不能从头开始
    for(i=0;i<elem_num;i++,right_end--) {
        arr[right_end]=temp_arr[right_end];
    }
}
//第二步，递归调用归并，将数组不断分割
void m_sort(int arr[],int temp_arr[],int left,int right){
    //tra_arr(arr,10);
    int center;
    //递归结束条件
    if(left<right){
        center=(right+left)/2;
        m_sort(arr,temp_arr,left,center);
        m_sort(arr,temp_arr,center+1,right);
        merge(arr,temp_arr,left,center+1,right);
    }
}
//第三步，初始化临时数组
void merge_sort(int arr[],int n){
    int *temp_arr;
    temp_arr=(int*)malloc(n*sizeof(int));
    m_sort(arr,temp_arr,0,n-1);
    free(temp_arr);
}

//快速排序
//首先，实现三数中值分割法,取一个“裁判” （中值）
int get_pri(int arr[],int left,int right){
    int center=(left+right)/2;
    if(arr[left]>arr[center]){
        swap(&arr[left],&arr[center]);
    }
    if(arr[left]>arr[right]){
        swap(&arr[left],&arr[right]);
    }
    if(arr[center]>arr[right]){
        swap(&arr[center],&arr[right]);
    }
    //把中值扔到倒数第二个，因为上述操作已经让倒数第一大于中值了
        swap(&arr[center],&arr[right-1]);

    return arr[right-1];

}
//其次，实现分而治之
void q_sort(int arr[],int left,int right){
    int i,j,pri;
    //如果规模已经小于三了，就不要再分而治之了，没得分了
    if(right-left>=3){
        //取中值
        pri= get_pri(arr,left,right);
        //取左右往中间靠拢的两个指针i,j
        i=left;
        j=right-1;
        //开始判断
        while(1){
            //如果当前i对应的值小于裁判，继续推进
            while(arr[++i]<pri);
            // 如果当前i对应的值大于裁判，继续推进
            while(arr[--j]>pri);
            //上面走完，肯定碰到硬杈了，在i和j没有错位的情况下
            //交换
            if(i<j){
                swap(&arr[i],&arr[j]);
            }
            else{
                break;
            }
        }
        swap(&arr[i],&arr[right-1]);
        //这个i的作用远不止此,这个i还记录了上一个裁判的位置
        //开始对分下来的两个部分进行同样的操作
        q_sort(arr,left,i-1);
        q_sort(arr,i+1,right);
    }
    //如果递归到规模已经无法再分了
    //就用普通的方法排序
    else{
        /*这里稍微讲一下
        数组和指针实际上是一样的东西
        到这里了，那肯定就剩一个或者两个元素了
        所以数组的开头变成left所指的位置，现在left所在位置的下标
        就是0，所以后面的n也要相应变化*/
        insert_sort(arr+left,right-left+1);
    }

}
//最后包装一下
void quick_sort(int arr[],int n){
    q_sort(arr,0,n-1);
}
//遍历数组
void tra_arr(int arr[],int n){
    for(int i=0;i<n;i++){
        printf("%d  ",arr[i]);
    }
    printf("\n");
}

以上就是C语言所有经典排序方法的实现代码的详细内容，更多关于C语言排序方法的的资料请关注服务器之家其它相关文章！

原文链接：https://blog.csdn.net/jiangjun_feng/article/details/117404323