首页 > 其他分享 >11.4 插入排序

11.4 插入排序

时间:2024-06-09 12:31:12浏览次数:31  
标签:11.4 插入排序 元素 base 排序 复杂度

目录

11.4   插入排序

11.4.1   算法流程

11.4.2   算法特性

11.4.3   插入排序的优势


11.4   插入排序

插入排序(insertion sort)是一种简单的排序算法,它的工作原理与手动整理一副牌的过程非常相似。

具体来说,我们在未排序区间选择一个基准元素,将该元素与其左侧已排序区间的元素逐一比较大小,并将该元素插入到正确的位置。

图 11-6 展示了数组插入元素的操作流程。设基准元素为 base ,我们需要将从目标索引到 base 之间的所有元素向右移动一位,然后将 base 赋值给目标索引。

单次插入操作

图 11-6   单次插入操作

11.4.1   算法流程

插入排序的整体流程如图 11-7 所示。

  1. 初始状态下,数组的第 1 个元素已完成排序。
  2. 选取数组的第 2 个元素作为 base ,将其插入到正确位置后,数组的前 2 个元素已排序
  3. 选取第 3 个元素作为 base ,将其插入到正确位置后,数组的前 3 个元素已排序
  4. 以此类推,在最后一轮中,选取最后一个元素作为 base ,将其插入到正确位置后,所有元素均已排序

插入排序流程

图 11-7   插入排序流程

示例代码如下:

insertion_sort.c

/* 插入排序 */
void insertionSort(int nums[], int size) {
    // 外循环:已排序区间为 [0, i-1]
    for (int i = 1; i < size; i++) {
        int base = nums[i], j = i - 1;
        // 内循环:将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while (j >= 0 && nums[j] > base) {
            // 将 nums[j] 向右移动一位
            nums[j + 1] = nums[j];
            j--;
        }
        // 将 base 赋值到正确位置
        nums[j + 1] = base;
    }
}

11.4.2   算法特性

相关文章

  • 冒泡排序、插入排序、快速排序
    三种排序:冒泡排序、插入排序、快速排序规则:冒泡排序:每一轮循环后,最大的一个数被交换到末尾,因此,下一轮循环就可以“刨除”最后的数,每一轮循环都比上一轮循环的结束位置靠前一位。插入排序:将待排序数组分为已排序和未排序两部分,初始已排序部分只包含第一个元素。然后,从第二个元素......
  • 插入排序详解及Java代码实现
    在计算机科学中,排序是一种基本的操作,它广泛应用于各种数据处理场景。插入排序(InsertionSort)是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的......
  • 插入排序
    //通过指针交换两个元素的值voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}/*****************************************************************name;InsertSort*function:sort*parameter;*@intarr[]*......
  • 数据结构排序算法之直接插入排序与希尔排序【图文详解】
    P.S.:以下代码均在VS2019环境下测试,不代表所有编译器均可通过。P.S.:测试代码均未展示头文件stdio.h的声明,使用时请自行添加。                                             博主主页:LiUEEEEE         ......
  • 11.4 命令判断
    11.4命令判断11.4.1用到的三个特殊符号:;&&||1.; 分号:不考虑指令的相关性,连续性,分号;不保证命令全部执行成功的命令:cd/opt/&&touch/opt/test.txt&&ls解释:命令1;命令2`命令1`不论执行成功与否,`命令2`一定会执行......
  • 数据结构的直接插入排序(C语言版)
    一.直接插入排序的基本概念1.直接插入排序的基本思想将数组分为已排序和未排序两部分。每次从未排序部分取出一个元素,将其插入到已排序部分的合适位置,使得已排序部分保持有序。重复步骤2,直到整个数组有序。2.排序的工作原理假设前i-1个元素已经有序,现在要将......
  • 七大排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、归并排序、快速排序
    以下内容转载自文章1.插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找到已排序元素中小于等于tem的元素5.tem插入到该元素的后面,如果已排序所有元......
  • 03 插入排序
    1.插入排序的含义类似扑克牌,假设认为0-0位置有序,再把0-1的位置变有序,循环直到所有的有序。每次拿取右侧的数字,一个一个对比放到左侧来。2.示例代码definsertion_sort(arr):ifarrisNoneorlen(arr)<2:returnforiinrange(1,len(arr)):#......
  • 冒泡排序、插入排序、选择排序
    冒泡排序思想:从左到右,元素交换。第一个元素和第二个元素比较,若第一个元素大于第二个,则交换元素,再第二个元素与第三个元素比较,依次比较,直到比较完。则最尾部的元素是最大值。voidmaopao(inta[5],intsi){for(inti=0;i<si-1;i++){for(intj=0;......
  • 插入排序
    插入排序简单来说假设数组第一个元素为一个有序序列然后将后面的无序序列依次与第一个元素比较更具大小决定待插入元素插入的位置。、、、//插入排序是吧无序序列中的元素依次插入到有序序列中,一般是从有序序列的尾部开始比较voidInsertSort(intbuf[10],intbufsize){......