昨天在论坛看见有人在问希尔排序，我想着前两天用过快速排序和冒泡  选择等做过测试 顺便把这个希尔排序也看一下算了希尔排序时对插入排序的优化 如果现在要升序排列
插入排序就是  将一个无序的数组  从第二个位置开始和前面的位置比较  如果比前面的数小  就将前面的数后移  一直这样下去 知道到了0下标 或者当前数比前面的数大   就将当前下标的位置填入这个数
        下标 0 1 2 3 4 5 6
做个例子 3 4 1 2 5 8 6
第一次 4和3 比较     大于  就不变化  现在3 4  已经是一个排好序的数组了
第二次 1和4  发现1<4    4后移  变成3 _ 4  中间是空出来的位置 然后以1和3比较 1<3  数组变成 _ 3 4  到达0下标 填入1
变成 1 3 4  
后面依次下去   目的就是保证每次都去插入一个数  这个被插入的数组里面都要是排好序的

而希尔排序  就是对插入排序的优化  他是将数组分组   ，用增量(d   一般都是arr.length/2)来分组  这里d=7/2=3的话  上面那个数组
第一次 就是   下标  0 3 6               1 4  2 5
·  3 2 6     为一组4 5   为一组1 8
    这样对两组分别 插入排序
  第一组就是 2 3 6
  第二组就是  4 5
  第三组就是  1 8
  这样第一次排序的结果 2 4 1 3 5 8 6         
这时候d/=2   d=1      如果d!=1  继续上态依次下去 分组 插入排序
当d=1时就是普通的插入排序  只不过这的时候  因为前面分插入排序过  很多都是排好序的(排序好了 只要比一次)  所以这样最后一次比较就很少比较了      

1. package com.liubo.test;
   
2. 
   
3. import java.io.IOException;
   
4. import java.util.Arrays;
   
5. public class SortDemo02 {
   
6.      public static void main(String[] args) throws InterruptedException, IOException {
   
7.           int [] arr1=new int[10000];
   
8.           int [] arr2=new int[10000];
   
9.           int [] arr3=new int[10000];
   
10.           int [] arr4=new int[10000];
    
11.           int [] arr5=new int[10000];
    
12.           int [] arr6=new int[10000];
    
13.          
    
14.           //随机生成10000个数据
    
15.           for(int i=0;i<10000;i++){     
    
16.                arr1[i]=(int) (Math.random()*1000);
    
17.                arr2[i]=arr1[i];
    
18.                arr3[i]=arr1[i];
    
19.                arr4[i]=arr1[i];
    
20.                arr5[i]=arr1[i];
    
21.                arr6[i]=arr1[i];
    
22.           }     
    
23.           System.out.println("测试数据个数:"+arr1.length);
    
24.          
    
25.           long start=System.currentTimeMillis();
    
26.           //自带排序
    
27.           Arrays.sort(arr1);     //据说这个 有两种排序 基本数据类型用快递排序  饮用对象用的是堆排序
    
28.           long end=System.currentTimeMillis();
    
29.           System.out.println("Arrays.Sort  用时:"+(end-start));
    
30.          
    
31.           start=System.currentTimeMillis();
    
32.           //冒泡排序
    
33.           bubbleSort(arr2);
    
34.           end=System.currentTimeMillis();
    
35.           System.out.println("bubbleSort  用时:"+(end-start));
    
36.          
    
37.           //选择排序
    
38.           start=System.currentTimeMillis();
    
39.           selectSort(arr3);
    
40.           end=System.currentTimeMillis();
    
41.           System.out.println("selectSort  用时:"+(end-start));
    
42.          
    
43.           start=System.currentTimeMillis();
    
44.           //插入排序
    
45.           insertSort(arr4);
    
46.           end=System.currentTimeMillis();
    
47.           System.out.println("insertSort  用时:"+(end-start));
    
48.          
    
49.          
    
50.           start=System.currentTimeMillis();
    
51.           //希尔排序
    
52.           myShellSort(arr5);
    
53.           end=System.currentTimeMillis();
    
54.           System.out.println("shellSort  用时:"+(end-start));
    
55.          
    
56.          
    
57.           //快速排序    分治法
    
58.           start=System.currentTimeMillis();
    
59.           fastSort(arr6);
    
60.           end=System.currentTimeMillis();
    
61.           System.out.println("fastSort  用时:"+(end-start));
    
62.      }
    
63.           /*
    
64.           * 冒泡排序  从最末尾的数开始来和前一个比较  每次将最小的浮到最上面
    
65.           * */
    
66.      private static void bubbleSort(int[] arr) {
    
67.           boolean flag=true;   //用来判断  如果一次冒泡下来 没变化 就说么已经排序好了 后面就不用排序了
    
68.           for(int i=0;flag&&i<arr.length-1;i++){
    
69.                flag=false;
    
70.                for(int j=arr.length-1;j>i;j--){
    
71.                     if(arr[j]<arr[j-1]){
    
72.                          swap(arr,j,j-1);
    
73.                          //交换了说明变化了
    
74.                          flag=true;
    
75.                     }
    
76.                }
    
77.           }
    
78.           //System.out.println(Arrays.toString(arr));;
    
79.      }
    
80.      
    
81.      /*
    
82.      * 每次遍历都找出最小的
    
83.      * 和被遍历的最前面的换位置  这样每次都将最小的放在前面了
    
84.      * */
    
85.      private static void selectSort(int[] arr) {
    
86.           int index=0;    //默认最小的在0
    
87.           for(int i=0;i<arr.length-1;i++){
    
88.                index=i;  //因为每次选择排序后   最小的都是剩下的最前面的那个
    
89.                for(int j=i+1;j<arr.length;j++){
    
90.                     if(arr[j]<arr[index]){
    
91.                          index=j;
    
92.                     }
    
93.                }
    
94.                if(index!=i)
    
95.                swap(arr,index,i);
    
96.           }
    
97.           //System.out.println(Arrays.toString(arr));
    
98.      }
    
99.      
    
100.      //插入排序
     
101.      private static void insertSort(int[] arr) {
     
102.           int index=0;   //被比较的位置
     
103.           int key=0;// 去比较的数的值
     
104.           for(int i=1;i<arr.length;i++){  //从第2个开始  与前面的比较  遇到第一个比他小的数 停留在那个数去的前一个位置
     
105.                index=i-1;
     
106.                key=arr[i];
     
107.                //循环
     
108.                while(index>=0 && key<arr[index]){
     
109.                     //前面大的数 后后移一位
     
110.                     arr[index+1]=arr[index];
     
111.                     index--;   //在和前面的比较
     
112.                }
     
113.                //当遇到比自己晓得或者在最前面的时候
     
114.                arr[index+1]=key;   //key的位置赵大鹏
     
115.           }
     
116.      //     System.out.println(Arrays.toString(arr));
     
117.      }
     
118. 
     
119.      //希尔排序
     
120.      private static void myShellSort(int[] arr) {
     
121.           int key=0;    //某个位置的数  要去和前面的数比较的
     
122.           int j=0;
     
123.           for(int d=arr.length/2 ; d>0 ;d/=2){
     
124.                //将这些坐标的数 3 0是一对   4 1  5 2  类推   就是当前位置  当前位置-d
     
125.                
     
126.                for(int i=d;i<arr.length;i++){
     
127.                     
     
128.                     key=arr[i];   //拿出来   每次组里面的最后一个数
     
129.                     //System.out.println(key);
     
130.                     //在每组中插入排序
     
131.                     for(j=i; j>=d;j-=d){
     
132.                          //开始循环
     
133.                               if(key < arr[j-d]){   //如果小于   就将前面大的数 移动后面那个空位置
     
134.                                    arr[j]=arr[j-d];   
     
135.                               }
     
136.                               else{
     
137.                                    break;
     
138.                               }
     
139.                     }
     
140.                     arr[j]=key;
     
141.                }
     
142.           }
     
143.           // System.out.println(Arrays.toString(arr));
     
144.      }
     
145. 
     
146.      /*
     
147.      * 分治法 先去一个数  将数组中小于他的数放在他的左边   大于他的数放在他的右边    从右边找比他小的j      左边找比他大的i   j==i exit  
     
148.      * 挖坑  填数    在依次对左边和右边这样
     
149.      *
     
150.      * */
     
151.      private static void fastSort(int[] arr) {
     
152.           int l=0,r=arr.length-1;
     
153.           fast_sort(arr,l,r);
     
154.           //System.out.println(Arrays.toString(arr));
     
155.      }
     
156.      private static void fast_sort(int[] arr, int l, int r) {
     
157.           int x=arr[l];   //每次将进来的这一段数组 的最前的数为标准 晓得填到他的左边  大的填到他的右边
     
158.           int i=r;
     
159.           int j=l;
     
160.           if(l<r){
     
161.                while(j<i){
     
162.                     //右边大的话就一直遍历下去  知道找到第一个小的
     
163.                     for(;j<i&&arr[i]>=x;i--);
     
164.                     //小的听到最前面的位置
     
165.                     if(j<i)
     
166.                     arr[j++]=arr[i];   //这时候i的位置空了
     
167.                     
     
168.                     //遍历左边的
     
169.                     for(;j<i&&arr[j]<x;j++);
     
170.                     //左边的移到右边空的位置
     
171.                     if(j<i)
     
172.                     arr[i--]=arr[j];
     
173.                }
     
174.                //最后i==j的时候
     
175.                arr[i]=x;
     
176.                //此时X为中间分为两段 分别递归
     
177.                if(l<i-1)
     
178.                fast_sort(arr,l,i-1);
     
179.                if(r>i+1)
     
180.                fast_sort(arr,i+1,r);
     
181.           }
     
182.      }
     
183. 
     
184.      //swap的
     
185.      public static void swap(int[] arr, int j,int k){
     
186.           arr[j]=arr[j]^arr[k];                    //     5^3=X      --->5=X
     
187.           arr[k]=arr[j]^arr[k];               //3=X^3=5  
     
188.           arr[j]=arr[j]^arr[k];               // X=X^5=3   换了
     
189.      }
     
190. 
     
191. }
     

复制代码

这里是测试结果



在随机生成数据下  基本就这样   冒泡(难道我的冒泡不是最优的？有更好的冒泡吗？我打印排序没错额   数据太多就没打印了 )最慢
     插入大于选择   快速和希尔差不多

好东西，排序的整理。

这个排序整理的不错，赞一个。
不同的情况适用不同的算法，单就随机生成的数据考察算法的优劣是不科学的。