初级排序算法

算法2.1 选择排序(升序)

  1. import edu.princeton.cs.algs4.In;
  2. import edu.princeton.cs.algs4.StdOut;
  4. public class Selection {
  5.     public static void sort(Comparable[] a){
  6.         for(int i = 0; i < a.length; i++){
  7.             int min = i;
  8.             for(int j = i + 1; j < a.length; j++){
  9.                 if(less(a[j],a[min])) min = j;
  10.             }
  11.             exch(a,i,min);
  12.         }
  13.     }//升序选择排序
  15.     private static boolean less(Comparable v, Comparable w){
  16.         return v.compareTo(w) < 0;
  17.     }//比较v是否小于w
  19.     private static void exch(Comparable[] a, int i, int j){
  20.         Comparable t = a[i];
  21.         a[i] = a[j];
  22.         a[j] = t;
  23.     }//元素交换
  25.     private static void show(Comparable[] a){
  26.         for(int i = 0; i < a.length; i++)
  27.             StdOut.print(a[i] + " ");
  28.         StdOut.println();
  29.     }//单行打印
  31.     public static boolean isSorted(Comparable[] a){
  32.         for(int i = 1; i < a.length; i++){
  33.             if(less(a[i],a[i-1])) return false;
  34.         }
  35.         return true;
  36.     }//判断是否有序
  38.     public static void main(String[] args){
  39.         String[] a = In.readStrings();
  40.         sort(a);
  41.         assert isSorted(a);
  42.         show(a);
  43.     }
  44. }

要点

  1. 选择排序外循环负责移动当前位置,内循环比较当前元素和已知最小元素,选择剩余元素中最小者安排在当前位置,选择排序不会访问索引左侧的元素
  2. 核心变量:i:控制索引,j:负责与索引元素比较的位置,min:时刻标记剩余元素中最小的索引

特点

  1. 对于长度为N的数组:选择排序需要大约N²/2次比较(调用less())和N次交换(调用exch())

证明:

  1. public static void sort(Comparable[] a){
  2.         for(int i = 0; i < a.length; i++){
  3.             int min = i;
  4.             for(int j = i + 1; j < a.length; j++){
  5.                 if(less(a[j],a[min])) min = j;
  6.             }
  7.             exch(a,i,min);
  8.         }
  9.     }

根据sort(),j范围[1,N-1],则比较次数(N-1)+(N-2)+…+1 == N(N-1)/2 ~ N²/2,i范围[0,N-1]则交换N次

  1. 运行时间和输入(初始状态)无关:为了找出最小元素而扫描一遍数组并不能为下一遍扫描提供信息,一个有序数组和一个完全随机的数组排序时间是一样的
  1. 数据移动是最少的:N次交换—交换次数和数组大小时线性关系,书中其他算法都不具有此特征,大部分增长级都是线性对数或平方级别.

算法2.2 插入排序(升序)

  1. //只有sort()不同
  2. public static void sort(Comparable[] a){
  3.         for(int i = 1; i < a.length; i++){
  4.             for(int j = i; j > 0 && less(a[j],a[j-1]); j--){
  5.                 exch(a,j,j-1);
  6.             }
  7.         }
  8.     }//升序插入排序

要点

  1. 插入排序外循环从a[1]开始,设定当前索引左侧元素都是有序的,内循环只需把索引元素插入到前面的合适位置,插入排序不会访问索引右侧的元素
  2. 低级错误:for(a;b;c){d}循环中b满足时,执行d再执行c,若b不满足,直接跳出循环;

特点

  1. 对于长度为N的数组:插入排序需要~N²/4次比较和~N²/4次交换.最坏情况下(完全倒序)需要~N²/2次比较和~N²/2次交换,最好情况下(已排好序)需要N-1次比较和0次交换

证明:

  1. public static void sort(Comparable[] a){
  2.         for(int i = 1; i < a.length; i++){
  3.             for(int j = i; j > 0 && less(a[j],a[j-1]); j--){
  4.                 exch(a,j,j-1);
  5.             }
  6.         }
  7.     }

假设倒序:则比较次数1+2+…+(N-1) == N(N-1)/2 ~ N²/2,倒序下每次比较后都需要交换,次数相同;假设排好序: 内层for循环(j > 0 && less(a[j],a[j-1]))限制只用比较(N-1)次,且不用进入循环内部交换,则交换0次

2.
倒置: 数组中两个顺序颠倒的元素,如4,3,7,5,1中如果要求升序则倒置为4-1,4-3,3-1,7-5,7-1,5-1共6对
部分有序: 如果数组中倒置的数量小于数组大小的某个倍数,则该数组为部分有序的
插入排序的交换次数和倒置的对数相同,需要比较的次数>=倒置对数,<=倒置对数+(N-1)
证明: 交换一次就减少了一对倒置数,当倒置数为0,即排序完成;而每次交换一定有一次比较,且1到N-1之间的每个 i都可能需要一次额外的比较(在a[i]刚交换完,j—后确认a[i]是否到了合适的位置,这时发生额外的比较)

算法2.3 希尔排序(升序)

  1. public class Shell {
  2.     public static void sort(Comparable[] a){
  3.         int N = a.length;
  4.         int h = 1;
  5.         while (h < N/3) h = h*3 + 1;//1,4,13,40,121,364......
  6.         while (h >=1){
  7.             for(int i = h; i < N; i++){
  8.                 for(int j = i; j - h >= 0 && less(a[j],a[j-h]); j -=h)
  9.                     exch(a,j,j-h);
  10.             }
  11.             h = (h-1)/3;
  12.         }
  13.     }//升序希尔排序

要点

  1. 由插入排序可知,对于越接近有序的数组,插入排序效率越高.希尔排序即通过交换间隔h的元素,对数组局部排序,在最终h = 1时就是一般的插入排序.
  2. 希尔排序是使数组中任意间隔h的元素都是有序的,这样的数组被称为h有序数组,为了动态调整h达到灵活调整顺序的目的,需要通过循环实时调整或数组提前预存方式实现h的变化序列,称为增长序列,算法2.3使用序列1/2(3^k-1),h在[1,N/3)变化,可以是1,4,13,40,121,364,1093…
  3. 与一般插入排序对比
    | 排序方式 | i初始值 | less参数 | | :—-: | :—-: | :—-: | | 插入 | 1 | a[j],a[j-1] | | 希尔 | h | a[j],a[j-h] |

特点

  1. 希尔排序的性能特征无法准确描述,但速度明显快于插入/选择排序,可以处理大型数组,目前只能说它的运行时间达不到平方级别