【算法】插入排序(从小到大) 排序范围(0~n-1)n为数组元素个数

布满荆棘的人生 2022-06-13 06:19 178阅读 0赞

我们再来谈谈另外一个基本排序算法，插入排序。

插入排序的思想也是十分简单。我们在排序范围(begin,end)中，选择数组下标为end的元素作为基准值，从它的前一个元素开始，向前遍历。在遍历过程中，把遍历到的值与基准值进行对比，如果比基准值**大**，就把这个值后移，遍历下标i前移。直到找到一个元素，比基准值**小**，或者遍历到数组头后结束，得到一个下标值，即插入位置。最后将基准值插入到这个下标值中。

下面我们就进行算法分析吧，数据还是1 3 2 8 0 6 总共6个数

![20170629165130374][]

1、第一趟，排序范围(0,1)，遍历下标i指向end所指位置，即下标1，基准值为3

![20170629165344900][]

我们发现，a\[i-1\]=a\[0\]=1 < 3，不需要向前遍历，下标1即为插入位置

2、第二趟，排序范围(0,2)，遍历下标i指向end所指位置，即下标2，基准值为2

![20170629165617405][]

我们发现，a\[i-1\] = a\[1\] = 3> 2，所以要将下标i前移，元素3后移，i指向1下标

![20170629165825547][]

a\[i-1\] = a\[0\] = 1 < 2，不需要向前遍历，下标1即为插入位置

![20170629170213298][]

3、第三趟，排序范围为(0,3)，遍历下标i指向end所指位置，即下标3，基准值为8

![20170629172605715][]

我们发现，a\[i-1\] = a\[2\] = 3 < 8，不需要向前遍历，下标3即为插入位置

![20170629172750653][]

4、第四趟，排序范围为(0,4)，遍历下标i指向end所指位置，即下标4，基准值为0

![20170629172849159][]

我们发现，a\[i-1\] = a\[3\] = 8> 0，所以要将下标i前移，元素8后移

![20170629173009487][]

a\[i-1\] = a\[2\] = 3> 0 ，所以要将下标i前移，元素3后移

![20170629173142029][]

a\[i-1\] = a\[1\] = 2> 0，所以要将下标i前移，元素2后移

![20170629173233386][]

a\[i-1\] = a\[0\] = 1> 0，所以我们要将下标i前移，元素1后移

![20170629173339563][]

此时，遍历指针i已经指向了数组头，即下标0，说明我是在遍历的所有元素中最小的，这时，下标0就是我们需要插入的位置

![20170629173516280][]

5、第五趟，排序范围为(0,5)，遍历下标i指向end所指位置，即下标5，基准值为6

![20170629173653616][]

我们发现，a\[i-1\] = a\[4\] = 8> 6，所以要将下标i前移，元素8后移

![20170629173910424][]

a\[i-1\] = a\[3\] = 3 < 6，不需要向前遍历，下标4即为插入位置

![20170629174032201][]

经过以上5趟，排序结束，最终序列为

![20170629174109419][]

从以上分析我们可以知道，要完成插入排序，要有两个方法，一个用于找插入位置并且插入数据(核心)，另外一个用于反复调用，扩大排序范围。与[选择排序][Link 1]不同，插入排序是保持begin指针不动，由前往后扩大。而选择排序是保持end指针不动，由前往后缩小。以上图中的下标i，就是基准值要插入的位置！

由此，我们可以得到插入排序算法核心(insert)与入口方法(sort)

#include <stdio.h>
    #define Elemtype int
    //插入排序核心
    void insertion(Elemtype a[] , int begin , int end)
    {
    	//将待排序数组的最后一个元素作为基准值
    	Elemtype base = a[end];
    	//遍历指针i指向待排序数组的最后一个元素
    	int i = end;
    	//循环判断，退出条件为：1、i已经指向数组头 2、发现有比基准值小的元素
    	while(i > 0 && a[i-1] > base)
    	{
    		//如果进入循环体，说明当前扫描值比基准值大，则应把基准值后移
    		a[i] = a[i-1];
    		//下标前移
    		i--;
    	}
    	//找到插入位置后，将基准值插入
    	a[i] = base;
    }
    
    void sort(Elemtype a[] , int begin , int end)
    {
    	int i;
    	//从第一个元素开始，到最后一个元素为止，保持begin指针不动，逐渐扩大排序范围
    	for(i = begin ; i <= end ; i++)
    	{
    		insertion(a,begin,i);
    	}
    }

完整可执行程序如下

运行效果如下：

![20170629194136995][]

插入排序算法的时间复杂度也是O(n^2)

[20170629165130374]: /images/20220613/c3ca50030520407c859abe9a019fa441.png
[20170629165344900]: /images/20220613/a5205ba43d10427d8f60b4fdd01556ac.png
[20170629165617405]: /images/20220613/4b3e072b835c498abfcb4e523d0eba95.png
[20170629165825547]: /images/20220613/ff35ada58aff40ad8f4e322c6962e01c.png
[20170629170213298]: /images/20220613/4f2e60f8f89747bf8168d621b5a67ab1.png
[20170629172605715]: /images/20220613/447f3fe30a614677ac85692e8a4f70e9.png
[20170629172750653]: /images/20220613/fd976d974ac54243a0bb9dd0f4e8d741.png
[20170629172849159]: /images/20220613/db962609e88d4c53873cd92e02e2e6d4.png
[20170629173009487]: /images/20220613/9238f2f8972e4246bfe27ce0ed603773.png
[20170629173142029]: /images/20220613/6e2aec78976845e3a91b485df3c8e6ee.png
[20170629173233386]: /images/20220613/3835f024629740cc8f179699ff1b738b.png
[20170629173339563]: /images/20220613/15fe52035930483b8488bb98c6c39f0b.png
[20170629173516280]: /images/20220613/aaa428f1431947e790c00f5e99e6d155.png
[20170629173653616]: /images/20220613/3e94595cf32747a79f36949d10269419.png
[20170629173910424]: /images/20220613/099345f9d2de4267a98ddf8a4b5d64c0.png
[20170629174032201]: /images/20220613/8c077ff481b64cf78fe662dad835fb01.png
[20170629174109419]: /images/20220613/7ba33fb7f1cf45868e05b6f48c6fa136.png
[Link 1]: http://blog.csdn.net/mgsky1/article/details/73866163
[20170629194136995]: /images/20220613/af196a4f607244aba40268348950d8dd.png