【算法】逻辑十分缜密，思路清晰的带大家一次性学会常见的排序算法系列ヾ(≧▽≦*)o。（三）插入排序

た入场券 2024-05-25 17:32 14阅读 0赞

## ✨前言✨： ##

**算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算法，不仅能提高coding能力，还能更加容易在笔面试中脱颖而出。本专栏将记录博主刷算法题的过程，不定期的会更新一些优质的算法题。如果对大家有帮助，别忘了三连支持哟！**

--------------------

**目录**

✨前言✨：

✨插入排序的思想✨

?如何进行插入?

?插入的具体方法?

✨插入排序具体代码的实现✨

✨时间复杂度的计算✨

--------------------

## ✨插入排序的思想✨ ##

> **?：插入排序的核心思想就是插入二字，理解要如何插入和其内在的逻辑对深刻理解插入排序至关重要。**

### **?如何进行插入?** ###

> ?**：我们假设要对n个数进行插入排序，那么我们的步骤是，先让下标0~0上有序（只有一个数显然成立），我们再把下标为1的数插入进这个有序序列中去让0~1上有序，而我们要实现0~2上有序，只需要让2位置的数插入到0~1上（这时0~1上的数相对顺序不变，其还是有序的，让2位置的数插入到应该在的位置），以此类推，最后一次时，下标为0~n-2上所有数都已经有序了，只需要将下标为n-1的元素插入到0~n-2这个有序序列中去。从这样的逻辑分析，每次我们让后面一个数插入时，前面所有数都已经有序，由这样的逻辑分析下去最后一定让所有数全部有序。**

### **?插入的具体方法?** ###

?**上文讲了插入排序的全部过程，但并没有细致的讲具体是如何进行插入的，其实插入的过程只有一个步骤：**

**比如我们现在想要让0~n上排成升序，由上述可知，此时0~n-1上一定已经有序，我们插入的时候不能改变原本0~n-1上所有元素的相对顺序，只需要让n位置的元素向左看与它相邻的元素，如果n位置的元素比左边的小，就让两个元素进行交换，然后这个元素继续与左边的元素比较，如果小就交换，直到它比左边元素大或者左边没有元素时才会停下来。**

**?:插入的步骤可以简化为4个字 （看 比 换 停）。**

--------------------

**讲到这里相信大家对插入排序的大致思路显然已经十分清晰了，如果大家胸有成竹，请大家先自己写一篇，再过来看看我写的代码，这样效果最好。**

--------------------

## ✨插入排序具体代码的实现✨ ##

#include<stdio.h>
    void Swap(int arr[], int i, int j)
    {
    	//两种方法
    	int tmp = arr[i];
    	arr[i] = arr[j];
    	arr[j] = tmp;
    	
    	//arr[i] = arr[i] ^ arr[j];
    	//arr[j] = arr[i] ^ arr[j];
    	//arr[i] = arr[i] ^ arr[j];
    }
    void insertionSort(int arr[], int sz)
    {
    	for (int i = 1; i < sz; i++)//控制插入排序的范围即0-1....0-n-1
    	{
    		for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--)
    		{
    //满足两个条件才交换
    //1:小于左边的数
    //2:没有越界
    
    			Swap(arr, j, j + 1);
    		}
    	}
    }

--------------------

## ✨时间复杂度的计算✨ ##

## ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16][] ##

--------------------

**以上代码，还可做优化在此仅作参考，若有更好的算法，还望能够私信告知，多谢各位。**

**由于本人水平十分有限，若有错误请即使告知！如果有帮助别忘了，万分感谢。**

**点赞? 收藏✨ 关注✌**

##  ##

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/4139180a2b7b4e51a1916e7bd08853a8.png