美文网首页iOS 面试
数据结构和算法 -- 冒泡排序、选择排序、插入排序、希尔排序

数据结构和算法 -- 冒泡排序、选择排序、插入排序、希尔排序

作者: iOS的火影乱斗 | 来源:发表于2021-04-20 16:34 被阅读0次

    你关注 我送礼:感谢各位的观看,别忘了点个赞,同时我在这里还给各位准备了你们专属资料,关注我,获得私信进裙了解,不要忘记看私信消息啊。或者直接进群有管理员主动找你,回复[7]之后,你就能拿到各自想要的资料。别忘了去领取啊

    定义

    假设含有n个记录的序列列为(r1,r2,.....,rn). 其相应的关键字分别为{k1,k2,......,kn}. 需确定 1,2,......,n 的⼀一种排序p1,p2,......pn. 使其相应的关键字满⾜足kp1 <= kp2 <= ...... <= kpn ⾮非递减(或 ⾮非递增)关系. 即使得到序列列成为⼀一个按关键字有序的序列列(rp1,rp2,...,rpn).这样得出操作称为排 序

    排序分类
    • 内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;
    • 外排序:由于排序的记录个数太多,不不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进⾏行行

    准备工作

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    
    //1.排序算法数据结构设计
    //用于要排序数组个数最大值,可根据需要修改
    #define MAXSIZE 10000
    typedef struct
    {
        //用于存储要排序数组,r[0]用作哨兵或临时变量
        int r[MAXSIZE+1];
        //用于记录顺序表的长度
        int length;
    }SqList;
    
    
    //2.排序常用交换函数实现
    //交换L中数组r的下标为i和j的值
    void swap(SqList *L,int i,int j)
    {
        int temp=L->r[i];
        L->r[i]=L->r[j];
        L->r[j]=temp;
    }
    
    //3.数组打印
    void print(SqList L)
    {
        int i;
        for(i=1;i<L.length;i++)
            printf("%d,",L.r[i]);
        printf("%d",L.r[i]);
        printf("\n");
    }
    

    有资料需求的可以了解下,有关于包括 数据结构、底层进阶、图形视觉、音视频、架构设计、逆向安防、RxSwift、flutter,算法等方面的资料,面试资料就在群文件里面可自行下载,891点击 488进入 181
    有什么问题也可以直接在里面提出来,互相交流,同时内有好友发内推机会,一起共同进步!

    冒泡排序

    冒泡排序(Bubble Sort) ⼀一种交换排序,它的基本思想就是:两两⽐比较相邻的记录的关键字,如果反序则交换,直到没有反序的记录为⽌

    初级版本

    初级版本冒泡排序就是利用两个循环,依次进行遍历交换

    //4. 冒泡排序-对顺序表L进行交换排序(冒泡排序初级版本)
    void BubbleSort0(SqList *L){
       
        int i,j;
        for (i = 1; i < L->length; i++) {
            for (j = i+1; j <= L->length; j++) {
                if(L->r[i] > L->r[j])
                    swap(L, i, j);
            }
        }
    }
    
    正宗冒泡排序

    初级版本冒泡排序,每次循环后原顺序表的顺序没有根本性的变化,而正宗冒泡排序是每次遍历都会对顺序表进行一次简单排序,并且找到一个相应位置的值

    //5.冒泡排序-对顺序表L作冒泡排序(正宗冒泡排序算法)
    void BubbleSort(SqList *L){
        int i,j;
        for (i = 1; i < L->length; i++) {
            //注意:j是从后面往前循环
            for (j = L->length-1; j>=i; j--) {
                
                //若前者大于后者(注意与上一个算法区别所在)
                if(L->r[j]>L->r[j+1])
                    //交换L->r[j]与L->r[j+1]的值;
                    swap(L, j, j+1);
            }
        }
    }
    
    冒泡排序的优化

    冒泡排序有个缺陷就是,假如原来的顺序表本来就是有序的,本质上不应该再次一个个遍历,应该在知道顺序表是有序时候直接终止遍历,优化点就是创建一个flag来标示一下剩下的顺序表是否是有序的,如果是有序的直接可以break

    //6.冒泡排序-对顺序表L冒泡排序进行优化
    void BubbleSort2(SqList *L){
        int i,j;
        //flag用作标记
        Status flag = TRUE;
        
        //i从[1,L->length) 遍历;
        //如果flag为False退出循环. 表示已经出现过一次j从L->Length-1 到 i的过程,都没有交换的状态;
        for (i = 1; i < L->length && flag; i++) {
            
            //flag 每次都初始化为FALSE
            flag = FALSE;
            
            for (j = L->length-1; j>=i; j--) {
                
                if(L->r[j] > L->r[j+1]){
                //交换L->r[j]和L->r[j+1]值;
                swap(L, j, j+1);
                //如果有任何数据的交换动作,则将flag改为true;
                flag=TRUE;
                }
            }
        }
    }
    
    ##选择排序

    选择排序也是两个循环,每次内循环都找到一个最小值,然后,让最小值和待排序数据的第一个值进行交换

    //7.选择排序--对顺序表L进行简单选择排序
    void SelectSort(SqList *L){
        
        int i,j,min;
    
        for (i = 1; i < L->length; i++) {
            //① 将当前下标假设为最小值的下标
            min = i;
            //② 循环比较i之后的所有数据
            for (j = i+1; j <= L->length; j++) {
                //③ 如果有小于当前最小值的关键字,将此关键字的下标赋值给min
                if (L->r[min] > L->r[j]) {
                    min = j;
                }
            }
            
            //④ 如果min不等于i,说明找到了最小值,则交换2个位置下的关键字
            if(i!=min)
                swap(L, i, min);
        }
    }
    
    插入排序

    直接插入排序算法(Stright Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增1的有序表;
    步骤:

    用哨兵temp,记录已排序好的有序表的后面的第一个值
    再跟已排序后的有序表倒序比较,如果有序表的值大于待排序的值,那么就将已排序的有序表的值往后移一位,因为后面值已经被temp记录了
    依次往前移,直到找到已排好的有序表中的值小于temp,那么temp就应该排在该值前面
    如果待排序的值最小,那么就插在第一个位置

    //8.直接插入排序算法--对顺序表L进行直接插入排序
    void InsertSort(SqList *L){
        int i,j;
        //L->r[0] 哨兵 可以把temp改为L->r[0]
        int temp=0;
        
        //假设排序的序列集是{0,5,4,3,6,2};
        //i从2开始的意思是我们假设5已经放好了. 后面的牌(4,3,6,2)是插入到它的左侧或者右侧
        for(i=2;i<=L->length;i++)
        {
            //需将L->r[i]插入有序子表
            if (L->r[i]<L->r[i-1])
            {
                //设置哨兵 可以把temp改为L->r[0]
                //倒序遍历已排序好的部分,找到temp应该插入的位置
                temp = L->r[i];
                for(j=i-1;L->r[j]>temp;j--)
                        //记录后移
                        L->r[j+1]=L->r[j];
                
                //插入到正确位置 可以把temp改为L->r[0]
                L->r[j+1]=temp;
            }
        }
    }
    
    希尔排序

    上面插入排序,我们根据实现知道对数据量小,基本有序的数据进行排序比较高效,但是对数据量大,无序的数据,就需要对插入排序进行改进了
    希尔排序听名字就能想到是Shell提出来的,只是对直接插入排序做了一个基本的改进。什么改进呢?
    希尔排序思想:

    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;
    对增量数组每次排序后,就会将每组值小的排到前面,值大的排到后面,这样就使数组变成了基本有序了,再整体插入排序的效率就比较高了
    随着增量逐渐减少,每组包含的关键词越来越多,当增量减⾄至1时,整个序列列恰被分成 一组,算法便便终⽌

    //9.希尔排序-对顺序表L希尔排序
    void shellSort(SqList *L){
        int i,j;
        int increment = L->length;
        //0,9,1,5,8,3,7,4,6,2
        //① 当increment 为1时,表示希尔排序结束
        do{
            //② 增量序列
            increment = increment/3+1;
            //③ i的待插入序列数据 [increment+1 , length]
            for (i = increment+1; i <= L->length; i++) {
                //④ 如果r[i] 小于它的序列组元素则进行插入排序,例如3和9. 3比9小,所以需要将3与9的位置交换
                if (L->r[i] < L->r[i-increment]) {
                    //⑤ 将需要插入的L->r[i]暂时存储在L->r[0].和插入排序的temp 是一个概念;
                    L->r[0] = L->r[i];         
                    //⑥ 记录后移
                    for (j = i-increment; j > 0 && L->r[0]<L->r[j]; j-=increment) {
                        L->r[j+increment] = L->r[j];
                    }             
                    //⑦ 将L->r[0]插入到L->r[j+increment]的位置上;
                    L->r[j+increment] = L->r[0];
                }
            }
        }while (increment > 1);
    }
    

    文章到这里就结束了,你也可以私信我及时获取最新资料以及面试相关资料。如果你有什么意见和建议欢迎给我留言。

    相关文章

      网友评论

        本文标题:数据结构和算法 -- 冒泡排序、选择排序、插入排序、希尔排序

        本文链接:https://www.haomeiwen.com/subject/sxcxlltx.html