各种排序算法及其java程序实现（3） -- 插入排序

插入排序(Insertion Sort)

 

1. 基本思想：

  每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

2. 排序过程：　

【示例】：

[初始关键字] [49] 38 65 97 76 13 27 49

    J=2(38) [38 49] 65 97 76 13 27 49

    J=3(65) [38 49 65] 97 76 13 27 49

    J=4(97) [38 49 65 97] 76 13 27 49

    J=5(76) [38 49 65 76 97] 13 27 49

    J=6(13) [13 38 49 65 76 97] 27 49

    J=7(27) [13 27 38 49 65 76 97] 49

    J=8(49) [13 27 38 49 49 65 76 97]

 

java代码实现：

 

    package test.suanfa;  
      
    public class InsertSort {  
          
        /** 
         * 测试 
         */  
        public static void main(String[] args) {  
            Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };  
            InsertSort insertSort = new InsertSort();  
            insertSort.insert(intgArr, 0, intgArr.length - 1);  
            for (Integer intObj : intgArr) {  
                System.out.print(intObj + " ");  
            }  
        }  
      
        /** 
         * 排序算法的实现，对数组中指定的元素进行排序 
         * @param array 待排序的数组 
         * @param from 从哪里开始排序 
         * @param end 排到哪里 
         */  
        public void insert(Integer[] array, int from, int end) {  
              
            /* 
             * 第一层循环：对待插入（排序）的元素进行循环 
             *  
             * 从待排序数组的第二个元素开始循环，到最后一个元素（包括）止 
             */  
              
            for (int i = from + 1; i <= end; i++) {  
      
                /* 
                 *  
                 * 第二层循环：对有序数组进行循环，且从有序数组最第一个元素开始向后循环 
                 *  
                 * 找到第一个大于待插入的元素 
                 *  
                 * 有序数组初始元素只有一个，且为原数组的第一个元素，一个元素数组总是有序的 
                 */  
      
                for (int j = 0; j < i; j++) {  
      
                    Integer insertedElem = array[i];// 待插入到有序数组的元素  
      
                    // 从有序数组中第一个元素开始查找第一个大于待插入的元素  
      
                    if ((array[j].compareTo(insertedElem)) > 0) {  
      
                        // 找到插入点后，从插入点开始向后所有元素后移一位  
      
                        move(array, j, i - 1);  
      
                        // 将待排序元素插入到有序数组中  
      
                        array[j] = insertedElem;  
      
                        break;  
                    }  
      
                }  
      
            }  
      
            // =======以下是java.util.Arrays的插入排序算法的实现  
      
            /* 
             *  
             * 该算法看起来比较简洁一j点，有点像冒泡算法。 
             *  
             * 将数组逻辑上分成前后两个集合，前面的集合是已经排序好序的元素，而后面集合为待排序的 
             *  
             * 集合，每次内层循从后面集合中拿出一个元素，通过冒泡的形式，从前面集合最后一个元素开 
             *  
             * 始往前比较，如果发现前面元素大于后面元素，则交换，否则循环退出 
             *  
             *  
             * 总感觉这种算术有点怪怪，既然是插入排序，应该是先找到插入点，而后再将待排序的元素插 
             *  
             * 入到的插入点上，那么其他元素就必然向后移，感觉算法与排序名称不匹，但返过来与上面实 
             *  
             * 现比，其实是一样的，只是上面先找插入点，待找到后一次性将大的元素向后移，而该算法却 
             *  
             * 是走一步看一步，一步一步将待排序元素往前移 
             */  
      
            /* 
             *  
             * for (int i = from; i <= end; i++) { 
             *  
             * for (int j = i; j > from && c.compare(array[j - 1], array[j]) > 0; 
             * j--) { 
             *  
             * swap(array, j, j - 1); 
             *  
             * } 
             *  
             * } 
             */  
      
        }  
      
        /** 
         * 数组元素后移 
         * @param array 待移动的数组 
         * @param startIndex 从哪个开始移 
         * @param endIndex 到哪个元素止 
         */  
        public void move(Integer[] array, int startIndex, int endIndex) {  
            for (int i = endIndex; i >= startIndex; i--) {  
                array[i + 1] = array[i];  
            }  
        }  
      
    }