【自考】插入排序

2024-08-26 19:18
文章标签 插入排序 自考

本文主要是介绍【自考】插入排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        软考自考中数据结构与算法基础中很重要的一部分就是排序算法,以前总觉得这部分挺不好理解的这次自考软考都要用到,必须要好好理解一下了,今天先总结一下插入排序。

        【知识点】

         排序算法分为:插入排序、选择排序、交换排序、归并排序和基数排序,插入排序直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序),插入排序主要有直接插入排序和希尔插入排序。

        1、概念

        插入排序:基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。插入排序的主要方法有直接插入排序和希尔插入排序。

         2、直接插入排序:

        即当插入第i个记录时,R1,R2,R3.......Ri-1均已排好序,将第i个记录Ri依次与R1,R2,R3.......Ri-1进行比较,找到合适的位置,将其正确插入到序列中。当一趟比较完成时,我们要将待比较数值置入比它小的数值的后一位,直到所有的排序完成。直接排序简单明了,但是速度比较慢。

         扑克牌相信每个人都玩过,在我们玩牌的过程中多数人的习惯是一边摸牌,一边理牌,也有些是全部发完在整理。其实这个整理牌的过程就相当于我们的直接插入排序。假如你手上有这样一幅牌,我相信每个人都会马上整理成有序的,然后就是等着赢了。

                              

         直接插入排序其实是比较简单的,纸牌的例子是从这里看到的,里面讲的很清楚,不明白的可以再看看。

         3、希尔排序

         希尔排序(Shell Sort)是插入排序的一种,因D.L.Shell于1959年提出而得名。

        基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

         看定义感觉挺复杂的,其实关键点就是他的增量d,增量如何求?举个例子更好说明一下:

          比如对关键码{49,38,65,97,76,13,27,49,55,04}进行排序,这里n=10,所以第一个增量d1=2/n=5;也就是将数列分成五组,每两个数一组,第一个距它的同组的距离也为5,分成的五组是{49,13}、{38,27}、{65,49}、{97,55}、{76,04},然后对这五组进行插入排序,组成新的一组数列。以此类推,第二次排序的增量d2=d1/2=3,第三次增量d3=d2/2=1。

         一般取d1=2/n,di+1=di/2,需要注意的是如果增量结果是偶数,则加1,保证di是奇数。

         该数列初始状态如下:

        

         第一次排序:增量为5,分成5组,将相同颜色的分为一组,对每组进行插入排序

        

        第一次排序结果如下:

       

         第二次排序:增量为3,分成3组,将相同颜色的分为一组,对每组进行插入排序

       

         第二次排序结果如下:

       

         第二次排序:增量为1,也就是对整组进行插入排序,结果如下:

       

        希尔排序的执行时间是依赖于增量序列的,好的增量序列有如下共同特征:最后一个增量必须是1;应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

        在排序算法中感觉考得比较多的还是时间复杂度及其稳定性,各类排序的精华部分都总结在如下表中: 

                   

       【小结】

        各类排序关键还在于如何理解,可以多联系生活,找些自己容易理解的例子,这样也更容易掌握。现在准备软考自考,感觉每天的时间都不够用的,每天晚上小组内一起学习讲题,学习起来也很有动力,接下来的日子继续加油!


这篇关于【自考】插入排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1109446

相关文章

(六十四)第 10 章 内部排序(静态链表的插入排序)

示例代码 staticLinkList.h // 静态链表的插入排序实现头文件#ifndef STATIC_LINK_LIST_H#define STATIC_LINK_LIST_H#include "errorRecord.h"#define SIZE 100#define NUM 8typedef int InfoType;typedef int KeyType;ty

6.1排序——插入排序与希尔排序

本篇博客来梳理两种常见排序算法:插入排序与希尔排序 常见的排序算法如图 写排序算法的原则:先写单趟,再写整体 一、直接插入排序 1.算法思想 先假定第一个数据有序,把第二个数据插入;再假设前两个数据有序,把第三个数据插入…以此类推,直到整个序列有序 2.具体操作(以排成升序为例) (1)单趟:针对单个数据 假设[0,end]有序,处理end+1处数据(用tmp存起来,原因:挪数据的时

插入排序 【InsertionSort】

插入排序 插入排序的工作方式像排序一手扑克牌。 假设左手的牌是排序好的,桌面上的是未知的牌 1. 开始时,我们的左手为空并且桌子上的牌面向下。 2. 然后,我们每次从桌子上拿走一张牌并将它插入左手正确的位置。 为了找到插入的正确位置,我们将要插入的牌与左手的牌挨着比较,直接找到合适的位置并插入进去。 在实际的实现过程中,我们可以将数组的第0个元素看成是已经排序好的,然后从第二个元素开始进

完整版自考西方文论选复习笔记资料

西方文论选读复习资料 1.柏拉图:古希腊哲学家,苏格拉底的学生。公园前387年在雅典城外建立学园开始授徒讲学,撰写对话。柏拉图的作品即《柏拉图文艺对话集》中讨论美学和文艺理论问题较多的有:《大希庇阿斯》、《伊安》、《高吉阿斯》、《会饮》、《斐德若》、《理想国》、《斐利布斯》、《法律》等。 ▲柏拉图《伊安》和《斐若德》内容:主要阐述了"迷狂说"和"灵魂回忆说":柏拉图认为,高明的诗人都是凭灵

《数据结构(C语言版)第二版》第八章-排序(8.2-插入排序)

【8.2插入类、8.3交换类、8.4选择类、8.5归并类、8.6分配类 都属于内部排序。 】 8.2 插入排序 8.2.1 直接插人排序 【算法特点】 (1)稳定排序。 (2)算法简便,且容易实现。 (3)也适用于链式存储结构,只是在单链表上无需移动记录,只需修改相应的指针。 (4)更适合于初始记录基本有序(正序)的情况。 当初始记录无序,n较大时,此算法时间复杂度较高,不宜采用。 #in

25版王道数据结构课后习题详细分析 第八章 8.2 插入排序

一、单项选择题 ———————————————————— ———————————————————— 解析:直接插入排序在最坏的情况下要做n(n-1)/2次关键字的比较,当n=5时, 关键字的比较次数为10。注意不考虑与哨兵的比较。 正确答案: ———————————————————— ———————————————————— 解析:由于序列初始基本有序,因此使用直接插入排序

冒泡排序;选择排序;插入排序;快排;判断大小端;位运算

1.冒泡排序:基础        时间复杂度来说:o(n^2) 从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。 #include <stdio.h>int main(void){int str[32] = 0;int i = 0;int j = 0;int len = sizeof(str) / sizeof(str[0]);

排序算法(动图详细讲解)(直接插入排序,希尔排序,堆排序,冒泡排序)

前言:         排序的方式有很多种,不同的排序思想是不一样的。         但是排序的时间复杂度和空间复杂度也都有区别。         例如:         最简单的冒泡排序,时间复杂度为O(N)         对排序的时间复杂度为O(N*logN)。 接下来就来仔细分析每种排序的思路,并写出代码。 插入排序:  基本思想:         直接插入排序是一种简

内部排序之一:插入排序和希尔排序的N中实现

前言    本来想将所有的内部排序总结为一篇博文,但是随着研究的深入,还是放弃了这个念头,斟前酌后,还是觉得分开来写比较好,具体原因,看完本篇博文也就自然明了了。    本篇文章主要探讨插入排序和希尔排序,之所将二者放在一起,很明显,是因为希尔排序是建立在插入排序的基础之上的。    注:以下各排序算法的N种实现方法大部分都是我根据算法思想,自己写出来的,或者是参考其本身的经典实现,

C语言——插入排序

先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。 #include <stdio.h> #include <stdlib.h> void insertion_sort(int *arr, int n) {     for (int i = 1; i < n; i++)     {         int key = arr[i];