八大排序算法(C语言版)之插入排序

这篇具有很好参考价值的文章主要介绍了八大排序算法(C语言版)之插入排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录:

八大排序算法:

超链接:
插入排序
选择排序
交换排序
归并排序
非比较排序

一、排序的概念

1.1 排序的概念

排序:所谓排序,就是使一串记录, 按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j], 且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 排序的应用

排序的目的通常是为了方便查找,或者统计最多或者最少的重复次数。
1.游戏竞赛。 游戏规则是随机一组30张图片,要求参加比赛的10人在30秒之内把图片按照从小到大顺序排序,时间最少的获胜。
2.调查问卷。 在1~10000中随机生成N个数,对于重复的数只保留一个,不同的数对应着不同学生的学号,再把这些数从小到大排序,按顺序找同学调查。
3.颁发特等奖学金。 某个大学有n名学生,每个人都有m门课,按照综合成绩排名,需要挑出最优秀的k位学生颁发特等奖学金。

二、直接插入排序

直接插入排序的基本思想:
把待排序的内容记录并逐一与排序好的有序序列比较,插入到有序序列中,直到待排序列的记录全部插入完毕,得到一个新的有序序列,这就是直接插入排序
八大排序算法(C语言版)之插入排序,数据结构,排序算法,c语言,算法
代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <windows.h>
#define m 1000
void IsertSort(int* arr, int n)
{
    int i;
    for (i = 1; i < n; i++)//i为待排序的第一个数下标
    {
        int end = i - 1;//end 为已排好序列的尾下标
        int tmp = arr[i];//把待排序的第一个数存起来
        //遍历已排序列,进行比较然后插入,这里我进行从小到大排序
        while (end >= 0)
        {
            if (arr[end] > tmp)//如果前面的数大,就把他往后移动一个
            {
                arr[end + 1] = arr[end];
                end--;
            }
            //否则就跳出
            else
                break;
            arr[end + 1] = tmp;
        }
    }
    //打印排序后的数据
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    int head, end,arr[m];
    //srand(初始化时间),time(直接返回时间戳)
    srand((unsigned)time(NULL));

    head = clock();
    for (int i = 0; i < m; i++)
        arr[i] = rand();//,时间不停的变化,每次产生不同的随机值
    IsertSort(arr,sizeof(arr)/sizeof(arr[0]));
    end = clock();
    //排序需要花费的时间
    printf("\n%d\n ", end - head);
    return 0;
}

直接插入排序的性能总结:
1.元素集合越接近有序,直接插入排序算法的时间效率越高。
2.时间复杂度:O(N^2)
3.空间复杂度为:O(1),它是一种稳定的排序算法
4.稳定性:稳定

三、希尔排序

希尔排序又叫缩小增量法。
希尔排序的基本思想:
先选定一个整数,然后把待排序的记录分成这个整数的组,所有距离为这个整数的记录被分在同一个组,并对每一个组内的记录进行排序。先预排序,然后在插入排序。

八大排序算法(C语言版)之插入排序,数据结构,排序算法,c语言,算法
代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <Windows.h>
#define m 10000
SheelSort(int* arr, int n)
{
  int gap = 3;
    //多趟
 for(int j=0;j<gap; j++)
     //每组进行插入排序
        for (int i =j; i < n - gap; i += gap)
        {
            //单趟
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0)
            {
                if (arr[end] < tmp)//从大到小排序
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                    break;   
            }
            arr[end + gap] = tmp;
        }
}
int main()
{
    int head, tail, i;
    int arr[m] = {0};
    srand((unsigned)time(NULL));
    
    for (i = 0; i < m; i++)
        arr[i] = rand()%1000;
    head = clock();
    SheelSort(arr, sizeof(arr) / sizeof(arr[0]));
    tail = clock();
    printf("%d ", tail - head);

    return 0;
}

效率如下
八大排序算法(C语言版)之插入排序,数据结构,排序算法,c语言,算法
我们可以优化一下(减少一个循环,但是效率还是差不多得,而且代码更简洁):

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <Windows.h>
#define m 10000
SheelSort_1(int* arr, int n)
{
    int gap = 3;
        //按顺序,一组一组排序
        for (int i = 0; i < n - gap; i ++)
        {
            //单趟
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0)
            {
                if (arr[end] < tmp)//从大到小排序
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                    break;
            }
            arr[end + gap] = tmp;
        }
}
int main()
{
    int head, tail, i;
    int arr[m] = {0};
    srand((unsigned)time(NULL));
    
    for (i = 0; i < m; i++)
        arr[i] = rand()%1000;
    head = clock();
    SheelSort_1(arr, sizeof(arr) / sizeof(arr[0]));
    tail = clock();
    printf("%d ", tail - head);

    return 0;
}

八大排序算法(C语言版)之插入排序,数据结构,排序算法,c语言,算法
我们可以得知预排序的意义
1.gap越大,大的数可以更快的到后面,小的数可以更快到前面,gap越大跳的越快,越不接近有序。
2.gap越小,大的小的数挪动越慢,越接近有序。
3.gap= =1,就是直接插入排序。
但是我们不知道gap取什么值最好
我们在把代码变一变,让gap无论是多少,最后都等于gap= =1.(gap >1为预排序)

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <Windows.h>
#define m 10000
SheelSort_3(int* arr, int n)
{
    int gap = n;
    while(gap >1)//先预排序,预排序结束后,直接插入排序
    {
    gap=gap/3+1;
    //gap=gap/2;
        //按顺序,一组一组排序
        for (int i = 0; i < n - gap; i ++)
        {
            //单趟
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0)
            {
                if (arr[end] < tmp)//从大到小排序
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                    break;
            }
            arr[end + gap] = tmp;
        }
        }
}
int main()
{
    int head, tail, i;
    int arr[m] = {0};
    srand((unsigned)time(NULL));
    
    for (i = 0; i < m; i++)
        arr[i] = rand()%1000;
    head = clock();
    SheelSort_3(arr, sizeof(arr) / sizeof(arr[0]));
    tail = clock();
    printf("%d ", tail - head);

    return 0;
}

计算它的时间复杂度?

1.gap很大时gap=n / 3+1,可分为n/3组数据,每组3个元素,每组最坏的比较次数为3次所以一共:n / 3 * 3次。
2.gap很小时,gap=1,每组1个元素,很接近有序,间距为gap的这些数据,数据往后挪动的次数:n。
3.gap很大时,n / 9个组,9个元素,每组最坏比较36次。(1+2……+8),间距为gap的这些数据。合计挪动数据:n / 9* 36=4n次
4.外面那个循环运算了log3^N次
总结:合计n / gap组,每组gap个,每组插入:1+2+3+……+gap。合计:(1+gap) * gap / 2
时间复杂度O(N^1.3)最好情况

稳定性:不稳定

四、排序算法复杂度及稳定性分析

如图:
八大排序算法(C语言版)之插入排序,数据结构,排序算法,c语言,算法
表格:
八大排序算法(C语言版)之插入排序,数据结构,排序算法,c语言,算法文章来源地址https://www.toymoban.com/news/detail-733739.html

到了这里,关于八大排序算法(C语言版)之插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】八大排序

    初看这些概念可能一脸懵,但是没有关系,等下面学完几种排序之后在来看这些概念非常容易理解。 排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的

    2024年02月01日
    浏览(59)
  • 数据结构之八大排序算法

    排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 下面是常见的排序算法: 直接插入排序是一种简单的插入排序法,其基本思想是: 把待排序的元素按其值的大小逐个插入到一个已经排好序的有序序列中,直到所有的

    2023年04月14日
    浏览(61)
  • 【数据结构】八大排序之简单选择排序算法

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 目录 一.简单选择排序简介及思路 二.简单选择排序的代码实现 三.简单选择排序的优化 四.简单选择排序的时间复杂度分析 结语 简单选择排序算法(Simple Selection Sort) 是一种简单直观的 选择排序算

    2024年02月01日
    浏览(78)
  • 【数据结构】 常见的八大排序算法

    排序有 内部排序和外部排序 ,内部排序是数据记录在内存中进行排序,这里八大排序就是内部排序,指直接插入,希尔,选择,堆排,冒泡,快排,归并,计数。 下面让我们来共同学习这八大排序吧!🤗🤗🤗 什么是外部排序: 外排序是数据量较大,内存放不下,数据放到外

    2024年02月12日
    浏览(112)
  • 【数据结构】--八大排序算法【完整版】

    本文主要讲解代码及代码思路,涵盖八大排序的全面知识点 ———————————————— 目录 一、直接插入排序 二、希尔排序(直接插入排序的改良版) 三、选择排序(直接选择排序) 四、堆排序 五、冒泡排序 六、快速排序 1、 左右指针法 2、挖坑法: 3、前后指针

    2024年02月16日
    浏览(46)
  • 第五章 数据结构与算法——八大排序

    目录 一、排序的概念及其运用 二、八大排序的原理及其实现(升序为例) (一)、直接插入排序 (二)、希尔排序(也叫缩小增量排序)(重要) 1.原理: 2.该排序一般分为两个步骤: 3.预排序过程: 4.预排序的意义(升序为例): 5.希尔排序的特点: 6.希尔排序代码实现

    2024年02月19日
    浏览(52)
  • 【数据结构初阶】八大排序算法+时空复杂度

    学会控制自己是人生的必修课 1.直接插入排序思想: 假设现在已经有一个有序序列,如果有一个数字插入到这段序列的末尾,我们会选择拿这个数和它前面的每个数字都比较一遍,如果前面的数字比他大,那我们就让前面的数字赋值到这个被插入的数字位置,依次与前面的数

    2024年02月01日
    浏览(117)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

    1. 插入排序(insertion-sort):                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(56)
  • 【数据结构】八大排序算法(内含思维导图和画图分析)

    作者主页: paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏:

    2024年02月08日
    浏览(63)
  • 手把手教你 ,带你彻底掌握八大排序算法【数据结构】

    直接插入排序是一种简单的插入排序法,其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 可以理解为一遍摸扑克牌,一边进行排序 在待排序的元素中,假设前面n-1(其中n=2)个数

    2024年02月02日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包