关于排序:菜鸟必看的排序算法简单通俗及代码实现几张图带你吃透排序算法

一、插入排序

插入排序算法是所有排序办法中最简略的一种算法，其次要的实现思维是将数据依照肯定的程序一个一个的插入到有序的表中，最终失去的序列就是曾经排序好的数据。

间接插入排序是插入排序算法中的一种，采纳的办法是：在增加新的记录时，应用程序查找的形式找到其要插入的地位，而后将新记录插入。

很多初学者所说的插入排序，实际上指的就是间接插入排序算法，插入排序算法还包含折半插入排序、2- 路插入排序，表插入排序和希尔排序等，后序文章都会一一讲到。

例如采纳间接插入排序算法将无序表 {3,1,7,5,2,4,9,6} 进行升序排序的过程为：

• 首先思考记录 3，因为插入排序刚开始，有序表中没有任何记录，所以 3 能够间接增加到有序表中，则有序表和无序表能够如图 1 所示：

图 1 间接插入排序（1）

• 向有序表中插入记录 1 时，同有序表中记录 3 进行比拟，1<3，所以插入到记录 3 的左侧，如图 2 所示：

图 2 间接插入排序（2）

• 向有序表插入记录 7 时，同有序表中记录 3 进行比拟，3<7，所以插入到记录 3 的右侧，如图 3 所示：

图 3 间接插入排序（3）

• 向有序表中插入记录 5 时，同有序表中记录 7 进行比拟，5<7，同时 5>3，所以插入到 3 和 7 两头，如图 4 所示：

图 4 间接插入排序（4）

• 向有序表插入记录 2 时，同有序表中记录 7 进行比拟，2<7，再同 5，3，1 别离进行比拟，最终确定 2 位于 1 和 3 两头，如图 5 所示：

图 5 间接插入排序（5）

• 照此法则，顺次将无序表中的记录 4，9 和 6 插入到有序表中，如图 6 所示：

图 6 顺次插入记录 4，9 和 6

间接插入排序的具体代码实现为：

#include <stdio.h>
// 自定义的输入函数
void print(int a[], int n ,int i){printf("%d:",i);
    for(int j=0; j<8; j++){printf("%d",a[j]);
    }
    printf("n");
}
// 间接插入排序函数
void InsertSort(int a[], int n)
{for(int i= 1; i<n; i++){if(a[i] < a[i-1]){// 若第 i 个元素大于 i-1 元素则直接插入；反之，须要找到适当的插入地位后在插入。int j= i-1;
            int x = a[i];
            while(j>-1 && x < a[j]){  // 采纳程序查找形式找到插入的地位，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = x;      // 插入到正确地位
        }
        print(a,n,i);// 打印每次排序后的后果
    }
}
int main(){int a[8] = {3,1,7,5,2,4,9,6};
    InsertSort(a,8);
    return 0;
}

运行后果为：

1:13752496
2:13752496
3:13572496
4:12357496
5:12345796
6:12345796
7:12345679

间接插入排序算法自身比拟简洁，容易实现，该算法的工夫复杂度为 O(n2)。

支付学习材料和视频 Q 群：1070240985

关注 UP 长时间更新分享 C /C++ 语言根底等编程干货技术，工具安装包和学习材料已备好。

材料内容包含：

2 小时把握《互联网聊天室零碎架构》
C/C++ 打造逆向工具《端口扫描神器》
IOCP 高性能服务器之《客户端压力测试零碎》
C/C++ 打造繁难《TCP 服务器端》程序
2 小时分析 C /C++ 编程精髓《指针详解》
面试官必考的《算法设计之链表》
腾讯 QQ 之《极速文件传输工具》
C、C++ 打造《服务器设计模型》
C/C++ 开发《系统文件浏览器工具》
C/C++ 开发《太空大战游戏》
手把手写《愤恨的小鸟弹球》游戏
等等 ……..

收费报名直通车：https://ke.qq.com/course/417774?flowToken=1028592 这是一门真正适宜任何零根底学习的入门课，由教学教训超过十年的大咖级老师解说。课程知识点通俗易懂，可能将每一个知识点落地到理论案例。

二、冒泡排序

起泡排序，别名“冒泡排序”，该算法的核心思想是将无序表中的所有记录，通过两两比拟关键字，得出升序序列或者降序序列。

例如，对无序表 {49，38，65，97，76，13，27，49} 进行升序排序的具体实现过程如图 1 所示：

图 1 第一次起泡

如图 1 所示是对无序表的第一次起泡排序，最终将无序表中的最大值 97 找到并存储在表的最初一个地位。具体实现过程为：

1. 首先 49 和 38 比拟，因为 38<49，所以两者替换地位，即从（1）到（2）的转变；
2. 而后持续下标为 1 的同下标为 2 的进行比拟，因为 49<65，所以不挪动地位，（3）中 65 同 97 比拟得悉，两者也不须要挪动地位；
3. 直至（4），97 同 76 进行比拟，76<97，两者替换地位，如（5）所示；
4. 同样 97>13（5）、97>27（6）、97>49（7），所以通过一次冒泡排序，最终在无序表中找到一个最大值 97，第一次冒泡完结；

因为 97 曾经判断为最大值，所以第二次冒泡排序时就须要找出除 97 之外的无序表中的最大值，比拟过程和第一次完全相同。

通过第二次冒泡，最终找到了除 97 之外的又一个最大值 76，比拟过程齐全一样，这里不再形容。

通过一趟趟的比拟，一个个的“最大值”被找到并挪动到相应地位，直到检测到表中数据曾经有序，或者比拟次数等同于表中含有记录的个数，排序完结，这就是起泡排序。

起泡排序的具体实现代码为：

#include <stdio.h>
// 替换 a 和 b 的地位的函数
void swap(int *a, int *b);
int main()
{int array[8] = {49,38,65,97,76,13,27,49};
    int i, j;
    int key;
    // 有多少记录，就须要多少次冒泡，当比拟过程，所有记录都依照升序排列时，排序完结
    for (i = 0; i < 8; i++){
        key=0;// 每次开始冒泡前，初始化 key 值为 0
        // 每次起泡从下标为 0 开始，到 8-i 完结
        for (j = 0; j+1<8-i; j++){if (array[j] > array[j+1]){
                key=1;
                swap(&array[j], &array[j+1]);
            }
        }
        // 如果 key 值为 0，表明表中记录排序实现
        if (key==0) {break;}
    }
    for (i = 0; i < 8; i++){printf("%d", array[i]);
    }
    return 0;
}
void swap(int *a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

运行后果为：

13 27 38 49 49 65 76 97

应用起泡排序算法，其工夫复杂度同理论表中数据的无序水平无关。若表中记录自身为正序寄存，则整个排序过程只需进行 n-1（n 为表中记录的个数）次比拟，且不须要挪动记录；若表中记录为逆序寄存（最坏的状况），则须要 n- 1 趟排序，进行 n(n-1)/2 次比拟和数据的挪动。所以该算法的工夫复杂度为O(n2)。

首先祝贺您，可能认真的浏览到这里，如果对局部了解不太明确，倡议先将文章珍藏起来，而后对不分明的知识点进行查阅，而后在进行浏览，相应你会有更深的认知。如果您喜爱这篇文章，就点个赞或者【关注我】吧！！我的项目实战直通车一起学习