【大话数据结构&算法】希尔排序

Love The Way You Lie 2022-09-25 01:25 181阅读 0赞

希尔排序的实质就是**分组插入排序**，该方法又称为缩小增量排序。

直接插入排序适合于序列基本有序的情况，希尔排序的每趟排序都会使整个序列变得更加有序，等整个序列基本有序了，再来一趟直接插入排序，这样会使排序效率更高，这就是希尔排序的思想。

--------------------

**基本思想总结如下**：

> 先将整个待排元素序列分割 成若干个子序列（由相隔某个“增量” 的元素组成）分别进行直接插入排序， 然后依次缩减增量再进行排序，待整个 序列中的元素基本有序（增量足够小） 时，再对全体元素进行一次直接插入排序。

--------------------

**希尔排序基本算法实现如下：**

void shellSort(int[] a, int n){
       int i,j,gap;
         //步长
         for (gap = n/2;gap > 0;gap /= 2) {
               //直接插入排序
               for(i = 0;i < gap;i++){
                     for(j = i + gap;j < n; j += gap){
                           //对一个小序列中的元素进行比较排序
                           if(a[j] < a[j - gap]){
                                 int temp = a[j];
                                 int k = j - gap;
                                 while(k >= 0 && a[k] > temp){
                                      a[k + gap] = a[k];
                                      k -= gap;
                                }
                                a[k + gap] = temp;
                          }
                    }
              }
        }
    }

--------------------

**java代码实现如下：**

public class ShellSort {
        
    
           public static void main(String[] args) {
                 int[] a = {
       9,4,2,1,5,0,6,7};
                 shellSort1(a, 8);
                 for (int i = 0; i < a.length; i++) {
                      System. out.println(a[i]);
                }
                System. out.println("***********" );
                 shellSort2(a, 8);
                 for (int i = 0; i < a.length; i++) {
                      System. out.println(a[i]);
                }
                System. out.println("***********" );
                 shellSort3(a, 8);
                 for (int i = 0; i < a.length; i++) {
                      System. out.println(a[i]);
                }
    
          }
           //严格按定义实现的希尔排序
           public static void shellSort1(int[] a, int n){
                 int i,j,gap;
                 //步长
                 for (gap = n/2;gap > 0;gap /= 2) {
                       //直接插入排序
                       for(i = 0;i < gap;i++){
                             for(j = i + gap;j < n; j += gap){
                                   //对一个小序列中的元素进行比较排序
                                   if(a[j] < a[j - gap]){
                                         int temp = a[j];
                                         int k = j - gap;
                                         while(k >= 0 && a[k] > temp){
                                              a[k + gap] = a[k];
                                              k -= gap;
                                        }
                                        a[k + gap] = temp;
                                  }
                            }
                      }
                }
          }
    
           /**
           * 优化：以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，
           * 然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，
           * 每个元素与自己组内的数据进行直接插入排序显然也是正确的。
           *
           * @param a
           * @param n
           */
           public static void shellSort2(int[] a, int n){
                 int j,gap;
                 //步长
                 for(gap = n / 2;gap > 0;gap /= 2){
                       //数组从第gap个元素开始
                       for(j = gap;j < n; j++){
                             //每个元素与自己组内的元素进行直接插入排序
                             if(a[j] < a[j - gap]){
                                   int temp = a[j];
                                   //交换a[j]和a[j-gap]的位置
                                   while(j - gap >= 0 && a[j - gap] > temp){
                                        a[j] = a[j - gap];
                                  }
                                  a[j - gap] = temp;
                            }
                      }
                }
          }
    
           /**
           * 优化：将以上优化算法的直接插入排序部分用直接插入排序算法替代
           *
           * @param a
           * @param n
           */
           public static void shellSort3(int[] a, int n){
                 int i,j,gap;
                 //步长
                 for(gap = n / 2;gap > 0;gap /= 2){
                       //数组从第gap个元素开始
                       for(i = gap;i < n;i++){
                             //交换a[i-gap]和a[i]的位置
                             for(j = i - gap;j >= 0 && a[j] > a[j + gap];j -= gap){
                                   int temp = a[j];
                                  a[ j] = a[j + gap];
                                  a[j + gap] = temp;
                            }
                      }
                }
    
          }
    
    }

--------------------

> **时间复杂度**：
> 
> 希尔排序的平均时间复杂度为**O(nlogn)\{以2为底\}**。

--------------------

> **空间复杂度**：
> 
> 希尔排序的空间复杂度同直接插入排序一样为**O(1)**。

--------------------

**注意**：希尔排序的增量取法需要注意的一点就是，**首先增量序列的最后一个值一定是1；其次增量序列中的值没有除1之外的公因子**，如8，4，2，1这样的序列就不要取，因为8，4，2有公因子2。