Go语言视频零基础入门到精通

javalearner

一、直接插入排序
   我们把数组分为已排序和未排序两部分，把未排序的元素一次一个插入到已排序部分的合适位置上。
已排序部分逐渐增大，直到整个数组变成有序的。
下面通过一个例子来说明这个排序流程：待排序列： 49， 38 ， 65 ， 97， 76 ， 13， 27 ，49 插入49： 49  插入38： 38， 49  插入65： 38， 49， 65  插入97： 38， 49， 65， 97  插入76： 38， 49， 65， 76， 97  插入13： 13， 38， 49， 65， 76， 97  插入27： 13， 27， 38， 49， 65， 76， 97  插入49： 13， 27， 38， 49， 49， 65， 76， 97
  二、希尔排序
    基本思想：希尔排序把n个元素按一定的间隔分成几组，然后按组为单位进行插入排序。 。     将待排记录序列以一定的增量间隔h 分割成多个子序列，对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h ，对于每一个步长h 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体插入排序。

   因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长h下每个子序列的规模都不大，用直接插入排序效率都较高。 尽管在随后的步长h递减分组中子序列越来越大，但由于整个序列的有序性也越来越明显，则排序效率依然较高。这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。

希尔算法的本质是缩小增量排序，是对直接插入排序算法的改进。
   
程序的增量序列常采用的表达式：
(1)h=3*h+1。(h=1,4,13,40,121,364...)
(2)h=2^k-1。(h=1,3,7,15,31,63...

例:待排序列:5,9,1,4,8,2,6,3,7

1. import java.util.Arrays;   
   
2. import java.util.Random;   
   
3. public class SortTest{  
   
4. /**  
   
5.      * 交换数组中的两个元素的位置  
   
6.      * @param array 待交换的数组  
   
7.      * @param i 第一个元素  
   
8.      * @param j 第二个元素  
   
9.      */  
   
10.     private void swap(int[] array, int i, int j) {   
    
11.         if (i != j) {//只有不是同一位置时才需交换   
    
12.             int  tmp = array[i];   
    
13.             array[i] = array[j];   
    
14.             array[j] = tmp;   
    
15.         }   
    
16.     }   
    
17.   
    
18.     /**  
    
19.      * 数组元素后移  
    
20.      * @param array 待移动的数组  
    
21.      * @param startIndex 从哪个开始移  
    
22.      * @param endIndex 到哪个元素止  
    
23.      */  
    
24.     private  void move(int[] array, int startIndex, int endIndex) {   
    
25.         for (int i = endIndex; i >= startIndex; i--) {   
    
26.             array[i + 1] = array[i];   
    
27.         }   
    
28.     }   
    
29.   
    
30.     /**  
    
31.      * 以指定的步长将数组元素后移，步长指定每个元素间的间隔  
    
32.      * @param array 待排序数组  
    
33.      * @param startIndex 从哪里开始移  
    
34.      * @param endIndex 到哪个元素止  
    
35.      * @param step 步长  
    
36.      */  
    
37.     private void move(int[] array, int startIndex, int endIndex, int step) {   
    
38.         for (int i = endIndex; i >= startIndex; i -= step) {   
    
39.             array[i + step] = array[i];   
    
40.         }   
    
41.     }   
    
42.    //生成随机数组   
    
43.     @SuppressWarnings("unchecked")   
    
44.     public   int[] randomArray() {   
    
45.         Random r = new Random(System.currentTimeMillis());   
    
46.         int[] a = new int[r.nextInt(30)];   
    
47.         for (int i = 0; i < a.length; i++) {   
    
48.             a[i] = r.nextInt(100);   
    
49.         }   
    
50.         return  a;   
    
51.     }   
    
52.    
    
53.     /**  
    
54.      *         插入排序算法的实现，对数组中指定的元素进行排序  
    
55.      * @param array 待排序的数组  
    
56.      * @param from 从哪里开始排序  
    
57.      * @param end 排到哪里  
    
58.      * @param c 比较器  
    
59.      */  
    
60.     public void insertSort(int[] array) {  //升序排列
    
61.   
    
62.         /*  
    
63.          * 第一层循环：对待插入（排序）的元素进行循环  
    
64.          * 从待排序数组断的第二个元素开始循环，到最后一个元素（包括）止  
    
65.          */  
    
66.         for (int i =1; i < array.length; i++) {   
    
67.             /*  
    
68.              * 第二层循环：对有序数组进行循环，且从有序数组最第一个元素开始向后循环  
    
69.              * 找到第一个大于待插入的元素  
    
70.              * 有序数组初始元素只有一个，且为源数组的第一个元素，一个元素数组总是有序的  
    
71.              */  
    
72.             for (int j = 0; j < i; j++) {   
    
73.                 int insertedElem = array[i];//待插入到有序数组的元素   
    
74.                 //从有序数组中最一个元素开始查找第一个大于待插入的元素   
    
75.                 if (array[j]>insertedElem) {   
    
76.                     //找到插入点后，从插入点开始向后所有元素后移一位   
    
77.                     move(array, j, i - 1);   
    
78.                     //将待排序元素插入到有序数组中   
    
79.                     array[j] = insertedElem;   
    
80.                     break;   
    
81.                 }   
    
82.             }   
    
83.         }   
    
84.      }
    
85.    /**  
    
86.      * 希尔排序算法的实现，对数组中指定的元素进行排序  
    
87.      * @param array 待排序的数组  
    
88.      */  
    
89.     public void shelltSort(int[] array) {   //升序排列
    
90.         //初始步长，实质为每轮的分组数   
    
91.         int step = initStep(array.length);   
    
92.   
    
93.         //第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值   
    
94.         for (; step >= 1; step = (step + 1) / 2 - 1) {   
    
95.             //对每轮里的每个分组进行循环   
    
96.             for (int groupIndex = 0; groupIndex < step; groupIndex++) {   
    
97.   
    
98.                 //对每组进行直接插入排序   
    
99.                 insertSort(array, groupIndex, step);   
    
100.             }   
     
101.         }   
     
102.     }   
     
103.   /**  
     
104.      * 直接插入排序实现  
     
105.      * @param array 待排序数组  
     
106.      * @param groupIndex 对每轮的哪一组进行排序  
     
107.      * @param step 步长  
     
108.      * @param end 整个数组要排哪个元素止  
     
109.      * @param c 比较器  
     
110.      */  
     
111.     private void insertSort(int[] array, int groupIndex, int step) {   
     
112.         int startIndex = groupIndex;//从哪里开始排序   
     
113.         int endIndex = startIndex;//排到哪里   
     
114.         /*  
     
115.          * 排到哪里需要计算得到，从开始排序元素开始，以step步长，可求得下元素是否在数组范围内，  
     
116.          * 如果在数组范围内，则继续循环，直到索引超现数组范围  
     
117.          */  
     
118.        while ((endIndex + step) <= array.length-1) {   
     
119.             endIndex += step;   
     
120.         }   
     
121.   
     
122.         // i为每小组里的第二个元素开始   
     
123.         for (int i = groupIndex + step; i <= endIndex; i += step) {   
     
124.             for (int j = groupIndex; j < i; j += step) {   
     
125.                 int insertedElem = array[i];   
     
126.                 //从有序数组中最一个元素开始查找第一个大于待插入的元素   
     
127.                 if (array[j]>insertedElem) {   
     
128.                     //找到插入点后，从插入点开始向后所有元素后移step位   
     
129.                     move(array, j, i - step, step);   
     
130.                     array[j] = insertedElem;   
     
131.                     break;   
     
132.                 }   
     
133.             }   
     
134.         }   
     
135.     }   
     
136.     private static int initStep(int len) {   //从最小步长1推导出最长初始步长值
     
137.         /*  
     
138.          * 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推:  
     
139.          * 1,3,7,15,...,2^(k-1)-1,2^k-1  
     
140.          * 如果数组长度小于等于4时，步长为1，即长度小于等于4的数组不且分组，此时直接退化为直接插  
     
141.          * 入排序  
     
142.          */  
     
143.         int step = 1;   
     
144.   
     
145.         //试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长   
     
146.         while ((step + 1) * 2 - 1 < len - 1) {   
     
147.             step = (step + 1) * 2 - 1;   
     
148.         }   
     
149.   
     
150.         System.out.println("初始步长 : " + step);   
     
151.         return step;   
     
152.     }   
     
153.       /**  
     
154.        * 测试  
     
155.      * @param args  
     
156.      */  
     
157.     public static void main(String[] args) {   
     
158.         int[] intArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 };  
     
159.         System.out.println("源 : " + Arrays.toString(intArr));   
     
160.         SortTest test=new SortTest();   
     
161.         //test.insertSort(intArr);
     
162.        test.shelltSort(intArr);
     
163.        System.out.println("升 : " + Arrays.toString(intArr));   
     
164.       
     
165.      
     
166.      }
     
167.     }   
     

复制代码

运行结果:
D:java>java SortTest
源 : [5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7]
初始步长 : 7
升 : [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]


   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/7/000712968.zip