一些经典排序算法及其 Java 实现

排序

学习算法总是从排序开始的，我这再次重新学习也不例外。主要根据《算法图解》，《算法第四版》这几本书进行重新学习，其中算法第四版是值得特别学习的。

这里尽量按算法第四版中讲述的顺序来。从最糟糕的选择排序，到插入排序，到优化插入排序的希尔排序（终于进入 n*logn 的领域了！），再到归并排序，快排，堆排序……

下面的排序算法都默认按照升序排列。

选择排序

选择排序是最简单的排序，它每次选择数组中一个最小或最大的元素，将其置于数组的首位，然后对子数组进行相同操作，直到整个数组有序。

下面是选择排序的代码——

void select_sort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) { // 将 a[i] 同 a[i+1..arr.length] 中的最小值交换
        int min = i; // 这里的 min 是最小元素的 index
        for (int j = i + 1; j < len; j++)
            if (arr[j] < arr[min]) 
                min = j; //发现了新的最小值，更新 min
        exch(arr, i, min); //交换 arr[i] 和 arr[min]
    }
}

选择排序的比较次数约为 n^2/2 次，交换次数为 n 次。选择排序的比较次数和交换次数不随输入的变化而变化，无论输入是完全随机还是基本有序，这说明选择排序并没有利用到输入数据的原始状态。插入排序改善了这一点。

插入排序

插入排序遵循这样的逻辑——将一个元素插入到已经有序的元素内。

void insert_sort(int[] arr) {
  int len = arr.length;
  for (int i = 1; i < len; i++) { //遍历 arr[1..len]，将其每一位都插入到其前面的数组中
    for (int j = i; j >= 1; j--) //将 arr[j] 插入到 arr[0..j] 中，其中 arr[0..j] 必定有序
      if (arr[j] < arr[j - 1]) //这里的 if 的判断可以加到 for 循环里，就不需要这个 if 了，但是这样逻辑更清楚一些
        exch(arr,j,j-1);// 如果待插入元素小于其前面的元素（逆序），则交换
      else
        break; //如果不小于，则说明待插入元素已经到达正确位置
  }
}

插入排序的最优比较次数是 n，最优交换次数是 0，最坏（完全逆序，每次插入需要插到数组首位）比较次数是 n^2/2，最坏交换次数是 n^2/2，平均（每次插入都正好插到正中间）交换次数是 n^2/4，平均比较次数是 n^2/4。显然，插入排序是优于选择排序的。

希尔排序

希尔排序是插入排序的改进。它定义间隔 h，以此将数组分为 h 个子数组（如，定义 h 为 2，则数组可以分为 0，2，4，6……和 1，3，5，7……），对任一子数组都进行插入排序（这使不相邻的元素也能够进行交换，因此能够减少交换次数），使任一子数组都有序，这时原数组称为 h 有序数组；然后减少 h，重复以上过程，直到最后 h 达到 1，此时的排序等同于插入排序，从而保证原数组有序。（可以认为，希尔排序的过程就是整体从无序越来越趋近有序的过程，前面提到过，插入排序对基本有序的数组是非常适合使用的）

这里的 h 一般使用等比数列 1/2(3^n - 1) 中（它的值为 1,4,13,40,121,364,1093……）大于等于 n/3 的第一个元素，这里的 n 为数组长度。之后，每次将 h 除以 3（获取数列中前一项），重复操作，直到最后一次 h 为 1，操作后数组有序。

比如对数组

{ 1, 10, 2, 6, 4, 6, 8, 1, 0, 3, 5, 9, 3, 2 }

n 为 14，则 14/3 == 4， 选择 4 为 h，则分割出来的子数组为——

// 横着看
1 4 0 3
10 6 3 2
2 8 5
6 1 9

上代码！

这里对每一次的 h 有序数组中的各子数组是在同一个 for 循环里（for (int i = h; i < len; i++)）进行的，它对任一个下标为 i 的元素都插入到它所属的子数组中（下标为 i-h,i-2h,i-3h…）。当然也可以每次直接排完一个子数组，但那样写起来更加复杂。

void shell_sort(int[] arr) {
    int len = arr.length;
    int h = 1; //间隔
    while (h < len / 3) h = h * 3 + 1; //等比数列的性质……总之这里得到大于等于 len/3 的数列中的第一个元素
    
    while (h >= 1) { //h==1 的时候执行最后一次，此时是整个数组基本有序，对整个数组进行插入排序
        for (int i = h; i < len; i++) {//每一个子数组的插入排序都在这里完成，可别把 i++写成 i+=h 了，这样就只排了其中一个子数组！
        	for (int j = i; j >= h; j-=h) {//将 arr[j] 插入到 arr[j-h],arr[j-2*h],arr[j-3*h]... 中
                if (arr[j] < arr[j - h])
                    exch(arr, j, j - h);
       			else
                    break; //同插入排序，写地更易懂些
            }
        }  
        h /= 3; //该数列满足这样的条件，其元素每次除以三就能获得前一项
    }
}

快速排序

快速排序可以这样描述——每次找到一个元素作为切分，将其置于正确的位置，并让其左边的元素都小于等于它，让其右边的元素都大于等于它，其后对其左右数组再次进行同样操作，直到数组长度为 1 或 0 时结束。

快排用 Haskell 代码能够非常优雅地描述。

sort :: [a] -> (a -> a -> Bool) -> [a] -- fn 为比较函数 
sort [] fn = []
sort [x] fn = [x]
sort (x:xs) fn = 
    lesser ++ [x] ++ larger
    where 
        lesser = sort [i | i <- xs, fn i x] fn
        larger = sort [i | i <- xs, not $ fn i x] fn

“让其左边的元素都小于等于它，让其右边的元素都大于等于它”这个操作需要使用两个指针，每次找到的元素将其交换，当两个指针交错或相同则跳出，将切分元素与后一个指针交换，就能达到置于正确位置的目的，然后对左右数组进行递归操作。快速排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)，为原地 (in-place) 排序。

void quicksort(int[] arr, int start, int end) { //初值是 arr,0,arr.length
    if (end - start <= 1) return; //递归的 base case，这里可以优化成在数组长度小于一定值（5~15）时使用插入排序
    int i = start; // i 在第一次循环时值为 pivot 的下一个元素的 index
    int j = end;
    int pivot = start; // 切分的 index
    while(true) {
        while (arr[++i]<arr[pivot]) if (i == end - 1) break; //找到第一个大于等于 pivot 的元素，if 防止越界
        while (arr[pivot]<arr[--j]) if (j == start) break; //找到第一个小于等于 pivot 的元素，这里的 if 在 pivot 为 start 的时候是冗余的，毕竟自己总是大于等于自己的，j 自减后，j==start 的时候一定会跳出 while。
        if (i >= j) break; //i，j 交错，循环结束
        exch(arr, i, j); //将大的移到右边，小的移到左边
    }
    exch (arr, pivot, j); //这次交换时，j 在前，指向最后一个小于等于 pivot 的元素，i 在后，指向第一个大于等于 pivot 的元素，这里当然得同 j 交换，不然就把一个大于等于 pivot 的元素放到前面去了，如果这个元素大于 pivot，则就无法满足条件了。如果切分使用最后一个元素，这里就应当使用 i 了
    quicksort (arr, start, j);
    quicksort (arr, j + 1, end);
}

然后是一个非常骚的实现，不过有一些不必要的交换——

// 区间前闭后闭
static void sort(int[] arr, int startIndex, int lastIndex) {
     // 基线条件
        if (lastIndex - startIndex <= 1) {return;}
        // 以尾部为 pivot
        int pivot = arr[lastIndex];
        int leftPointer = startIndex - 1;
        // 最后一次遍历时将会对 pivot 进行移动
        for (int i = startIndex; i <= lastIndex; i++) {
            if (arr[i] <= pivot) { //可以认为这里的 i 是用来统计小于等于 pivot 的元素的数量的（并且将这样的元素都往前移）
                leftPointer++;
                exch(arr, i, leftPointer);
            }
        }
        sort(arr, startIndex, leftPointer - 1);
        sort(arr, leftPointer, lastIndex);
}

这种实现实际上就是在遍历中维护数组和一个指针，并保证这样的状态——这个指针及其左边的所有元素始终小于等于 pivot。每次遇到小于等于 pivot 的元素，指针和数组将进行变动以维护该状态。最后一次遍历时，参与比较的是标兵本身，最终指针的位置就是标兵应当处在的位置。

归并排序

归并排序是典型的分治算法。在每次排序中，它将数组分成两份，对两份进行排序，然后将其归并 (merge) 到一起。这里的归并使用辅助空间则容易编写。

归并排序的递归（自顶向下）方法很容易编写——

int[] temp;
void sort(int[] arr) {
    temp = new temp[arr.length]; //temp 数组用于 merge 操作中暂存元素
    sort(arr,0, arr.length);
}
void sort(int[] arr, int start, int end) {
    if (end - start <= 1) return; //长度为 0 或 1 的数组不需要排序
    int mid = (start + end) / 2;
    sort(arr, start, mid); // 排序 arr[start..mid]
    sort(arr, mid, end); // 排序 arr[mid..end]
    merge(arr, start, mid, end);
}
void merge(int[] arr, int start, int mid, int end) {
    // 将 arr[start..mid] 和 arr[mid..end] 归并，首先将其移动到辅助数组中
    for (int i = start; i < end; i++)
        temp[i] = arr[i];
    
    int i = start;
    int j = mid;
    // 双指针法…找到 temp[i],temp[j] 中较小的那个，将其移入归并数组中
    //这里不用 while 循环，能用 for 就用 for
    for (int p = start; p < end; p++)
        if (i >= mid)
            arr[p] = temp[j++]; // 第一个数组到顶了，后面只用迁移第二个数组
    	else if (j >= end)
            arr[p] = temp[i++]; //第二个数组到顶
    	else if (arr[i] < arr[j]) //两数组都没到顶，找小的那个
            arr[p] = temp[i++];
    	else
            arr[p] = temp[j++];
}

自底向上的归并排序也是容易理解的，它每次把数组分为长度为 1,2,4,8,16……（直到其长度大于数组长度）的子数组，对每个这样的子数组，两两进行归并操作（对于每次归并操作，其两个子数组一定是在前一次归并中已经被排序的，而长度为 1 的子数组是有序的）。

static void sort(int[] arr) {
    temp = new int[arr.length];
    for (int len = 1; len < arr.length; len *= 2) { // len 为每个待归并的子数组长度
        // 对每个长度的每个子数组，这里的 i 是数组的起始，数组的长度为 len
        for (int i = 0; i < arr.length - len; i += len*2) { 
            // merge 数组 [i,i + len/2],[i + len/2+1, i + len]
            int left = i;
            int mid  = left + len - 1;
            int right = Math.min(arr.length - 1, left + len + len - 1);
            merge(arr, left, mid, right);
        } 
    }
}

堆排序

关于堆及其提供的两个方法 swim，sink，见 [这篇文章](../12-03 关于堆 heap/)。

堆排序的过程可以如下理解——

1. 首先将数组构建成一个堆（如果要升序排序，则构建大顶堆，如果要降序排序，则构建小顶堆），这构建过程表现在对堆中的从 N/2 到 1 为下标的元素进行 sink 操作（对没有子节点的元素进行 sink 方法是无意义的，从后往前使用 sink 方法保证对任何调用 sink 方法的元素，其子节点都是堆。也可以对所有元素调用 swim 方法，但这样显然是更加低效的，不像 sink 方法能够利用其左右节点是已经堆有序这样的性质）。
2. 然后，每次将堆顶元素同堆尾元素交换，将堆的长度-1，然后对堆顶调用 sink 方法（即让堆重新有序），这样就达到了把堆顶元素置于正确位置的目的。（这过程就像选择排序，每次找到一个最大/小的元素，移到数组尾端。但是堆排序所需的比较更少，因为相比与选择排序，堆能够以常数时间找到最大/小的元素，并且在之后只需要 logn 次比较来让数组重新堆有序）
3. 重复步骤二，直到堆的长度为 1。
4. 下面给出的实现中只排序了 arr[1:]，所以最终需要把 arr[0] 插入到其后的已排序数组中。或许将堆的编号从零开始计算会省去这一步？有点麻烦。这里也可以对 exch 和 sink 方法进行修改，将其接受的索引都减 1。

这里为什么是从 N/2 开始？因为通过数学方法可以证明，N/2 是从后往前数第一个有左右子节点的节点。

首先需要明确 N/2 的数学意义是随 N 的奇偶而变的，如果 N 为偶数，则 N/2 则为数学意义上的 N/2，如果 N 为奇数，则 N/2 则要理解成 Math.floor(N / 2.0)，其将向下取整（实际上是进行了带余数的除法，余数被舍弃了），这时候 (N - 1) / 2 才等价于数学意义上的 N/2。

当 N 为偶数的时候，N/2 节点的左子结点为 N / 2 * 2 = N，为堆中最后一个节点，当 N 为奇数的时候，N/2 等价于 (N - 1) / 2，其右子节点为 (N - 1) / 2 * 2 + 1 = N，为堆中最后一个节点。

因此，堆中最后一个节点必然是 N/2 的子节点，所以 N/2 必然是最后一个有左右节点的节点（N/2 有最后一个子节点，则 N/2 + 1 必然没有子节点）

private static <T> void heapSort(Comparable<T>[]arr) {
    int N = arr.length - 1;
    for (int i = N/2;i>=1;i--)
        sink(arr,i,N); // 构建堆
    
    while (N > 1) {
        exch(arr,1,N); // 每次将堆顶和堆尾交换
        sink(arr,1,--N); // 将 N-1，然后对堆顶进行 sink 操作
    }
}
public static <T> void sort(Comparable<T>[] arr) {
    if (arr==null||arr.length<=1) return;
    heapSort(arr); // 堆排序
    for (int i = 1; i < arr.length;i++) // 这里只排序了 arr[1:]，因此需要对 arr[0] 插入到后面的数组中
        if (less(arr[i-1],arr[i])) // 这里的 less 的含义是 arr[i-1]>arr[i]
            exch(arr,i-1,i);
    	else return;
}