直接插入排序 java实现

偏执的太偏执、 2022-06-15 05:49 167阅读 0赞

直接插入排序的算法思路是：  
基于给定的一个数组，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。

package demo;
    
    public class InsertSort {
            public static void main(String[] args) {
    // int[] m=processArray();
                //为了方便测试，还是使用固定数组
                int[] m={
       11,9,77,66,23,83,31,2,71,10};
                long startTimeMs = System.currentTimeMillis();
                insertSort(m);
                long endTimeMs = System.currentTimeMillis();
                System.out.println("排序时间为"+(endTimeMs-startTimeMs)+"ms");
            }
    
            public static void insertSort(int[] a) {
                int tmp;
                System.out.println("排序之前： "+toString(a));
                for (int i = 1; i < a.length; i++) {
       //循环1
                        for (int j = i; j > 0; j--) { //循环2
                            if (a[j] < a[j - 1]) {
                                tmp = a[j - 1];
                                a[j - 1] = a[j];
                                a[j] = tmp;
                            }
                        }
                   System.out.println("第"+i+"趟排序结果："+toString(a));
                }
            }
    // public static void insertSort(int[] arr){ 
    // System.out.println("排序之前： "+toString(arr));
    // for(int i = 1;i < arr.length; i ++){ 
    // if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了，反之则进入if语句
    // int temp = arr[i];
    // int j;
    // for(j = i-1; j >= 0 && arr[j] > temp; j --){ 
    // arr[j+1] = arr[j];//把比temp大的元素全部往后移动一个位置 
    // }
    // arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
    // } 
    // System.out.println("第"+i+"趟排序结果："+toString(arr));
    // }
    // 
    // }
    
            //将数组转为字符串
            public static String toString(int[] a){
                StringBuffer sb=new StringBuffer();
                   for(int each:a){
                       sb.append(each+" ");
                   }
                   return  sb.toString();
            }
            //产生一个随机数组，存放10个不重复的100以内的数字
            private static int[] processArray() {
                int[] m=new int[10];
                for(int j=0;j<10;j++){
                    int i=(int) Math.ceil(Math.random()*100);
                    m[j]=i;
                    for(int k=0;k<j;k++){
                           if(m[j] == m[k]){
                              j--;
                              break;
                           }
                        }
                }
                return m;
            }
    }

![这里写图片描述][SouthEast]

注释的insertSort()是另一种交换方案，但是每次都会进入循环2，不是很好。  
时间复杂度分析：  
最好情况下：  
若数组为正序，只进行了循环1，比较了n-1次，没有移动，时间复杂度为O（n）；  
最坏情况下：  
若数组为反序：  
比较次数为1+2+3+….+(n-1）=O(n^2);  
移动次数为（1+2）+（2+2）+…+（n-1+2）=(n-1)\*(n-4)/2=O(n^2) i取值范围1~n-1,时间复杂度为O(n^2);  
空间复杂度分析：  
在直接插入排序中只使用了i,j,temp这3个辅助元素，与问题规模无关，所以空间复杂度为O(1)。  
稳定性分析：  
在整个排序结束后，相同元素的相对位置没有发生变化，所以直接插入排序是一种稳定排序。

[SouthEast]: /images/20220615/de462298e91c48f78c4b253da4fd006f.png