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

插入排序是排序算法的一种，它不改变原有的序列（数组），而是创建一个新的序列，在新序列上进行操作。

这里以从小到大排序为例进行讲解。

基本思想及举例说明

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

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

下面，以对 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，待排序元素为空，排序结束）

算法总结及实现

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

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

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

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

以上就是对插入排序的详细介绍，希望能帮助C语言开发的同学理解掌握插入排序。

赞 (0)

相关推荐

  • C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • c++几种基本的插入排序(图文)

    c++几种基本的插入排序(图文)

    1.插入排序 插入排序(Insertion Sort)是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 时间复杂度:O(n^2); 算法描述: 1.从第一个元素开始,该元素可以认为已经被排序 2.取出下一个元素,在已经排序的元素序列中从后向前扫描 3.如果

  • java直接插入排序示例

    java直接插入排序示例

    影响排序效率的一般从3个方面比较:数据比较的次数,数据移动的次数,内存空间占用的大小.我们就冒泡排序.选择排序.插入排序.快速排序做一个总的比较.一般情况下不会使用冒泡排序算法,因为它的比较次数和移动次数在几种排序算法中都是最多的,它的唯一好处是算法简单,易于理解,所以在数据量很小的时候它会有些应用价值.选择排序在比较次数上和冒泡排序一样,都是n的平方,但它把交换的次数降低到了最低,所以在数据量很小且交换数据相对于比较数据更加耗时的情况下,可以应用选择排序.在大多数情况下,当数据量比较小或基本上

  • JS实现冒泡排序，插入排序和快速排序并排序输出

    JS实现冒泡排序，插入排序和快速排序并排序输出

    在一次面试中被问到了此问题,但是真是懵了,没能回答上来,后来通过JS整理了一下,在结合html代码做了一个文本框,把输入的内容从文本框排序输出,再次不做叙述了,下面通过一段代码给大家展示下: 以下是代码: index.html <!DOCTYPE html> <html> <head> <title>Sorting</title> <link rel="stylesheet" type="text/css&qu

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • C++插入排序算法实例

    插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

  • python 实现插入排序算法

    复制代码 代码如下: #!/usr/bin/python def insert_sort(array): for i in range(1, len(array)): key = array[i] j = i - 1 while j >= 0 and key < array[j]: array[j + 1] = array[j] j-=1 array[j + 1] = key if __name__ == "__main__": array = [2, 4, 32, 64,

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

    插入排序是排序算法的一种,它不改变原有的序列(数组),而是创建一个新的序列,在新序列上进行操作. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的. 在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素.第一轮时,将第一个元素作为排序好的子数组,插入第二个元素:第二轮,将前两个元素作为排序好的数组,插入第三个元素.以此类

  • Go语言实现遗传算法的实例代码

    在没介绍正文之前先给大家补充点go语言基本知识及实例. Go 语言教程 Go 是一个开源的编程语言,它能让构造简单.可靠且高效的软件变得容易. Go是从2007年末由Robert Griesemer, Rob Pike, Ken Thompson主持开发,后来还加入了Ian Lance Taylor, Russ Cox等人,并最终于2009年11月开源,在2012年早些时候发布了Go 1稳定版本.现在Go的开发已经是完全开放的,并且拥有一个活跃的社区. Go 语言特色 简洁.快速.安全 并行.有

  • Python实现七个基本算法的实例代码

    1.顺序查找 当数据存储在诸如列表的集合中时,我们说这些数据具有线性或顺序关系. 每个数据元素都存储在相对于其他数据元素的位置. 由于这些索引值是有序的,我们可以按顺序访问它们. 这个过程产实现的搜索即为顺序查找. 顺序查找原理剖析:从列表中的第一个元素开始,我们按照基本的顺序排序,简单地从一个元素移动到另一个元素,直到找到我们正在寻找的元素或遍历完整个列表.如果我们遍历完整个列表,则说明正在搜索的元素不存在. 代码实现:该函数需要一个列表和我们正在寻找的元素作为参数,并返回一个是否存在的布尔值

  • 用js实现简单算法的实例代码

    一.冒泡排序 var arr1=[3,9,2,7,0,8,4]; for(var i=0;i<arr1.length;i++){ for(var j=i+1;j<arr1.length;j++){ var temp=0; if(arr1[i]>arr1[j]){ temp=arr1[i]; arr1[i]=arr1[j]; arr1[j]=temp; } } } alert(arr1); 二.快速排序 var a=[3,5,0,9,2,7,5]; function quickSort(a

  • Java编程基于快速排序的三个算法题实例代码

    快速排序原理简介 快速排序是我们之前学习的冒泡排序的升级,他们都属于交换类排序,都是采用不断的比较和移动来实现排序的.快速排序是一种非常高效的排序算法,它的实现,增大了记录的比较和移动的距离,将关键字较大的记录从前面直接移动到后面,关键字较小的记录从后面直接移动到前面,从而减少了总的比较次数和移动次数.同时采用"分而治之"的思想,把大的拆分为小的,小的拆分为更小的,其原理如下:对于给定的一组记录,选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,

  • python实现kmp算法的实例代码

    kmp算法 kmp算法用于字符串的模式匹配,也就是找到模式字符串在目标字符串的第一次出现的位置 比如 abababc 那么bab在其位置1处,bc在其位置5处 我们首先想到的最简单的办法就是蛮力的一个字符一个字符的匹配,但那样的时间复杂度会是O(m*n) kmp算法保证了时间复杂度为O(m+n) 基本原理 举个例子: 发现x与c不同后,进行移动 a与x不同,再次移动 此时比较到了c与y, 于是下一步移动成了下面这样 这一次的移动与前两次的移动不同,之前每次比较到上面长字符串的字符位置后,直接把模

  • Java实现Shazam声音识别算法的实例代码

    Shazam算法采用傅里叶变换将时域信号转换为频域信号,并获得音频指纹,最后匹配指纹契合度来识别音频. 1.AudioSystem获取音频 奈奎斯特-香农采样定理告诉我们,为了能捕获人类能听到的声音频率,我们的采样速率必须是人类听觉范围的两倍.人类能听到的声音频率范围大约在20Hz到20000Hz之间,所以在录制音频的时候采样率大多是44100Hz.这是大多数标准MPEG-1 的采样率.44100这个值最初来源于索尼,因为它可以允许音频在修改过的视频设备上以25帧(PAL)或者30帧( NTSC

  • C语言动态顺序表实例代码

    C语言动态顺序表实例代码

    目录 顺序表概念: 一.准备工作 二.顺序表的基本操作  1.顺序表的初始化函数 2.尾插函数(在尾部插入数据) 3.头插函数(在数组头部插入数据)  4.尾删函数 5.头删函数 6.在第pos的位置插入数据 7.删除第pos个位置的数据 8.修改第pos个位置的数据 9.查找函数. 10.销毁函数 11.打印函数 三.总代码: 顺序表概念:         顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构.一般情况下用数组存储.在数组上完成数据的增删查改. 代码解析: 一.准备工

  • C语言打印各种图案实例代码

    1.线段图案 #include<stdio.h> int main() { int a = 0; while(~scanf("%d",&a)) { int i = 0; for(i=0;i<a;i++) { printf("*"); } printf("\n"); } return 0; } 2.正方形图案 #include<stdio.h> int main() { int a = 0; while(~sc

  • C语言实现三子棋实例代码

    我是半自主的完成了这个程序,看了B站鹏哥视频并仔细思索后才做出来的,我没有完全采用他的方法,导致程序还有一些不足之处,还请各位大佬指出. 首先,我将该程序的实现分为3个板块,main,game.h,和game.c; 代码如下: #define _CRT_SECURE_NO_WARNINGS #include"game.h" void menu() { printf("****************************************\n"); prin

随机推荐