美文网首页
算法—排序篇

算法—排序篇

作者: 土豆骑士 | 来源:发表于2020-05-20 15:51 被阅读0次

    本文要点:冒泡排序、选择排序、插入排序、希尔排序、堆排序

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

    排序是常用的相关函数:

    //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");
    }
    

    1、冒泡排序

    冒泡排序(Bubble Sort) 一种交换排序,它的基本思想就是: 两两比较相邻的记录的关键字,如果 反序则交换,直到没有反序的记录为⽌。(每一趟遍历,将大值移动到序列末尾)

    冒泡排序初级版本

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

    正宗冒泡排序算法 (对于已经排好序的部分,不再继续进行遍历)

    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);
            }
        }
    }
    

    .冒泡排序-对顺序表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;
                    
                }
            }
        }
    }
    

    2、选择排序

    简单排序算法(Simple Selection Sort) 就是通过 n-i 次关键词比较,从n-i+1个记录中找出关键字最小的记录,并和第i(1<=i<=n) 个记录进行交换。

    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);
        }
    }
    

    3、直接插入排序

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

    示例
    示例续
    void InsertSort(SqList *L) {
        
        int i,j;
        
        int temp=0;//L->r[0] 哨兵 可以把temp改为L->r[0]
        
        //假设排序的序列集是{0,5,4,3,6,2};
        //i从2开始的意思是我们假设5已经放好了. 后面的牌(4,3,6,2)是插入到它的左侧或者右侧
        for(i=2;i<= L->length;i++) {
            
            if (L->r[i] < L->r[i-1]) {//需将L->r[i]插入有序子表
                
                temp = L->r[i];//设置哨兵 可以把temp改为L->r[0]
                
                for(j = i-1;L->r[j] > temp;j--) {//j = i-1 之前的便是排好序的
    
                    L->r[j+1]=L->r[j];//记录后移
                }
                
                L->r[j+1]=temp;//插入到正确位置 可以把temp改为L->r[0]
            }
        }
    }
    

    4、希尔排序 ==>基于插入排序的改进

    在插入排序之前,将整个序列调整成基本有序. 然后再对全体序列列进⾏一次直接插入排序。


    模拟

    **希尔排序思想: **希尔排序是把记录按下标的一定增量分组,对每组使用直接插⼊入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量量减⾄1时,整个序列恰被分成 一组,算法便终⽌。


    增量分组,对比前移
    缩减增量,分组,直接插入排序
    缩减增量到1,再直接插入排序
    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;// 3 可以换做别的值,2.
            //③ 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);
    }
    

    时间复杂度分析:

    increment
    5、堆排序

    佛洛依德发明的一种数据结构,大顶堆,小顶堆。
    大顶堆:二叉树,跟节点值 大于左右节点。
    小顶堆:二叉树,跟节点值 小于左右节点。


    大顶堆,小顶堆

    是具有下⾯性质的完全⼆叉树: 每个结点的值都⼤于或等于其左右孩⼦结点的值,称为大顶堆;

    ⼆叉树性质5: 如果对一颗有n个结点的完全二叉树的结点按层序编号,对任⼀结点i (1 ≤ i ≤ n) 有:

    • 如果 i = 1 ,则结点 i 是二叉树的根. ⽆双亲. 如果 i > 1,则其双亲是结点 [ i / 2 ];
    • 如果 2i > n ,则结点 i ⽆左孩子 (结点i 为叶子结点); 否则左孩⼦子是结点 2i;
    • 如果 2i + 1 > n ,则结点 i ⽆右孩子; 否则其右孩子是结点 2i+1;

    根据完全二叉树的基本性质和“堆”的特性可以演化出 堆排序

    堆排序(Heap Sort) 就是利用堆(假设我们选择⼤顶堆)进行排序的算法。

    它的基本思想:

    1. 将待排序的序列构成⼀个⼤顶堆,此时,整个序列的最大值就是堆顶的根结点,将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值);
    2. 然后将剩余的n-1个序列重新构成一个队,这样就会得到n个元素的次大值, 如此重复执行,就能得到一个有序列了;

    调整模拟:

    大顶堆调整
    调整续
    调整续
    排序模拟:
    排序模拟

    大顶堆调整函数;

    /*
     条件: 在L.r[s...m] 记录中除了下标s对应的关键字L.r[s]不符合大顶堆定义,其他均满足;
     结果: 调整L.r[s]的关键字,使得L->r[s...m]这个范围内符合大顶堆定义.
     */
    void HeapAjust(SqList *L,int s,int m){
        
        int temp,j;
        //① 将L->r[s] 存储到temp ,方便后面的交换过程;
        temp = L->r[s];
        
        //② j 为什么从2*s 开始进行循环,以及它的递增条件为什么是j*2
        //因为这是颗完全二叉树,而s也是非叶子根结点. 所以它的左孩子一定是2*s,而右孩子则是2s+1;(二叉树性质5)
        for (j = 2 * s; j <=m; j*=2) {
            
            //③ 判断j是否是最后一个结点, 并且找到左右孩子中最大的结点;
            //如果左孩子小于右孩子,那么j++; 否则不自增1. 因为它本身就比右孩子大;
            if(j < m && L->r[j] < L->r[j+1])
                ++j;
            
            //④ 比较当前的temp 是不是比较左右孩子大; 如果大则表示我们已经构建成大顶堆了;
            if(temp >= L->r[j])
                break;
            
            //⑤ 将L->[j] 的值赋值给非叶子根结点
            L->r[s] = L->r[j];
            //⑥ 将s指向j; 因为此时L.r[4] = 60, L.r[8]=60. 那我们需要记录这8的索引信息.等退出循环时,能够把temp值30 覆盖到L.r[8] = 30. 这样才实现了30与60的交换;
            s = j;
        }
        
        //⑦ 将L->r[s] = temp. 其实就是把L.r[8] = L.r[4] 进行交换;
        L->r[s] = temp;
    }
    
    void HeapSort(SqList *L){
        int I;
        
        //1.将现在待排序的序列构建成一个大顶堆;
        //将L构建成一个大顶堆;
        //i为什么是从length/2.因为在对大顶堆的调整其实是对非叶子的根结点调整.
        for(i=L->length/2; i>0;i--){
            HeapAjust(L, i, L->length);
        }
        
        
        //2.逐步将每个最大的值根结点与末尾元素进行交换,并且再调整成大顶堆
        for(i = L->length; i > 1; i--){
            
            //① 将堆顶记录与当前未经排序子序列的最后一个记录进行交换;
            swap(L, 1, i);
            //② 将L->r[1...i-1]重新调整成大顶堆;
            HeapAjust(L, 1, i-1);
        }
    }
    

    时间复杂度:O(nlogn)。

    测试:

    #define N 9
    int main(int argc, const char * argv[]) {
        // insert code here...
        printf("Hello, 排序算法\n");
        
        int i;
        int d[N]={9,1,5,8,3,7,4,6,2};
        //int d[N]={9,8,7,6,5,4,3,2,1};
        //int d[N]={50,10,90,30,70,40,80,60,20};
        SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
        
        for(i=0;i<N;i++)
            l0.r[i+1]=d[i];
        
        l0.length=N;
        l1=l2=l3=l4=l5=l6=l7=l8=l9=l10=l0;
        
        printf("排序前:\n");
        print(l0);
        printf("\n");
        
        //1.初级冒泡排序
        printf("初级冒泡排序:\n");
        BubbleSort0(&l0);
        print(l0);
        printf("\n");
        
        //2.冒泡排序
        printf("冒泡排序:\n");
        BubbleSort111(&l1);
        BubbleSort(&l1);
        print(l1);
        printf("\n");
        
        //3.冒泡排序优化
        printf("冒泡排序(优化):\n");
        BubbleSort2(&l2);
        print(l2);
        printf("\n");
        
        //4.选择排序
        printf("选择排序:\n");
        SelectSort(&l3);
        print(l3);
        printf("\n");
        
        //5.直接插入排序
        printf("直接插入排序:\n");
        InsertSort(&l4);
        print(l4);
        printf("\n");
        
        //6.希尔排序
        printf("希尔排序:\n");
        shellSort(&l5);
        print(l5);
        printf("\n");
        
        //7.堆排序
        //注意:执行对排序时更换一下数据源. 这里我为什么要这组数据,原因是为了与下标个位数字讲解时进行区分;因为在这个算法讲解过程,出现了很多下标的相关计算.
        /* int d[N]={50,10,90,30,70,40,80,60,20}; */
        printf("堆排序:\n");
        HeapSort(&l6);
        print(l6);
        printf("\n");
        
        
        
        
        printf("\n");
        return 0;
    }
    // 1,2,3,4,5,6,7,8,9
    

    相关文章

      网友评论

          本文标题:算法—排序篇

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