插入排序算法---插入排序与希尔排序

              INSERTION-SORT(A)
1for j ← 2 to length[A]
2do key ← A[j]
3          ? Insert A[j] into the sorted sequence A[1 ‥ j - 1].
4          i ← j - 15while i > 0 and A[i] > key
6do A[i + 1] ← A[i]
7                 i ← i - 18          A[i + 1] ← key
        

            
                     static
                int count = 0;
     /***
     * 把n个待排序的元素看成一个有序表和一个无序表， 开始有序表只包含一个元素，无序表中包含n-1个元素，
     * 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较， 将它插入到有序表中的适当位置，使之成为新的有序表。
     */publicstaticvoid runInsertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int insertVal = a[i];
            // insertValue准备和前一个数比较int index = i - 1;

            while (index >= 0 && insertVal < a[index]) {
                // 将把a[index]向后移动
                                a[index + 1] = a[index];
                // 让index向前移动一位
                               index--;
            }

            // 将insertValue插入到适当位置
                        a[index + 1] = insertVal;
            System.out.println("indexPos>>>"+(index+1));
            System.out.print("第" + (i) + "次排序结果：");
            for (int k = 0; k < a.length; k++) {
                System.out.print(a[k] + "\t");
            }
            System.out.println("");
            count++;
        }
        System.out.print("最终排序结果：");
        for (int l = 0; l < a.length; l++) {
            System.out.print(a[l] + "\t");
        }
    }

publicstaticvoid main(String[] args) {
        int[] array = newint[6];  
        for (int k = 0; k < array.length; k++) {  
            array[k] = (int) (Math.random() * 100);  
        }
        System.out.print("排序之前结果为:");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println("");
        runInsertSort(array);
        System.out.println("交换次数："+count);
    }
        

            排序之前结果为:661290754385    
indexPos>>>0
第1次排序结果：126690754385    
indexPos>>>2
第2次排序结果：126690754385    
indexPos>>>2
第3次排序结果：126675904385    
indexPos>>>1
第4次排序结果：124366759085    
indexPos>>>4
第5次排序结果：124366758590    
最终排序结果：124366758590    排序次数：5
        

二分插入排序

插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n²)。

            
                public
                class
                 SortSolution {

    
                static
                int count = 0;


    /***
     * 向有序序列中插入元素，那么插入位置可以不断地平分有序序列， 并把待插入的元素的关键字与平分有序序列的关键字比较，以确定下一步要平分的子序列，
     * 直到找到合适的插入位置位置。
     */publicstaticvoid runBinaryInsertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int insertVal = a[i];// 待插入的值int low = 0;
            int high = i - 1;

            while (low <= high) {
                // 找出low,high的中间索引int mid = (low + high) / 2;
                // 如果要插入的值大于mid的值if (insertVal > a[mid]) {
                    low = mid + 1;
                }// 限制在索引大于mid的那一半中搜索else {
                    high = mid - 1;
                }// 限制在索引小于mid的那一半中搜索            }

            // 将low到i处的所有元素向后整体移动一位for (int j = i; j > low; j--) {
                a[j] = a[j - 1];
            }

            // 将insertValue插入到适当位置
            a[low] = insertVal;
            System.out.println("indexPos>>>"+(low));
            //System.out.print("\n");
            System.out.print("第" + (i) + "次排序结果：");
            for (int k = 0; k < a.length; k++) {
                System.out.print(a[k] + "\t");
            }
            System.out.println("");
            count++;
        }
    }

    
    publicstaticvoid main(String[] args) {
        int[] array = newint[1500];  
        for (int k = 0; k < array.length; k++) {  
            array[k] = (int) (Math.random() * 100);  
        }
        SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date begintime = new Date();
        System.out.println("开始时间: " + df.format(begintime));
        System.gc();
        System.out.print("排序之前结果为:");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println("");
        runBinaryInsertSort(array);
        System.out.println("交换次数："+count);
        Date endtime = new Date();
        System.out.println("结束时间：" + df.format(endtime));
        Date time = new Date(endtime.getTime() - begintime.getTime());
        System.out.println("总用时间：" + time.getMinutes() + "分"
                + time.getSeconds() + "秒");
    }
        
}