目录
 
一.简介
二.数组插入法排序原理
三.数组插入法排序实战
四.猜你喜欢
 
 
 
零基础 C/C++ 学习路线推荐 : C/C++ 学习目录 >> C 语言基础入门
 
 
一.简介
 
经过前面的学习，我们已经学会了数组遍历，在开发中，我们经常回碰到对数组进行排序，例如：学习成绩排序，身高排序，年龄排序等等；在 C 语言中常见的数组排序一共有四种：
 
1.冒泡法排序
2.选择法排序
3.插入法排序
4.快速法排序
 
二.数组插入法排序原理
 
将要排序的数组分成两部分，每次从后面的部分取出索引最小的元素插入到前一部分的适当位置
 
三.数组插入法排序实战
 
/******************************************************************************************/
//@Author:猿说编程
//@Blog(个人博客地址): www.codersrc.com
//@File:C语言教程 - C语言 数组排序 – 插入法排序
//@Time:2021/06/08 08:00
//@Motto:不积跬步无以至千里，不积小流无以成江海，程序人生的精彩需要坚持不懈地积累！
/******************************************************************************************/


#include<stdlib.h>
#include<stdio.h>

void main()
{
    int a[5] = { 12, 19, 2 , 993, -34 };
    int len = sizeof(a) / sizeof(int);
    for (int i = 0; i < len; i++)
    {
        printf("排序之前：index:%d  value:%d\n", i, a[i]);
    }
    //插入法排序
    for (int i = 1; i < len; i++) {
        int temp = a[i];
        int j = i - 1;
        while (temp < a[j]) {
            a[j + 1] = a[j];
            j--;
            if (j == -1) {
                break;
            }
        }
        a[j + 1] = temp;
    }
    printf("-----------------------------------\n");
    for (int i = 0;i<len;i++)
    {
        printf("排序之后：index:%d  value:%d\n", i, a[i]);
    }
    system("pause");
}

/*
输出：

排序之前：index:0  value:12
排序之前：index:1  value:19
排序之前：index:2  value:2
排序之前：index:3  value:993
排序之前：index:4  value:-34
-----------------------------------
排序之后：index:0  value:-34
排序之后：index:1  value:2
排序之后：index:2  value:12
排序之后：index:3  value:19
排序之后：index:4  value:993
请按任意键继续. . .
*/
 
四.猜你喜欢
 
安装 Visual Studio
安装 Visual Studio 插件 Visual Assist
Visual Studio 2008 卸载
Visual Studio 2003/2015 卸载
C 语言格式控制符/占位符
C 语言逻辑运算符
C 语言三目运算符
C 语言逗号表达式
C 语言 for 循环
C 语言 while 循环
C 语言 do while 和 while 循环
C 语言 switch 语句
C 语言 goto 语句
C 语言 char 字符串
C 语言 sizeof 和 strlen 函数区别
C 语言 strcpy 和 strcpy_s 函数区别
C 语言 memcpy 和 memcpy_s 区别
C 语言 数组定义和使用
C 语言 数组遍历
C 语言 数组排序 – 冒泡法排序
C 语言 数组排序 – 选择法排序
C 语言 数组排序 – 插入法排序
 
未经允许不得转载：猿说编程 » C 语言 数组排序 – 插入法排序

 
一、数组的原理和特点
 
定义:
 
一组能够存储相同数据类型的变量和集合。
 
特点如下:
 
保存同一数据类型。
 
定义数组必须要有固定长度，并且不能修改。
 
数组拥有边界检查，一旦越界，会抛出索引越界异常。
 
数组是引用数据类型,存放在堆内存中,但同时会在栈内存中存储地址值指向堆内存中的变量。
 
对象数组和基本数据类型的数组在使用上是相同的，区别是对象数组保存的是引用，基本数据类型的数组保存的是基本数据类型。
 
二、动态数组的概念
 
动态数组是指一个数组的长度可以无限进行扩充，已达到无限长度。其实质是创建一个新数组，长度在原数组的基础上扩充，放弃原来数组，然后把原数组中的元素复制到新的数组中。
 
三、如何手动实现动态数组
 
增加元素:
 
在添加元素的时判断数组是否还有剩余空间。
 
如果有剩余空间直接添加。
 
如果没有剩余空间则转到第4步。
 
创建新的数组根据扩充后的长度。
 
把原数组的数据复制到新的数组中。
 
删除元素:
 
由于数组是线性结构，通常要保证元素的连续性。当删除的元素不是数组的末尾元素时候，我们要把被删除元素之后的元素依次前移，以确保末尾会流出空余位置，便于添加新元素的时候总在末尾，也便于避免查询时候出现空指针异常。
 

 
四、具体代码实现如下
 
public void addElement(Dog dog) {
 
// 判断数组是否已满 添加元素
 
if (count >= dogs.length) {
 
// 讲原来的数组长度扩大一倍
 
int newLength = dogs.length * 2;
 
// 复制 根据原来的数组 创建一个新数组
 
dogs = Arrays.copyOf(dogs, newLength);
 
}
 
// 添加数组元素
 
dogs[count] = dog;
 
count++;
 
}
 
// 删除数组元素 根据id值来删除
 
public void removeElement(int id) {
 
// 获取要删除的对象
 
for (int i = 0; i < count; i++) {
 
if (dogs[i].getId() == id) {
 
// (覆盖)将该元素后面的元素整体向后移动
 
for (int j = i; j < count; j++) {
 
dogs[j] = dogs[j + 1];
 
// 将数组最后一个元素置空
 
dogs[count - 1] = null;
 
count--;
 
break;
 
}
 
}
 
}
 
}
 
详细代码参考地址
 
五、动态数组总结
 
变相解决了数组固定长度带来的问题。
 
使得数组成为存储效率较高的结构。
 
频繁扩充会导致性能下降，产生垃圾对象数组。
 
适合添加、查找、便利，但不适合插入和删除操作。
 
被普遍使用在ArrayList，Vector等集合中。

4 插入排序
 
在开始学习插入排序之前，让我们先对 for 循环做个补充：如下是关于 for 循环结束时，i 的取值的演示代码
 
        int i;
        for (i = 5; i >= 0; i--) {
            System.out.print(i);
        }
        System.out.println("\nfor循环结束时i=" + i);
        System.out.println("-----------------");
        for (i = 0; i <= 5; i++) {
            System.out.print(i);
        }
        System.out.println("\nfor循环结束时i=" + i);
 
运行结果：
 
543210
for循环结束时i=-1
-----------------
012345
for循环结束时i=6
 
我们可以看到，当for循环结束时，i会最后一次执行for循环语句中的i++或者i–，那么在此基础之上我们来讲讲数组排序中的插入排序。
 
4.1插入排序原理
 
插入排序是将数组分为两部分, 将后部分的首部元素逐一与前部分的每一个元素从后往前进行比较，在合理位置插入 。
插入排序算法效率要高于选择排序和冒泡排序
 
步骤
未排序数组array：[7,2,3,8,1]
第一步： 在数组中划分边界，将边界右数第一个元素array[1]赋值于temp，再将temp和7进行比较
[7｜2,3,8,1]
因temp小于7，则将array[1]的值改为array[0]的值
[7｜7,3,8,1]
遍历结束，到达尽头，不执行循环语句体，将temp值赋予array[0]，边界右移
[2,7｜3,8,1]
第二步： 将边界右数第一个元素array[2]赋值于temp，再将temp和7进行比较
[2,7｜3,8,1]
因temp小于7，则将array[2]的值改为array[1]的值
[2,7｜7,8,1]
继续遍历，因temp不小于2，则不执行循环语句体，再将temp值赋予array[1]，边界右移
[2,3,7｜8,1]
第三步： 将边界右数第一个元素array[3]赋值于temp，再将temp和8进行比较
[2,3,7｜8,1]
因temp不小于7，则不执行循环语句体，边界右移
[2,3,7,8｜1]
第四步： 将边界右数第一个元素array[4]赋值于temp，再将temp和8进行比较
[2,3,7,8｜1]
因temp小于8，则将array[4]的值改为array[3]的值，继续遍历
[2,3,7,8｜8]
因temp小于7，则将array[3]的值改为array[2]的值，继续遍历
[2,3,7,7｜8]
因temp小于3，则将array[2]的值改为array[1]的值，继续遍历
[2,3,3,7｜8]
因temp小于2，则将array[1]的值改为array[0]的值，继续遍历
[2,2,3,7｜8]
遍历结束，到达尽头，不执行循环语句体，将temp值赋值于array[0]
[1,2,3,7｜8]
参考代码：
 
        int[] arr = {7, 2, 3, 8, 1};
        System.out.println("未排序元素：\t " + Arrays.toString(arr));
        System.out.println("--------------开始排序-----------------");
        int i, j, temp;
        for (i = 1; i < arr.length; i++) {
            temp = arr[i];
            for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                arr[j + 1] = arr[j];
                System.out.println("\t\t\t " + Arrays.toString(arr));
            }
            arr[j + 1] = temp;
            System.out.println("第" + i + "轮排序结果：" + Arrays.toString(arr));
            System.out.println("--------------------------------------");
        }
 
运行结果：
 
未排序元素：	 [7, 2, 3, 8, 1]
--------------开始排序-----------------
			 [7, 7, 3, 8, 1]
第1轮排序结果：[2, 7, 3, 8, 1]
--------------------------------------
			 [2, 7, 7, 8, 1]
第2轮排序结果：[2, 3, 7, 8, 1]
--------------------------------------
第3轮排序结果：[2, 3, 7, 8, 1]
--------------------------------------
			 [2, 3, 7, 8, 8]
			 [2, 3, 7, 7, 8]
			 [2, 3, 3, 7, 8]
			 [2, 2, 3, 7, 8]
第4轮排序结果：[1, 2, 3, 7, 8]
--------------------------------------

插入法相对较复杂，基本原理是抽出一个数据，在前面数据中寻找相应的位置插入，然后继续下一个数据，直到排序完成
 
以9、6、15、4、2为例来进行插入法排序
 
元素[0]
元素[1]
元素[2]
元素[3]
元素[4]
初始值
9
6
15
4
2
第1次
9
 
第2次
 
6
9
第3次
6
9
15
第4次
4
6
9
15
结果
2
4
6
9
15
从表中可知，第一次排序将第一个元素放在首位，然后取出第二元素与其比较，如果小于第一个数则放在第一个数左边，反之则放在右边。以此类推，将元素逐个取出与前面的相比较，直到最后一个元素找到相应的位置放入
 
下面通过代码实现
 
#include<stdio.h>
int main()
{
	int arr[10];                      /*定义一个10个元素的数组*/ 
	int i,j,temp,pos;                 /*temp记录最小值，pos记录最小值位置*/
	for(i=0;i<=9;i++)                 /*输入各个数字*/
	{
		scanf("%d",&arr[i]);
	}
	for(i=1;i<10;i++)                  /*从数组的第二个元素开始循环*/
	{
		temp=arr[i];                  /*设置插入值*/ 
		pos=i-1;                      /*记录插入值前一个位置*/ 
		while(pos>=0&&temp<arr[pos])  /*与前面数逐个比较寻找插入值的位置*/ 
		{
			arr[pos+1]=arr[pos];      /*插入数值*/ 
			pos--;
		}
		arr[pos+1]=temp;
	}
	for(i=0;i<=9;i++)                  /*输出排序后的数组*/
	{
		printf("%d ",arr[i]);
	}
	return 0;
 } 
 
插入法排序共需要进行n-1次取出元素并寻找位置插入，因此当序列较为有序时，插入排序有较快的运算速度