插入排序算法的实现

谁践踏了优雅 2022-03-01 14:46 185阅读 0赞

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。  
算法适用于少量数据的排序，时间复杂度为O(n^2)  
遍历一个数组，每次遍历一个数的时候，和前边的数判断，如果比前边的数小就和前边的数交换，这样直到满足条件即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]下边我们看一下具体代码的实现

public class InsertSort {
        public static void sort(Comparable[] arr){
        	//遍历这个数组
            for (int i = 1;i<arr.length;i++){
            	//循环判断每个元素和前边的值
                for (int j = i;j > 0;j--){
                    if (arr[j].compareTo(arr[j-1])<0){
                        swap1(arr,j-1,j);
                    }
                }
            }
        }
    	public static void swap1(Object[] arr,int i, int j){
    	        Object temp;
    	        temp = arr[j];
    	        arr[j] = arr[i];
    	        arr[i] = temp;
    	    }
    
        public static void main(String[] args) {
            int n = 10000;
            Comparable[] arr = selectSort.generateRandomArray(n,0,n);
            long startTime = System.currentTimeMillis();
            InsertSort.sort(arr);
            long endTime = System.currentTimeMillis();
            System.out.println("插入排序时差："+(endTime-startTime));
        }
    }

我们观察一下这个代码，在swap中每次交换都要做三步替代，那么这种数据小的话还可以接受，如果数据量很大的话应该可想而知是有多浪费时间的了。那么我们在这一块尽量优化一下。  
大家想一下，我们可以把要遍历比较的数e先取出来，然后跟前边的比较，但是并不进行交换操作，而是直接把前边的值往后挪，当符合条件的时候就把e放到这个往后挪之后的元素地址这儿。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 1]这样的话我们就减少了两步，数据量大的情况话速度就可想而知了

//改进版
        public static void strong_sort(Comparable[] arr){
            for (int i = 1;i<arr.length;i++){
                Comparable e = arr[i];
                int j;
                for (j = i;j > 0 && arr[j-1].compareTo(e) > 0 ;j--){
                    arr[j] = arr[j-1];
                }
                arr[j] = e;
            }
        }

测试结果如下  
![在这里插入图片描述][20190322204353373.png]  
这个差距确实不小的

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]: /images/20220301/920bc85c131541f289f14c4ab8124924.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 1]: /images/20220301/16f0522eac624b198a8b23341d0a0693.png
[20190322204353373.png]: /images/20220301/1f544c56a12a452083bcc4a4e2436a50.png