插入排序InsertSort

素颜马尾好姑娘i 2022-05-23 10:35 149阅读 0赞

插入排序,就像是打斗地主的时候把自己手里的牌按照大小排序,总数组长度就是一个人对多起牌的长度,一开始手里一张牌,这张牌就是最小的,放最左边,再起一张,拿这张跟第一张比较(依次跟前面的比较大小),小于第一张的话就排第一位,最先起的放第二位(交换位置),这样,手里的牌已经是按照大小排序过的了.依次类推,直到牌面起完,也就排好了所有的牌面.  
基于这个思想,说下代码排序原理:  
有一个tempArray数组,第一轮先拿第二位跟第一位比较,然后按大小排序.第二轮,拿第三位跟第一位以及第二位比较,按大小排序,第三轮,拿第四位跟第三位,第二位,以及第一位比较…依次类推.  
则转化为代码实现为:

for (int i = 1;i < tempArray.length;i++){
                //循环第i次的时候,数组下标为i的跟下标为i-1的比较大小,每次比较都是跟第i位之前的比较.
                //声明中间变量
                int tempNum = -1;
                for (int j = i;j>0;j--){
                    // 如果tempArray[j-1]>tempArray[j],则交换位置
                    if (tempArray[j-1]>tempArray[j]){
                        tempNum = tempArray[j];
                        tempArray[j] = tempArray[j-1];
                        tempArray[j-1]= tempNum;
                    }
                    flag++;                
                }
            }

然后简单的说下插入排序的时间复杂度:  
插入排序,如果数组长度为n的话,每次比较循环次数,依次为,当i=1时,内层循环为1次,tempArray\[0\]与tempArray\[1\]比较.当i=2时,内部循环两次.当i=n时,内部循环n次.  
则总循环次数为:  
0+1+2+3+…+(n-1)=n\*(n-1)/2,  
时间复杂度为O(N²),故,排序次数随着数组的长度J型递增.  
因此,小数量级排序可以使用,大数量级时,排序速度较慢,不建议使用.  
PS:本章代码已推送到GitHub,有需要的博友可以前去下载验证查看,GitHub地址为:  
[https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/InsertSort.java][https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_InsertSort.java]  
代码验证输出效果如下:  
![这里写图片描述][70]

[https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_InsertSort.java]: https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/InsertSort.java
[70]: /images/20220523/5b8d96332ce0436ca4dd38f2e21ea451.png