579-插入排序算法的思想和性能分析

比眉伴天荒 2022-09-11 15:24 182阅读 0赞

## 插入排序算法的思想 ##

![在这里插入图片描述][7a6a53565f5c4f5194a71360ba241496.png]  
**对于插入排序算法来说，不仅仅没有交换，而且比较的次数也少！**  
![在这里插入图片描述][8b7b2cc55826483c9a315791c3304c3f.png]  
**插入排序：每次会把前面的一组序列当做已经排序好的，然后把后面的元素，按照有序的方式插入到前面的序列就可以了。**  
![在这里插入图片描述][13bacaa22180406883a7eba4168708fa.png]  
**具体该怎么做呢？  
下面这是我们原始的一组待排序的序列。**  
![在这里插入图片描述][a35bde6d40b545559cf3b4f1e374fac5.png]  
**我们认为第一个元素25本身就是有序的序列，因为就一个元素25嘛。**  
**我们从第二个元素开始处理：**

**第1趟**：认为25是有序的序列，然后把40按照顺序插入到其前面已经有序的序列，因为前面已经是有序的序列，所以40就往前找，找第一个小于或者等于40的数字，插入到其后面。  
![在这里插入图片描述][d87535fc1a7547e5bc8dfdf86b9d6a46.png]  
现在前面有序的序列是：25,40

**然后开始第2趟**：处理25这个元素，25前面是有序的序列了，然后25往前找第一个小于或者等于25的元素（维护其稳定性），插入到其后面。  
25先和40比，40比25大，把40往后挪，  
![在这里插入图片描述][d79948b330604ea9bc91b1d10d3f77f3.png]  
![在这里插入图片描述][7b74bcb7950344a7afe325154fac5b3c.png]  
然后25和25比，25==25，就插入到25的后面，保持其稳定性。  
![在这里插入图片描述][ef274b00922a47cd82321043eeee9e48.png]  
第二趟处理完，前面的有序序列是：25,25,40

**现在开始第3趟：**  
处理元素9，9前面已经是有序的序列了，9往前遍历，寻找第一个小于等于9的元素，插入到其后面![在这里插入图片描述][3b3e412e07d84a898563f66e6338de69.png]  
![在这里插入图片描述][b266804564194078862919d94c321652.png]  
![在这里插入图片描述][80c1aa08611a42e3ab2bf4397199ec5d.png]  
![在这里插入图片描述][9160e4d0dc6b412dab6650ad73450f9d.png]  
![在这里插入图片描述][596fa15858bd457985dcce89f2e4237d.png]  
现在前面有序的序列是：9，25,25,40

**现在开始第4趟：** 处理元素32，往前找第一个小于等于32的元素  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][78c7b184d3e6478f85bd733a51f37f72.png]  
![在这里插入图片描述][592f9590377a41b4b8110d19b534ab46.png]  
**这一趟只比较了1个元素，就按序插到前面有序的序列中了**  
![在这里插入图片描述][1093e389c73040b3924cdc713af2aa69.png]  
**在数据量大的情况下，元素越有序，选择排序算法的比较次数越少，效率越高。**

**第5趟也是如此操作，以此类推下去，直到最后一趟处理最后一个元素为止。**

![在这里插入图片描述][aa334a72f7cc4853b7fa030e35a80415.png]

![在这里插入图片描述][d29c838e1fe746149467f101f72c1f20.png]  
![在这里插入图片描述][82e8dc694eda4e9c843322e7944e7461.png]  
![在这里插入图片描述][44994aca27834ae08c77edb50a3b2b72.png]  
**最后一趟：处理31**  
![在这里插入图片描述][4e32d22141694124994ff3143de416c5.png]  
**因为每一趟的待处理元素的前面序列是有序的，所以基本上，比较的次数是比较少的，基本上都一两次，两三次就有序插入OK了，除非在后面处理的数字是非常小的数字，需要比较多次。**

**所以插入排序的每一趟处理的效率是非常高的，而且处理的步骤是非常少的，很快的。**

**有时候甚至比较1次就可以：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 插入排序算法的代码实现 ##

//插入排序算法  时间复杂度: 最坏、平均 O(n^2)  最好：O(n)  空间：O(1)  稳定性：稳定的
    void InsertSort(int arr[], int size)
    {
        
    	for (int i = 1; i < size; i++)//O(n) <size，因为最后一个元素也是要处理的 
    	{
        
    		int val = arr[i];
    		//此趟未排序序列的首位置的值，因为每一趟处理，无序序列少1个元素 ，前面的有序序列多1个元素 
    		int j = i - 1;//前面有序序列的末尾元素的下标 
    		for (; j >= 0; j--)//O(n)
    		{
        
    			if (arr[j] <= val)//找第一个小于等于val的值 
    			{
        
    				break;
    			}
    			arr[j + 1] = arr[j];//把当前元素往后挪动 
    		}
    		arr[j + 1] = val;//放到第一个小于等于val的元素的后面 
    	}
    }

## 插入排序算法的性能分析 ##

**时间复杂度:**  
**最坏、平均时间复杂度** O(n^2)  
因为是有2个for循环，是嵌套的  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

**最好时间复杂度**：O(n)  
待排序的序列已经是有序的序列了。  
相当于内层循环不做任何数据移动交换，外层循环遍历1遍就完了。

**空间复杂度**：O(1)  
只定义了固定的栈上的变量，不会随着数据量的变大，变量增加。  
在原数组内操作。没有开辟额外的空间。

**是稳定的排序算法**  
因为它找的是 前面有序序列中，小于等于它的数字，然后插到其后面  
后面的元素是不会跑到前面和它相等的元素的前面的，只会跟在其后面。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

[7a6a53565f5c4f5194a71360ba241496.png]: /images/20220828/b0c172b4799f47cab7819c26bfa2a2b0.png
[8b7b2cc55826483c9a315791c3304c3f.png]: /images/20220828/2f0af39837164fac9239316142a7082d.png
[13bacaa22180406883a7eba4168708fa.png]: /images/20220828/3e76f7fb407d4981844d9c034799e3f9.png
[a35bde6d40b545559cf3b4f1e374fac5.png]: /images/20220828/0d082398fae2407c81e39dabf2f4ef49.png
[d87535fc1a7547e5bc8dfdf86b9d6a46.png]: /images/20220828/03a6578a13ee428595937760f83ed0d2.png
[d79948b330604ea9bc91b1d10d3f77f3.png]: /images/20220828/0c6da61246a94939b46e2733f94de83d.png
[7b74bcb7950344a7afe325154fac5b3c.png]: /images/20220828/d69ff5db1e7e4921ade017172c817019.png
[ef274b00922a47cd82321043eeee9e48.png]: /images/20220828/0eb8df56036143a697cfa1cb3f4b649a.png
[3b3e412e07d84a898563f66e6338de69.png]: /images/20220828/833fc695b06e48c4b7fe016f0827515c.png
[b266804564194078862919d94c321652.png]: /images/20220828/8baeae2fe791457ab8160ac30267757c.png
[80c1aa08611a42e3ab2bf4397199ec5d.png]: /images/20220828/b31b8442ee4843c6b9353f304a77aab7.png
[9160e4d0dc6b412dab6650ad73450f9d.png]: /images/20220828/9aa6fe8907f04897bd4687bcbd441b26.png
[596fa15858bd457985dcce89f2e4237d.png]: /images/20220828/74f6e2d4b2384104b8b46698c220efc3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/08bf816ae5dc43398627fec3367d000d.png
[78c7b184d3e6478f85bd733a51f37f72.png]: /images/20220828/8d7dfcbcd52f4657a2bc3d7208af3914.png
[592f9590377a41b4b8110d19b534ab46.png]: /images/20220828/df07fff01d6048aebb9dab24b8f38cf2.png
[1093e389c73040b3924cdc713af2aa69.png]: /images/20220828/b0812fbda1b94a0882f715fa7c59fe4a.png
[aa334a72f7cc4853b7fa030e35a80415.png]: /images/20220828/4ea1061690a04599ad66e66dcf223e0e.png
[d29c838e1fe746149467f101f72c1f20.png]: /images/20220828/43d2918bde5d458287151631a9362596.png
[82e8dc694eda4e9c843322e7944e7461.png]: /images/20220828/6c0cced109614c609514771714fcd364.png
[44994aca27834ae08c77edb50a3b2b72.png]: /images/20220828/b1e4b716deec4a28afab8e318dde3343.png
[4e32d22141694124994ff3143de416c5.png]: /images/20220828/032ad834b42d45b2b5f4d2bffbef543e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/bf21591cdb834e43a26f0ba1cb97db13.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/66c13b5d563246eb8de49256dac35b6a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/53a0c24645654b28838679288270cf6f.png