四、高级排序---希尔排序

算法
算法
发布日期:   2020-10-30

1. 引言

  1. 基础排序，包括冒泡排序，选择排序还有插入排序，并且对他们在最坏情况下的时间复杂度做了分析，发现都是O(N^2)，而平方阶通过我们之前学习算法分析我们知道，随着输入规模的增大，时间成本将急剧上升，所以这些基本排序方法不能处理更大规模的问题，接下来我们学习一些高级的排序算法，争取降低算法的时间复杂度最高阶次幂。

  2. 希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

  3. 插入排序缺点：如果已排序的分组元素为{2,5,7,9,10}，未排序的分组元素为{1,8}，那么下一个待插入元素为1，我们需要拿着1从后往前，依次和10,9,7,5,2进行交换位置，才能完成真正的插入，每次交换只能和相邻的元素交换位置。那如果我们要提高效率，直观的想法就是一次交换，能把1放到
    更前面的位置，比如一次交换就能把1插到2和5之间，这样一次交换1就向前走了5个位置，可以减少交换的次数。

2. 排序思路

  1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
  2. 对分好组的每一组数据完成插入排序；
  3. 减小增长量，最小减为1，重复第二步操作。

在这里插入图片描述

3. 代码实现

  • 实际上就是在插入排序的基础上将增量1改为h，并增加一层判断h的循环

    public class Shell {
  /*
     对数组a中的元素进行排序
  */
  public static void sort(Comparable[] a){
      //1.根据数组a的长度，确定增长量h的初始值；
      int h = 1;
      while(h<a.length/2){
          h=2*h+1;
      }
      //2.希尔排序
      while(h>=1){
          //排序
          //2.1.找到待插入的元素
          for (int i=h;i<a.length;i++){
              //2.2把待插入的元素插入到有序数列中
              for (int j=i;j>=h;j-=h){

                  //待插入的元素是a[j],比较a[j]和a[j-h]
                  if (greater(a[j-h],a[j])){
                      //交换元素
                      exch(a,j-h,j);
                  }else{
                      //待插入元素已经找到了合适的位置，结束循环；
                      break;
                  }
              }

          }
          //减小h的值
          h= h/2;
      }

  }

  /*
      比较v元素是否大于w元素
   */
  private static  boolean greater(Comparable v,Comparable w){
      return v.compareTo(w)>0;
  }

  /*
  数组元素i和j交换位置
   */
  private static void exch(Comparable[] a,int i,int j){
      Comparable temp;
      temp = a[i];
      a[i]=a[j];
      a[j]=temp;
  }
}

    4. 时间复杂度分析

    在希尔排序中，增长量h并没有固定的规则，有很多论文研究了各种不同的递增序列，但都无法证明某个序列是最好的，对于希尔排序的时间复杂度分析，已经超出了我们课程设计的范畴，所以在这里就不做分析了。
    我们可以使用事后分析法对希尔排序和插入排序做性能比较。

对于希尔排序性能目前最重要的结论是：它的运行时间达不到平方级

已知在最坏情况下希尔排序的比较次数和N的3/2次方成正比

  • 希尔排序与插入排序的性能比较

    public class SortCompare {
  //调用不同的测试方法，完成测试
  public static void main(String[] args) throws Exception{
      //1.创建一个ArrayList集合，保存读取出来的整数
      ArrayList<Integer> list = new ArrayList<>();

      //2.创建缓存读取流BufferedReader，读取数据，并存储到ArrayList中；
      BufferedReader reader = new BufferedReader(new InputStreamReader(SortCompare.class.getClassLoader().getResourceAsStream("reverse_arr.txt")));
      String line=null;
      while((line=reader.readLine())!=null){
          //line是字符串，把line转换成Integer，存储到集合中
          int i = Integer.parseInt(line);
          list.add(i);
      }

      reader.close();


    //3.把ArrayList集合转换成数组
    Integer[] a = new Integer[list.size()];
    list.toArray(a);
    //4.调用测试代码完成测试
    //testInsertion(a);//37499毫秒
    testShell(a);//30毫秒
    //testMerge(a);//70毫秒

}

//测试希尔排序
public static void testShell(Integer[] a){
    //1.获取执行之前的时间
    long start = System.currentTimeMillis();
    //2.执行算法代码
    Shell.sort(a);
    //3.获取执行之后的时间
    long end = System.currentTimeMillis();
    //4.算出程序执行的时间并输出
    System.out.println("希尔排序执行的时间为："+(end-start)+"毫秒");

}

//测试插入排序
public static void testInsertion(Integer[] a){
    //1.获取执行之前的时间
    long start = System.currentTimeMillis();
    //2.执行算法代码
    Insertion.sort(a);
    //3.获取执行之后的时间
    long end = System.currentTimeMillis();
    //4.算出程序执行的时间并输出
    System.out.println("插入排序执行的时间为："+(end-start)+"毫秒");
}

//测试归并排序
public static void testMerge(Integer[] a){
    //1.获取执行之前的时间
    long start = System.currentTimeMillis();
    //2.执行算法代码
    Merge.sort(a);
    //3.获取执行之后的时间
    long end = System.currentTimeMillis();
    //4.算出程序执行的时间并输出
    System.out.println("归并排序执行的时间为："+(end-start)+"毫秒");
}

}

算法
  目录