插入排序：C语言实现

缺乏、安全感 2022-04-06 12:30 207阅读 0赞

## 一、概述 ##

插入排序很好理解，与实际生活紧密相连，或可以说是来源于生活中的感悟。

插入排序是用的非常多的一种排序方法，因为在实际编程中，数据往往是排序好的

所以往排序好的数据中插入新数，此时用插入排序会特别快速。

假设十个人按排队，从矮到高，你会怎么排？

首先，第2人与第1人比，若2比1矮，那么他们互换位置，否则不动，此时前两位已经排好了

然后第3人站出来，看看前面哪个位置中，自己比左边的高，右边的矮，然后插进去，若是前面人中最高的，

就不动。此时前3人排好了，以此类推。

程序中要先用一个变量保存这个“站出来的”数。直到此数找到比TA矮的人，那时留出一个空位，可以插入。

/*
    	在一维乱序的数组中
    	使用插入排序，实现从小到大排列
    	精髓：从右往左比较，直到碰到小于等于它的数，插入，进入下一个循环
    */
    #include <stdio.h>
    int main(void)
    {
    	int i,j;
    	int temp;
    
    	int a[] = {98,908,45,21,0,0,-5,7987,-21,785,-354,66,78,21,89,4564};
    	int n = sizeof(a)/sizeof(a[0]);	// 数组元素的个数
    
    	for(i=1; i<n; i++)	// 初值i=1，从第二个开始比较，循环一次比较一轮
    	{
    		temp = a[i];
    		j = i-1;		// 与它前一个数做比较
    		
    		while((j >= 0) && (a[j] > temp))
    		{
    			a[j+1] = a[j];
    			j--;		/* 
    							j-1，再与前一个比较，直到碰到小于等于它的数
    							while循环退出，左边形成一个新的有序序列
    						*/
    		}
    		if(j != i-1)
    		{
    			a[j+1] = temp;
    		}
    		/*
    			j != i-1说明执行过上面while，并找到了位置，那么插入
    			如果j = i-1,则说明没有执行while，说明它与左边比是最高的，不用换位置
    		*/
    
    	}
    	
    	for(i=0; i<n; i++)
    	{
    		printf("%d\x20",a[i]);
    	}
    	printf("\n");
    
    	return 0;
    }

## 二、可输入数据的插入排序 ##

/*
    	有输入地插入一个数
    	让原来的数组从大到小排列
    */
    #include <stdio.h>
    int main(void)
    {
    	int a[10] = {1,3,5,7,9,11,13,15,17};
    	int i = 8;	// 存储数组最大下标
    	int data = 0;	//要插进来的数
    	
    	scanf("%d",&data);
    	while((i>=0) && (a[i]>data))    // 找到data应插入的位置，并把该位置空出来 
    	{
    		a[i+1] = a[i];
    		i--;
    	}
    	a[i+1] = data;	// data插入该位置
    	
    	for(i=0; i<10; i++)
    	{
    		printf("%d\x20",a[i]);
    	}
    	printf("\n");
    
    
    	return 0;
    }

## 三、与冒泡排序的比较 ##

冒泡排序是从左往右比，插入排序是从右往左比，但也是一轮轮比较

原序列中，从左边第二个开始，每一轮比较一个数，每个数以此与左边所有数比较

左边都是以排好的数列，该数与排好的数列逐个比较，最后插入，形成新有序数列。

## 四、本程序的缺陷 ##

此程序是手动指定了数组长度为10，为何？数组定长，若写成  int a\[\] = \{1,3,5,7,9,11,13,15,17\};

系统自动初始化数组长度为9，你就无法扩展数组a了，数组的最后一个元素将会向后覆盖一个int型未分配给它的内存空间。

综上，程序猿需要手动维护数组的长度，若可以动态扩展长度的话，

那么就可定义成  int a\[\] = \{1,3,5,7,9,11,13,15,17\};   这种形式。

可以通过 sizeof(a) / sizeof(a\[0\]) 获取数组中有意义的数据的长度，然后减一就是数组最大下标。

若需要插入就动态扩展一个int型空间即可。

动态数组和链表将会解决这个缺陷。

更多排序方法：

[冒泡排序][Link 1]

[选择排序][Link 2]

[插入排序][Link 3]

[快速排序][Link 4]

[Link 1]: https://blog.csdn.net/adidas74891496/article/details/84950279
[Link 2]: https://blog.csdn.net/adidas74891496/article/details/84950461
[Link 3]: https://blog.csdn.net/adidas74891496/article/details/84917221
[Link 4]: https://blog.csdn.net/adidas74891496/article/details/84953285