C语言插入排序算法及代码

插入排序是排序算法的一种,它不改变原有的序列(数组),而是创建一个新的序列,在新序列上进行操作。这里以从小到大排序为例进行讲解。

操作方法

  • 01

    基本思想及举例说明 插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的。

  • 02

    在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮时,将第一个元素作为排序好的子数组,插入第 二个元素;第二轮,将前两个元素作为排序好的数组,插入第三个元素。以此类推,第i轮排序时,在前i个元素的子数组中插入第i+1个元素。直到所有元素都 加入排序好数组。

  • 03

    下面,以对 3  2  4  1 进行选择排序说明插入过程,使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。第1轮[ 3 ]  [ 2  4  1 ]  (最初状态,将第1个元素分为排序好的子数组,其余为待插入元素)[ 3 ]  [ 2  4  1 ]  (由于3>2,所以待插入位置j=1)[ 2  3 ]  [ 4  1 ]  (将2插入到位置j)第2轮[ 2  3 ]  [ 4  1 ] (第1轮排序结果)[ 2  3 ]  [ 4  1 ] (由于2<4,所以先假定j=2)[ 2  3 ]  [ 4  1 ] (由于3<4,所以j=3)[ 2  3  4 ]  [ 1 ] (由于4刚好在位置3,无需插入)第3轮[ 2  3  4 ]  [ 1 ] (第2轮排序结果)[ 2  3  4 ]  [ 1 ] (由于1<2,所以j=1)[1  2  3  4 ]    (将1插入位置j,待排序元素为空,排序结束)

  • 04

    算法总结及实现 选择排序对大小为N的无序数组R[N]进行排序,进行N-1轮选择过程。首先将第1个元素作为已经排序好的子数组,然后将剩余的N-1个元素,逐个插入到已经排序好子数组;。因此,在第 i轮排序时,前i个元素总是有序的,将第i+1个元素插入到正确的位置。

  • 05

    #include<stdio.h> #include<stdlib.h> #define N 8 void insert_sort(int a[],int n); //插入排序实现,这里按从小到大排序 void insert_sort(int a[],int n)//n为数组a的元素个数 { //进行N-1轮插入过程 for(int i=1; i<n; i++) { //首先找到元素a[i]需要插入的位置 int j=0; while( (a[j]<a[i]) && (j<i)) { j++; } //将元素插入到正确的位置 if(i != j)  //如果i==j,说明a[i]刚好在正确的位置 { int temp = a[i]; for(int k = i; k > j; k--) { a[k] = a[k-1]; } a[j] = temp; } } } int  main() { int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; insert_sort(num, N); for(int i=0; i<N; i++) printf("%d  ", num[i]); printf("\n"); system("pause"); return 0; }

  • 06

    注意:插入排序是一种稳定的排序算法,不会改变原有序列中相同数字的顺序。

  • 07

    插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是 第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该 插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序 就是排好序后的顺序,所以插入排序是稳定的。

(0)

相关推荐

  • 快速排序算法的代码实现

    本文将讲述快速排序算法的代码实现:主要是java代码的实现: 操作方法 01 如图,我们首先给出全部的代码实现,大家可以先行运行实现. 02 篇幅有限,接上图,第二张图: 03 详细讲述每段代码的意思 ...

  • 插入排序算法C语言实现

    对于小规模输入,插入排序是一种非常快速的排序算法,且原理简单,结构紧凑. 插入排序的原理:从序列中第二个数A开始, 将A,插入前面已经排好的序列中,形成一个新的排序好的序列,以此类推到最后一个元素.( ...

  • C语言排序算法:[3]教你理解简单选择排序。

    简单选择排序是经常用到的一种排序算法,它的原理是什么?如何实现,坐标X为您一一解答. 操作方法 01 一.简单选择排序一句话概括:每次选择无序数列中最小的将其放在有序数列的最后. 02 二.在简单选择 ...

  • C语言排序 C语言冒泡排序算法(Bubble Sort)

    操作方法 01 冒泡排序原理: 设要排序的数据记录到一个数组中,把关键字较小的看成"较轻"的气泡,所以就应该上浮.从底部(数组下标较大的一端)开始,反复的从下向上扫描数组.进行每一 ...

  • 如何写好代码

    以硬件代码Verilog为例,其他编程语言也有许多相通甚至相同的地方.Verilog代码是硬件设计人员必须掌握,甚至要熟练运用的硬件语言,通过该Verilog代码你几乎可以实现任何你想要的功能,大到一 ...

  • C语言教程 两个整数交换

    本教程将介绍两个整数交换 操作方法 01 新建一个 两个整数交换 项目,如图所示: 02 添加一个 swap.c 文件,如图所示: 03 包含stdio.h和stdlib.h头文件,如图所示: 04 ...

  • 插入排序图文讲解

    插入排序是最简单的排序算法之一,对于有N个元素的序列,插入排序由N-1趟排序组成.它的工作原理是通过构建有序序列,对于未排序的数据,在已经排序序列中从后向前扫描,找到相应位置插入 操作方法 01 排序 ...

  • 冒泡排序算法的实现

    我们在学语言或者算法时,避免不了要学习冒泡排序的算法.本文将实现冒泡排序算法的代码实现. 操作方法 01 原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换, 这样一趟过去后,最大或 ...

  • centos中文乱码修改字符编码使用centos支持中文

    一、中文支持 安装中文语言包: 复制代码 代码如下: yum groupinstall chinese-support 修改字符编码配置,没有这个文件就创建它: 复制代码 代码如下: vim /etc ...