本文主要是介绍排序算法之---插入排序（看完不懂来打我呀呀），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、插入排序
还是那句话：不是常用的我不说,实用才是王道。
算法基本思想：
- 一个未排序的数组（也可以是链表）可以分为两个部分，前半部分是已经排序的，后半部分是未排序的。
- 在进行未排序时，只需要在未排序的部分中选择一个元素，将其插入到前面有序的数组中即可（找到合适的位置插入）
- 直到未排序的为0，则排序完成。
二、直接上代码：（会的就不用看第三部分了）
Java老大哥：
package suanFa;
/*** 插入排序，时间复杂度O(n^2)*/import java.util.Arrays;public class insertSort {public static void insertSort1(int[] arr){int length = arr.length;int i, j, key;//数组第一个默认为有序for(i = 1; i < length; i++){ //key为要准备插入的元素key = arr[i];j = i - 1;while(j >= 0 && arr[j] > key){arr[j+1] = arr[j];j--;}//找到合适的位置插入keyarr[j+1] = key;}}public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = {5,3,1,0};System.out.println("未开始插入前:"+Arrays.toString(arr));insertSort1(arr);System.out.println("插入完成后:"+Arrays.toString(arr));}
}Python新竞老大哥：
"""排序算法之--插入排序"""
def insertSort(list):length = len(list)for i in range(1,length): #未排序的序列从第二个开始往后遍历for j in range(i, 0, -1): #已排序的从后往前遍历if list[j] < list[j - 1]: # 如果当前元素小于前一个元素, 则交换元素位置#列表直接这样交换两个值是可以的list[j - 1], list[j] = list[j], list[j - 1]else: #如果大于前一个元素，则保持位置不变break
if __name__ == "__main__":list = [6,3,1,0]print(list)insertSort(list)print(list)
三、分析如下：（提供给不是很理解的小朋友）
假设数组arr由下图所示
考虑到篇幅的原因，我这里直接带你跑一遍 java算法程序。我保证：如果你跟着走一遍，还不会，那就是我蠢了（哈哈哈，开玩笑啦啦啦，哪有这么说自己的）
- 首先用i, j ,key 三个变量分别来表示：无序部分的下标、有序部分的下标、无序部分准备要插入的元素
- 看图，可以知道，无序部分的下标是从：1 - 数组长度减一
- 有序部分的下标是：0 到 i - 1(这里需要稍微想想：无序部分的起始坐标减掉1就是有序部分的最后坐标）
上面的懂了之后：下面就好办了：走进程序的世界了解一下
- 取无序第一个暂存在key中，即（key = arr[i]）
- 往下j = 0 (这里保存的是有序下标的最后坐标）
- 进入while循环：j=0且5>3符合条件，进入循环内部
- 将arr[0]处的值（a[j] = 5），赋值给arr[1] (arr[ j+1 ] )
- j减减后值为-1，不符合while循环条件，退出循环体
- 程序继续往下走，j+1 = 0,所以将key的值赋给arr[0]
- 这样就把无序中的3成功插入到 有序中了
- 然后程序继续for循环，直到无序部分完成。
四、分享结束
最后有兴趣一起交流的，可以关注我的公众号：这里你能够学到很实用的技巧，不是常用的我不说，公众号回复提取码即可获取以下学习资料啦啦啦啦，喜欢就拿去吧！！
-
Java web从入门到精通电子书
-
Python机器学习电子书
-
Python400集（北京尚学堂）
-
JavaScript项目案例、经典面试题
-
Java300集（入门、精通）
-
Java后端培训机构录集（同事培训内部提供）
这篇关于排序算法之---插入排序（看完不懂来打我呀呀）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
