C语言之常用的排序算法

####前提

前提:
稳定的含义:未排序前两个相同的数在排序完成后是否交换了位置，也就意味着是否更多的没必要的消耗了资源
稳定:没交换位置 不稳定:交换了位置
例如：
未排序前:3(下标为1),3(下标为2) 排序后: 3(下标为2),3(下标为1)

冒泡排序

冒泡排序思想:每一轮选出最大或者最小的值放在最后面，属于稳定排序
平均时间复杂度:O(N^2) 最好:O(N) 最坏:O(N^2)
空间复杂度:O(1)

//冒泡排序
void maoPao(int a[],int length)//a[]:代码自助式
{
    //原始顺序
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    //冒泡排序思想:每一轮选出最大或者最小的值放在最后面，属于稳定排序
    //平均时间复杂度:O(N^2)  最好:O(N) 最坏:O(N^2)
    //空间复杂度:O(1)
    for(int i=0;i<length;i++){
        for(int j=0;j<length-i-1;j++){
            if(a[j]>a[j+1]){//最大放后面
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
        // //解开为每轮的排序过程
        // for(int i=0;i
        //     printf("%d ",a[i]);
        // }
        // printf("\n");
    }
    //排序后
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

选择排序

选择排序原理:分为排序段(最初无)和未排序段(从0开始)，找出未排序段元素的最值追加在排序段后面
根据下标来运算,属于不稳定排序
平均时间复杂度:O(N^2) 最好:O(N^2) 最坏:O(N^2)
空间复杂度:O(1)

//选择排序
void xuanZhe(int a[],int length)
{
    //原始顺序
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    //选择排序原理:分为排序段(最初无)和未排序段(从0开始)，找出未排序段元素的最值追加在排序段后面
    //根据下标来运算,属于不稳定排序
    //平均时间复杂度:O(N^2)  最好:O(N^2) 最坏:O(N^2)
    //空间复杂度:O(1)
    for(int i=0;i<length-1;i++){
        int max=i;//最大值暂设为未排序的首个元素
        for(int j=i+1;j<length;j++){
            if(a[max]<a[j]){
                max = j;//找到更大值，将最大值下标设为该下标，然后让该下标的元素进行后续的对比
            }
        }

        if(i!=max){//如果最大值下标不是之前那个循环开始时初设的下标，便开始交换
            int t = a[i];
            a[i] = a[max];
            a[max] = t;
        }
        // //解开为每轮的排序过程
        // for(int i=0;i
        //     printf("%d ",a[i]);
        // }
        // printf("\n");
    }
    //排序后
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

插入排序

插入排序原理:分为排序段(最初为0)和未排序段(从1开始)，未排序段元素依次与排序段元素对比并插入
根据值来运算,根据下标运算会在移动的时候自己跟自己比较，达不到想要的效果，属于稳定排序
平均时间复杂度:O(N^2) 最好:O(N) 最坏:O(N^2)
空间复杂度:O(1)

//插入排序
void chaRu(int a[],int length)
{
    //原始顺序
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    //插入排序原理:分为排序段(最初为0)和未排序段(从1开始)，未排序段元素依次与排序段元素对比并插入
    //根据值来运算,根据下标运算会在移动的时候自己跟自己比较，达不到想要的效果，属于稳定排序
    //平均时间复杂度:O(N^2)  最好:O(N) 最坏:O(N^2)
    //空间复杂度:O(1)
    for(int i=1;i<length;i++){//无序段
        int dp = a[i];//记录带插入的数据
        int j=i;//验证是不是不需要移动，即待插入元素在排序段中元素相比便是最大
        while(j>0&&dp<a[j-1]){//有序段
            a[j] = a[j-1];
            j--;
        }
        if(j!=i-1){
            a[j] = dp;
        }
        // //解开为每轮的排序过程
        // for(int i=0;i
        //     printf("%d ",a[i]);
        // }
        // printf("\n");
    }
    //排序后
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

希尔排序

希尔排序原理:将一定数量间隔(第一次最佳是元素个数/2)的元素归为一个组进行排序，然后再将数量间隔按比例缩小重复上一次动作
运用到了二分法的思想以及插入排序、另外，与数组元素个数为奇数还是偶数无关，无非是分组多包含一个
注意事项:避免序列中的值(尤其是相邻的值)互为倍数的情况、最后一个步长为1，即插入排序
根据间隔度来操作，属于不稳定排序
平均时间复杂度:O(NlogN) 最好:O(Nlog2N) 最坏:O(N*log2N)
空间复杂度:O(1)

//希尔排序
void xiEr(int a[],int length)
{
    //原始顺序
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    //希尔排序原理:将一定数量间隔(第一次最佳是元素个数/2)的元素归为一个组进行排序，然后再将数量间隔按比例缩小重复上一次动作
    //运用到了二分法的思想以及插入排序、另外，与数组元素个数为奇数还是偶数无关，无非是分组多包含一个
    //注意事项:避免序列中的值(尤其是相邻的值)互为倍数的情况、最后一个步长为1，即插入排序
    //根据间隔度来操作，属于不稳定排序
    //平均时间复杂度:O(N*logN)  最好:O(N*log2N) 最坏:O(N*log2N)
    //空间复杂度:O(1)
    int gap = length/2;
    // int gap=1;
    // while(gap
    //     gap = gap*4+1;//一个好的希尔排序最重要的便是步长(间隔=步长+1)的确定
    // }
    while(gap>0){
        // printf("gap:%d\n",gap);
        for(int i=gap;i<length;i++){//每组元素的排序板块，不同组便从头开始
            int t = a[i];
            int j = i-gap;
            // printf("j:%d\n",j);
            while(j>=0&&a[j]>t){//升序亦或者降序,>=是多个排序的关键，运用到了插入排序
                a[j+gap] = a[j];
                // printf("%d\n",j);
                j -= gap;//进行那一组的元素坐标迁移，如果<0便退出，这是j为负数
                // printf("..%d\n",j);
            }
            a[j+gap] = t;//恢复坐标，并对其进行赋值(替换)
        }
        gap = gap/2;//步长缩小一半(一定条件下可随意缩小,如 /2、/3,性能会不一样)
        // printf("======\n");
        // //解开为每轮的排序过程
        // for(int i=0;i
        //     printf("%d ",a[i]);
        // }
        // printf("\n");
    }
    //排序后
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

归并排序

归并排序原理:N个小空间，不断开辟小空间的两倍空间，利用两个指针将小空间的元素进行排序并放在新开辟的大空间中，重复直至完成全排序
运用到了化整为零的思想，用空间换时间，属于稳定排序
平均时间复杂度:O(NlogN) 最好:O(NlogN) 最坏:O(N*logN)
空间复杂度:O(N)

//归并排序
void guiBing(int a[],int length)
{
    //原始顺序
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    //归并排序原理:N个小空间，不断开辟小空间的两倍空间，利用两个指针将小空间的元素进行排序并放在新开辟的大空间中，重复直至完成全排序
    //运用到了化整为零的思想，用空间换时间，属于稳定排序
    //平均时间复杂度:O(N*logN)  最好:O(N*logN) 最坏:O(N*logN)
    //空间复杂度:O(N)
    if(length<2){ return; }//长度为2，不用再使用归并排序这种消耗空间的算法
    int mid=length/2;   //数组对半分，二分法思想,进行各自的排序，空间换时间

    int *p,*q;//从属语句不能是声明，也就意味着if语句后面不能声明变量
    if(length%2==0){
        p = malloc(mid*sizeof(4));
        q = malloc(mid*sizeof(4));
    }else{//数组元素为奇数
        p = malloc(mid*sizeof(4));
        q = malloc((mid+1)*sizeof(4)); 
    }
    //.......提示:在堆区开辟空间更好(第一次是一个元素一个空间，放进去)，因为可以封装成一个函数，因为要无数次开辟，释放同理
    //将数组分批装进去
    //再定义两个指针指向两个新建的数组头，依次对比放入一个更大的空间即可
    //C语言实现太复杂，C++的容器更好实现一点
    //广度比深度更重要，所以就不编程了
    free(p);
    free(q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

快速排序

快速排序原理:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
运用到了递归以及二分法的思想，属于不稳定排序
平均时间复杂度:O(NlogN) 最好:O(NlogN) 最坏:O(N^2)
空间复杂度:O(logN)

//一次排序的声明
int onceSort(int *s,int i,int j);
//查看数组元素函数声明
void show(int a[],int length);
//快速排序
void kuaiSu(int a[],int low,int hight)
{
    //快速排序原理:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，
    //             再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
    //运用到了递归以及二分法的思想，属于不稳定排序
    //平均时间复杂度:O(N*logN)  最好:O(N*logN) 最坏:O(N^2)
    //空间复杂度:O(logN)
    int mid = 0;//以第一个元素为基准值
    if(low<hight){
        //一次排序的结果
        mid = onceSort(a,low,hight);
        // show(a,11);  //每轮变化情况
        //左集合排序调用 kuaiSu()
        kuaiSu(a,low,mid-1);
        //右集合排序调用 kuaiSu()
        kuaiSu(a,mid+1,hight);
    }
}
//一次排序
int onceSort(int *s,int i,int j)
{
    int tmp = s[i];//以对应下标最小的值为基准
    while(i<j){
        //先进行上边界值的判断,如果上边界值大于关键值，则 j-- 
        while(i<j && tmp<=s[j])
            j--;
        // printf("-");show(s,11);//验证指针停止移动后的情况    printf()为每次变成情况
        //当循环结束时，如果 is[j],则必须将 s[j] 放在 tmp 左边
        if(i<j){
            s[i] = s[j];
            // printf("---");show(s,11);//验证更换值后是顺序，即将小值放基准值左边
        }
        //再进行下边界值的判断，如果下边界值 小于 关键值，则 i++
        while(i<j && tmp>=s[i])
            i++;
        // printf("-");show(s,11);printf("-\n");
        //同理,这时,tmp
        if(i<j){
            s[j] = s[i];
            // printf("---");show(s,11);printf("---\n");
        }
    }
    s[i] = tmp;//将基准值插入小的右边
    // printf("tmp_back:");show(s,11);
    //返回基准值的下标
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

main函数：

int main(int argc,char *argv[])
{
    int a[11]={8,9,1,2,7,2,3,5,4,6,0};
    // maoPao(a,11);
    // xuanZhe(a,11);
    // chaRu(a,11);
    // xiEr(a,11);
    // guiBing(a,11);
    //快速排序
    show(a,11);
    kuaiSu(a,0,10);
    show(a,11);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

参考文献:
①https://cloud.tencent.com/developer/article/1377630
②https://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html