Java基础知识强化57：经典排序之希尔排序（ShellSort）

1. 希尔排序的原理：

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

在上面这幅图中：

初始时，有一个大小为 10 的无序序列。

在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。

接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。

按照直接插入排序的方法对每个组进行排序。

在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。

按照直接插入排序的方法对每个组进行排序。此时， 排序已经结束。

需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。（希尔排序的不稳定性）

所以，希尔排序是不稳定的算法。

 

2. 希尔排序代码实现：

package cn.itcast;  2 
/*
 * 希尔排序：先取一个小于n的整数d1作为第一个增量，  5  * 把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。  6  * 先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，  7  * 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。  8  */
public class ShellSort { 10     public static void main(int[] data) { 11         for (int i = data.length / 2; i > 2; i /= 2) { 12             for (int j = 0; j < i; j++) { 13  insertSort(data, j, i); 14  } 15  } 16         insertSort(data, 0, 1); 17  } 18 
    /**
 * @param data 21  * @param j 22  * @param i 23      */
    private static void insertSort(int[] data, int start, int inc) { 25         for (int i = start + inc; i < data.length; i += inc) { 26             for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) { 27                 swap(data, j, j - inc); 28  } 29  } 30  } 31     /*
 * 交换数组中的两个元素 33      */
    public static void swap(int[] data, int i, int j) { 35         int temp = data[i]; 36         data[i] = data[j]; 37         data[j] = temp; 38  } 39 } 40 /*
 * 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序 　　 42  * 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组， 43  * 组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1， 即所有记录放进一个组中排序为止 　　 44  * 初始：d=5 　　49 38 65 97 76 13 27 49 55 04 　　 45  * 49 13 　　|-------------------| 　　 46  * 38 27 |-------------------| 　　 47  * 65 49 　　|-------------------| 　　 48  * 97 55 |-------------------| 　　 49  * 76 04 　　|-------------------| 　　 50  * 一趟结果 　　13 27 49 55 04 49 38 65 97 76 　　 51  * d=3 　　 13 27 49 55 04 49 38 65 97 76 　　 52  * 13 55 38 76 |------------|------------|------------| 　　 53  * 27 04 65 |------------|------------| 　　 54  * 49 49 97 |------------|------------| 　　 55  * 二趟结果 13 04 49* 38 27 49 55 65 97 76 　　 56  * d=1 　　13 04 49 38 27 49 55 65 97 76 57  * 　　 |----|----|----|----|----|----|----|----|----| 　　 三趟结果 　　 58  * 04 13 27 38 49 49 55 65 76 97 59  */

 

3. 希尔排序示例代码：

package com.himi.classicort;  2 
public class ShellSortDemo {  4     
    public static void main(String[] args) {  6         
        int[] array = new int[] {12, 33, 4, 15, 25, 55, 18};  8         
        System.out.println("希尔排序之前的数组："); 10  printArray(array); 11         
 System.out.println(); 13         
        System.out.println("希尔排序之后的数组："); 15  shellsort(array); 16  printArray(array); 17     
 } 19 
    
    
    
    
    public static void shellsort(int[] array) { 25         int d = array.length; 26         while (true) { 27             
            for (int i = 0; i < d; i++) { 29                 
                for (int j = i; j + d < array.length; j += d) { 31                     int temp; 32                     
                    if (array[j] > array[j + d]) { 34                         temp = array[j]; 35                         array[j] = array[j + d]; 36                         array[j + d] = temp; 37  } 38  } 39  } 40 
            if (d == 1) { 42                 break; 43  } 44             d--; 45  } 46         
 } 48     
    public static void printArray(int[] array) { 50 
        System.out.print("["); 52         
        int i; 54         for(i= 0; i<array.length; i++) { 55             
            if(i ==array.length-1) { 57  System.out.print(array[i]); 58             } else { 59                 System.out.print(array[i]+","); 60  } 61  } 62         System.out.print("]"); 63         
 } 65 }

运行程序，如下：