高级排序

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

希尔排序

希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本

前面学习插入排序的时候,我们会发现一个很不友好的情况,如果已排序的分组元素为$2,5,7,9,10$,未排序的分组元素为$1,8$,那么下一个待插入元素为$1$,我们需要拿着$1$从后往前,一次与$10,9,7,5,2$进行交换位置,才能完成正真的插入,每次交换只能和相邻的元素交换位置,那如果我们要提高效率,直观的想法就是一次交换,能把$1$放到更前面的位置,比如一次交换就能把$1$插入到$2$和$5$之间,这样一次交换$1$就向前前进了$5$个位置,可以减少交换的次数

需求

排序前:$9,1,2,5,7,4,8,6,3,5$

排序后:$1,2,3,4,5,5,6,7,8,9$

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

增长量$h$的确定:增长量$h$的值每一次固定的规则,采用以下规定

int h = 1;
    while (h < 数组长度 / 2) {
      h = 2 * h + 1;
    }
    //循环结束我们就可以确定h的最大值
    //h的减小规则
    h = h / 2;
希尔排序的API设计
类名Shell
构造方法Shell():创建Shell对象
成员方法1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值
希尔排序的代码实现

shell对象

public class Shell {

  public static void sort(Comparable[] a) {
    //首先由数组的长度来确定增长量h
    int h = 1;
    while (h < a.length / 2) {
      h = h * 2 + 1;
    }
    //进行希尔排序
    while (h >= 1) {
      /**
       * 其实我们分组,就是按0号位作为第一组元素的第一个默认排号的元素进行排序的
       * 而一共有h的间距,所以第一组第一个是0,第二组第一个是0+1,....第h组第一个是0+h*/
      for (int i = h; i <= a.length - 1; i++) {
        /**
         * 还是老样子,从后往前进行比较,只不过查看的间距不再是插入排序的1,而是h*/
        for (int j = i; j >= h; 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 = a[j];
    a[j] = a[i];
    a[i] = temp;
  }
}

测试方法

public class ShellTest {

  public static void main(String[] args) {
    Integer[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
    Shell.sort(arr);
    System.out.println(Arrays.toString(arr));
  }
}
希尔排序的时间复杂度分析

在希尔排序中,增长量$h$并没有固定的规则,很多论文研究了各种不同的递增序列,但都无法证明某个序列是最好的,对于希尔排序的时间复杂度分析,已经超出了我们设计的范畴,所以在这里不再讨论

我们可以使用事后分析法对希尔排序与插入排序做性能比较

我使用一个名叫reverse_arr.txt的文件,里面存放的是100000到1的逆向数据,我们可以根据这个批量数据完成测试,测试的思想:在执行排序前记录一个时间,在排序完成后记录一个时间,两时间的时间差就是排序的损耗时间

之所以使用逆序的数据文件,那是因为逆序是对排序来说最坏的一种情况,十分不友好,所以对测试排序算法的性能是很有效的

希尔排序和插入排序性能比较测试代码
public class SortCompare {
  //调用不同的测试方法完成测试

  public static void main(String[] args) throws Exception {
    //创建一个Arraylist集合,保存IO读取到的整数数据
    ArrayList<Integer> list = new ArrayList<>();

    //创建BufferedReader,读取数据,并存储到ArrayList中

    BufferedReader reader =
        new BufferedReader(
            new InputStreamReader(SortCompare.class.getClassLoader().getResourceAsStream(
                "reverse_arr.txt")));
    String line = null;
    while ((line = reader.readLine()) != null) {
      //line是字符串,我们需要转化成Integer的形式,才能存储到集合中
      int i = Integer.parseInt(line);
      list.add(i);
    }
    reader.close();
    //把ArrayList集合转换为数组
    Integer[] a = new Integer[list.size()];
    list.toArray(a);
    //调用测试代码
    testinsert(a);
    //插入排序的时间23458毫秒
    testshell(a);
    //希尔排序执行的时间18毫秒
  }

  //测试希尔排序

  public static void testshell(Integer[] a) {
    long start = System.currentTimeMillis();
    Shell.sort(a);
    long end = System.currentTimeMillis();
    System.out.println("希尔排序执行的时间" + (end - start) + "毫秒");
  }

  //测试插入排序

  public static void testinsert(Integer[] a) {
    long start = System.currentTimeMillis();
    Insertion.sort(a);
    long end = System.currentTimeMillis();
    System.out.println("插入排序的时间" + (end - start) + "毫秒");
  }
}
  • 插入排序的时间23458毫秒
  • 希尔排序执行的时间18毫秒

归并排序

递归

在正式学习归并排序之前,我们得先学习一下递归算法

定义

定义方法时,在方法内部调用方法本身,称之为递归

例:

public void show() {
    System.out.println("test");
    show();
  }
作用

它通常把一个大型复杂的问题,层层转换为一个与原问题相似的,规模较小的问题来求解,递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量

注意事项

在递归中,不能无限制的调用自己,必须要有边界条件,能够让递归结束,因为每一次递归调用都会在栈内存中开辟新的空间,重新执行方法,如果递归的层级太深,很容易造成内存溢出

graph TB
        subgraph 栈内存
         idn[第n+1次,栈内存溢出]
         id2[第二次调用]
         id1[第一次调用]
         id2-.-idn
         id1-.-id2
        end
需求

请定义一个方法,使用递归方法完成求$N$的阶乘

/**
     * 分析
     * 1!:  1
     * 2!:  2*1=2*1!
     * 3!:  3*2*1=3*2!
     * 4!:  4*3*2*1=4*3!
     * ...
     * n!:  n*(n-1)*(n-2)*...*2*1=n*(n-1)!
     * 所以,假设有一个方法factorial用来求n的阶乘,那么n的阶乘还可以表示为n*factorial(n-1)*/
代码实现
public static void main(String[] args) {
    long result = factorial(5);
    System.out.println(result);
  }

  public static long factorial(int n) {
    if (n == 1) {
      return 1;
    } else {
      return n * factorial(n - 1);
    }
  }

归并排序

归并排序是建立在归并操作上的一种有效的排序方法,该算法是采用分治法的一个非常典型的应用,将已有序的子序合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序,若将两个有序表合并成一个有序表,称为二路归并

需求

排序前:$8,4,5,7,1,3,6,2$

排序后:$1,2,3,4,5,6,7,8$

排序原理
  1. 尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是$1$为止
  2. 将相邻的两个子组进行合并成一个有序的大组
  3. 不断重复步骤$2$,直到最终只有一个组为止

归并排序API设计
类名Merge
构造方法Merge():创建Merge对象
成员方法1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static void sort(Comparable[] a,int lo,int hi):对数组a中从索引lo到索引hi之间的元素进行排序 3.private static void merge(Comparable[] a,int lo,int mid,int hi):从索引lo到索引mid为一个子组,从索引mid+1到索引hi为另一个子组,把数组a中的这两个子组的数据合并成一个有序的大组(从索引lo到索引hi) 4.private static boolean less(Comparable v,Comparable w):判断v是否小于w
成员变量1.private static Comparable[] assist:完成归并操作所需要的辅助数组
归并原理

代码实现

Merge

public class Merge {

  /**
   * 归并所需要的辅助数组
   */
  private static Comparable[] assist;

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

  /**
   * 对数组a中的元素进行排序
   */
  public static void sort(Comparable[] a) {
    //1.初始化辅助数组assist
    assist = new Comparable[a.length];
    //2.定义一个lo变量和hi变量,分别记录数组中最小的索引位置和最大的索引位置
    int lo = 0;
    int hi = a.length - 1;
    //3.调用sort的重载方法完成数组a中,从索引lo到索引hi的元素的排序
    sort(a, lo, hi);
  }

  /**
   * 对数组a中从lo到hi的元素进行排序
   */
  private static void sort(Comparable[] a, int lo, int hi) {
    //做安全性校验
    if (hi <= lo) {
      return;
    }
    //对从lo到hi之间的数据进行分组,分为两组
    int mid = lo + (hi - lo) / 2;
    //分别对每一组进行排序
    sort(a, lo, mid);
    sort(a, mid + 1, hi);
    //再将两个组的数据合在一起,进行归并
    merge(a, lo, mid, hi);
  }

  /**
   * 对数组中,从lo到mid为一组,从mid+1到hi为一组,对这两组数据进行归并
   */
  private static void merge(Comparable[] a, int lo, int mid, int hi) {
    //定义三个指针,一个指向数组头lo作为归并辅助数组assist的头,一个指向待归并数组的头作为左数组的头,一个作为待归并右数组的头
    int i = lo;
    int p1 = lo;
    int p2 = mid + 1;
    //遍历左右两个数组,移动p1与p2两个指针,将数字较小的元素放入到辅助数组assist中
    while (p1 <= mid && p2 <= hi) {
      //比较对应元素的值
      if (less(a[p1], a[p2])) {
        assist[i++] = a[p1++];
      } else {
        assist[i++] = a[p2++];
      }
    }
    //当左数组遍历完或者右数组遍历完,就将剩下的一遍数组的剩余元素全部移动到辅助数组上去
    while (p1 <= mid) {
      assist[i++] = a[p1++];
    }
    while (p2 <= hi) {
      assist[i++] = a[p2++];
    }
    //全部归并且排好序了,将辅助数组复制到原数组当中
    for (int index = lo; index <= hi; index++) {
      a[index] = assist[index];
    }
  }
}

MergeTest

public static void main(String[] args) {
    Integer[] a = {8, 4, 5, 7, 1, 3, 6, 2};
    Merge.sort(a);
    System.out.println(Arrays.toString(a));
  }
归并排序的时间复杂度

归并排序是分治思想的最典型的例子,上面的算法中,对$a[lo...hi]$进行排序,先将它分为$a[lo...mid]$与$a[mid+1...hi]$两部分,分别通过递归调用将他们单独排序,最后将有序的子数组归并为最终的排序结果,该递归的出口就在于如果一个数组不能再被分为两个子数组,那么就会执行$merge$进行归并,在归并的时候判断元素的大小进行排序

用树状图来描述归并,如果一个数组有$8$个元素,那么它将每次除以$2$才能找到最小的子数组,一共拆分$log_28$次,值为$3$次,所以数的层数一共是$3$层,那么从顶部到向下第$k$层,第$k$层就有$2^k$个子数组,每个数组的长度为$2^(3-k)$,归并最多需要$2^(3-k)$次比较,因此每层的比较次数为$2^k\times2^(3-k)=2^3$,那么$3$层总共为$3\times2^3$

假设元素的个数为$n$,那么使用归并排序拆分的次数为$log_2^n$层,那么使用$log_2^n$替换上面$3\times2^3$中的$3$这个层数,最终得出的归并排序的时间复杂度为:$log_2^n\times2^(long_2^n)=nlog_2^n$,根据大$O$法则,忽略底数,最终归并排序的时间复杂度为$O(nlogn)$

归并排序的缺点

需要申请额外的数组空间,导致空间复杂度提升,是典型的以空间换时间的算法

归并排序与希尔排序的性能测试

我们使用同样的测试方法来完成这两个排序算法之间的性能比较,仍然使用reverse_arr.txt文件,里面存放的是从1000000到1的逆向数据,我们可以根据这个批量数据完成测试,测试的思想:在执行排序前记录一个时间,在排序完成后记录一个时间,两个时间的差就是排序的耗时

希尔排序和插入排序性能比较测试代码
public static void testMerge(Integer[] a) {
    long start = System.currentTimeMillis();
    Merge.sort(a);
    long end = System.currentTimeMillis();
    System.out.println("归并排序执行的时间" + (end - start) + "毫秒");
  }
  • 归并排序执行的时间33毫秒

快速排序

快速排序是对冒泡排序的一种改进,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

需求

排序前:$6,1,2,7,9,3,4,5,8$

排序后:$1,2,3,4,5,6,7,8,9$

排序原理
  1. 首先设定一个分界值,通过该分界值将数组分成左右两部分
  2. 将大于或等于分界值的数据放到数组右边,小于分界值的数据放到数组的左边,此时左边部分中各元素都小于或等于分界值,而右边部分中各个元素都大于或等于分界值
  3. 然后,左边和右边的数据可以独立排序,对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值,右侧的数组数据也可以做类似处理
  4. 重复上述过程,可以看出,这是一个递归定义,通过递归将左侧部分排好序后,再递归排好右侧部分的顺序,当左侧和右侧两个部分的数据排完序后,整个数组的排序也就完成了

快速排序API设计
类名Quick
构造方法Quick():创建Quick对象
成员方法1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static void sort(Comparable[] a,int lo,int hi):对数组a中从索引lo到索引hi之间的元素进行排序 3.public static int partition(Comparable[] a,int lo,int hi):对数组a中,从索引lo到索引hi之间的元素进行分组,并返回分组界限对应的索引 4.private static boolean less(Comparable v,Comparable w):判断v是否小于w 5.private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值
切分原理

把一个数组切分成两个子数组的基本思想:

  1. 找一个基准值,用两个指针分别指向数组的头部和尾部
  2. 先从尾部向头部开始搜索一个比基准值小的值,搜索到立即停止,并记录指针的位置
  3. 再从头部向尾部开始搜索一个比基准值大的值,搜索到立即停止,并记录指针的位置
  4. 交换当前左边指针位置和右边指针位置的元素
  5. 重复$2,3,4$步骤,直到左边指针的值大于右边指针的值为止
代码实现

Quick

public class Quick {

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

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

  /**
   * 对数组内的元素进行排序
   */
  public static void sort(Comparable[] a) {
    int lo = 0;
    int hi = a.length - 1;
    sort(a, lo, hi);
  }

  /**
   * 对数组a中从索引lo到索引hi之间的元素进行排序
   */
  private static void sort(Comparable[] a, int lo, int hi) {
    //安全性校验
    if (hi <= lo) {
      return;
    }
    //需要对数组中lo索引到hi索引处的元素进行分组(左子组和右子组)
    //返回的是分组的分界值所在的索引,是分界值位置变换后的索引
    int partition = partition(a, lo, hi);
    //让左子组有序,因为partition是分界值,不需要排序,所以是partition-1
    sort(a, lo, partition - 1);
    //让右子组有序,因为partition是分界值,不需要排序,所以是partition+1
    sort(a, partition + 1, hi);
  }

  /**
   * 对数组a中,从索引lo到索引hi之间的元素进行分组,并返回分组界限对应的索引
   */
  public static int partition(Comparable[] a, int lo, int hi) {
    //确定分界值
    Comparable key = a[lo];
    //定义两个指针,分别指向待切分元素的最小索引处与最大索引处的下一位置
    int left = lo;
    int right = hi + 1;
    //切分
    while (true) {
      //先从右往左扫描,移动right指针,找到一个比分界值小的元素,并停止
      while (less(key, a[--right])) {
        if (right == lo) {
          break;
        }
      }
      //再从左往右扫描,移动left指针,找到一个比分界值大的元素,并停止
      while (less(a[++left], key)) {
        if (left == hi) {
          break;
        }
      }
      //判断left>=right,如果是则证明元素全部扫描完毕,结束循环,如果不是,继续扫描
      if (left >= right) {
        break;
      } else {
        exch(a, left, right);
      }
    }
    //这里主要要写right,因为left可能还会向右移动一格,所以就形成了left>right,所以真正的中间位置是right,而不是left
    exch(a, lo, right);
    return right;
  }
}

QuickTest

public static void main(String[] args) {
    Integer[] a = {6, 1, 2, 7, 9, 3, 4, 5, 8};
    Quick.sort(a);
    System.out.println(Arrays.toString(a));
  }
快速排序和归并排序的区别

快速排序是另一种分治的排序方法,它将一个数组分成两个子数组,将两部分独立的排序,快速排序和归并排序是互补的,归并排序将数组分成两个子数组分别排序,并将有序的子数组归并从而将整个数组排序,而快速排序的方法则是当两个数组都有序时,整个数组自然就有序了,在归并排序中,一个数组被等分为两半,归并调用发生在处理整个数组之前,在快速排序中,切分数组的位置取决于数组的内容,递归调用发生在处理整个数组之后

快速排序时间复杂度

快速排序的一次切分从两头开始交替搜索,直到$left$和$right$重合,因此一次切分算法的时间复杂度为$O(n)$,但整个快速排序的时间复杂度和切分的次数有关

  • 最优情况:每一次切分选择的基准数字刚好将当前序列等分

如果我们把数组的切分看做是一个树,那么上图就是它的最优情况的图示,共切分了$logn$次,所以最优情况下快速排序的时间复杂度为$O(nlogn)$

  • 最坏情况:每一次切分选择的基准数字是当前序列中最大数或者最小数,这使得每次切分都会有一个子组,那么总共就得切分$n$次,所以最坏情况下,快速排序的时间复杂度为$O(n^2)$
  • 平均情况:每一次切分选择的基准数字不是最大值和最小值,也不是中间值,这种情况我们就可以用数学归纳法证明,快速排序的时间复杂度为$O(nlogn)$

排序的稳定性

稳定性的定义

数组$arr$中有若干元素,其中$A$元素和$B$元素相等,并且$A$元素在$B$元素前面,如果使用某种排序算法排序后,能够保证$A$元素依然在$B$元素的前面,可以说这个算法是稳定的

稳定性的意义

如果一组数据只需要一次排序,则稳定性一般是没有意义的,但如果一组数据需要多次排序,稳定性则是有意义的,例如要排序的内容是一组商品对象,第一次排序按照价格由低到高进行排序,第二排序按照销量由高到低排序,如果第二次排序使用稳定性算法,就可以使得相同销量的对象依旧保持着价格由低到高的顺序展开,只有销量不同的对象才需要重新排序,这样既可以保持第一次排序的原有意义,而且可以减少系统开销

  1. 按照价格由低到高排序
商品名称价格销量
三星S20399923
一加9499957
Iphone12599957
Mac Air699934
  1. 按照销量由高到低排序
商品名称价格销量
一加9499957
Iphone12599957
Mac Air699934
三星S20399923
常见排序算法的稳定性
  • 冒泡排序:只有当$arr[i]>arr[i+1]$的时候,才会交换元素的位置,而相等的时候并不交换位置,所以冒泡排序是一种稳定排序算法
  • 选择排序:选择排序是给每个位置选择当前元素最小的,例如有数据$5(第一个),5(第二个),2,9$,第一遍选择到的最小元素为$2$,所以$5(第一个 )$会与$2$进行交换位置,此时$5(第一个 )$到了$5(第二个 )$后面,破坏了稳定性,所以选择排序是一种不稳定的排序算法
  • 插入排序:比较是从有序列表的末尾开始的,也就是想要插入的元素和已经有序的最大元素开始比较,如果比它大则直接插入在其后面,否则一直往前直到找到它该插入的位置,如果遇到一个和插入元素相等的,那么把插入的元素放在相等元素的后面,所以相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的
  • 希尔排序:希尔排序是按照不同长度的分组对元素进行插入排序,虽然一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相对的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的
  • 归并排序:归并排序在归并的过程中,只有$arr[i]<arr[i+1]$的时候才会交换位置,如果两个元素相等则不会交换位置,所以它并不会破坏稳定性,归并排序是稳定的
  • 快速排序:快速排序需要一个基准值,在基准值的右侧找一个比基准值小的元素,在基准值的左侧找一个比基准值大的元素,然后交换这两个元素,此时会破坏稳定性,所以快速排序是一种不稳定的排序
Last modification:April 4th, 2021 at 05:13 pm