常见排序算法

由于近期在学习排序算法，决定将自己的学习过程记录下来，一是为了自己能够方便的复习，另一个是将这个知识分享给大家。我将使用 Java 语言实现下列排序算法

• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序

准备工作

为了对实现的算法进行测试，我们准备一个工具类 Helper，里面包括我们由于测试算法正确与否的方法以及性能测试的代码，包括交换数组中的两个元素(这个操作在排序时经常用到，所以抽象出一个方法)，还有产生一个指定容量和范围的随机数组，还有判断数组是否有序的函数以及性能测试的函数

import java.util.Arrays;
import java.util.Random;

public class Helper {
    
    //交换arr[i]和arr[j]
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    //产生一个范围在rangeL-rangeR，容量为n的数组
    public static int[] generateArray(int n, int rangeL, int rangeR) {
        Random random = new Random();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = random.nextInt(rangeR - rangeL + 1) + rangeL;
        }

        return arr;
    }
    
    //判断数组是否有序(从小到大)
    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
    
    //测试排序需要的时间 需要传入一个函数接口Sort
    public static double testTime(int[] arr, Sort sort) {
        long startTime = System.nanoTime();
        sort.sort(arr);
        long endTime = System.nanoTime();
        
        return (endTime - startTime) / 1000000000.0;
    }
}

其中 testTime 需要传入一个函数式接口 Sort，该接口定义如下

public interface Sort {
    public void sort(int[] arr);
}

我们在调用该方法时，只要将我们的排序算法的方法引用传入即可。

选择排序

为了描述的精确性，我们把数组分为两部分，一部分是已经排好序的区域，一部分是未排序的区域

选择排序的策略就是在未排序的区域找出最小元素的位置，然后将它交换到未排序区域的最前方，然后已排序区域向前扩大一位，然后接着上面策略，直至未排序的区域为空，排序结束。下面以一个例子进行说明，我们默认蓝色区域代表已排序区域，白色区域代表未排序区域

代码如下

public class SelectionSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            Helper.swap(arr,minIndex,i);
            minIndex = i + 1;
        }
    }

    public static void main(String[] args) {
        //对100000个数进行排序
        int n = 100000;
        //产生随机数组
        int[] arr = Helper.generateArray(n, 0, n);
        //传入排序算法的引用，得到排序所需时间
        double time = Helper.testTime(arr,SelectionSort::sort);
        //确定算法是否排好序
        System.out.println("isSorted: " + Helper.isSorted(arr));
        //打印排序所需时间
        System.out.println(time + "s");
    }
}

输出为

isSorted: true
7.319637673s

可见算法已经排好序，并且选择排序对 100000 个数据排序所需的时间为 7.32s 左右。

插入排序

插入排序就像是你在打斗地主，当你摸牌时你对牌的排序。向上面一样，我们将数组分为已排序的部分和未排序的部分，以排序的部分就是你已经排好序的牌，现在你又摸到了一张牌，那么你是不是会将这张牌与排好序的牌进行比较，插入到合适的位置，然后继续摸下一张牌，然后又进行插入排序，直到牌已经摸完了(未排序的部分为空)，那么你就已经拍好序了，下面看一个例子

代码为

public class InsertSort {

    public static void sort(int[] arr) {
        //i = 1开始，因为默认第一张牌是排好序的
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                //如果后面比前面小，进行交换
                if (arr[j - 1] > arr[j]) {
                    Helper.swap(arr,j - 1, j);
                } else {
                    //如果后面比前面大，结束交换
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 100000;
        int[] arr = Helper.generateArray(n, 0, n);
        double time = Helper.testTime(arr,InsertSort::sort);
        System.out.println("isSorted: " + Helper.isSorted(arr));
        System.out.println(time + "s");
    }
}

输出为

isSorted: true
8.863959818s

这表明插入排序对 100000 个数据排序所需的时间为 8.86s 左右。它的速度比选择排序还要慢一些，这时因为插入排序中含有大量的交换操作，如果我们将上面的交换操作替换为赋值操作

public static void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int e = arr[i]; //保存要插入的元素
        int j; //记录要插入的位置
        for (j = i; j > 0; j--) {
            if (arr[j - 1] > e) {
                //向后移动
                arr[j] = arr[j - 1];
            } else {
                break;
            }
        }
        arr[j] = e;
    }
}

这时需要的时间为

isSorted: true
2.293106947s

并且对于近乎有序的数组，插入排序的速度非常的快，甚至比后面要介绍的 $O(N \log N)$ 的速度还要快。

希尔排序

希尔排序是对插入排序的改进。既然是改进，那么我们就要知道插入排序有什么问题：如果有一个很小的数在数组的后方，那么这个数就会进行很长时间的交换才能插入到合适的位置，这明显是一个比较慢的过程

而希尔排序将解决这一个问题，希尔排序首先将数组分组，比如

上面的示例中，我们从每隔 3 个一组到每隔 2 个一组最后每隔 1 个一组，我们把上面的 "3,2,1" 称之为增幅序列 h，不同的递增序列对算法的性能也有影响，有很多的论文研究了不同的递增序列，但都无法证明某个递增序列是最好的，下面的程序考虑使用 "1, 4, 13, ..." 这个递增序列(h = 1, h = 3 \* h + 1)，代码如下

public class ShellSort {

    public static void sort(int[] arr) {
        int N = arr.length;
        int h = 1;
        while (h < N / 3) {
            h = 3*h + 1; // 1 4 13 40 121 ...
        }

        // h = 1的时候就是对整个数组进行插入排序
        while (h >= 1) {
            //每隔h个元素(将数组分成了h组)进行插入排序
            for (int i = h; i < N; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arr[j - h] > arr[j]) {
                        Helper.swap(arr, j, j-h);
                    } else {
                        break;
                    }
                }
            }
            h = h/3;
        }
    }

    public static void main(String[] args) {
        int n = 100000;
        int m = 10;
        double time = 0;
        for (int i = 0; i < m; i++) {
            int[] arr = Helper.generateArray(n, 0, n);
            time += Helper.testTime(arr, ShellSort::sort);
            System.out.println("isSorted: " + Helper.isSorted(arr));
        }
        time = time / m;
        System.out.println(time + "s");
    }

}

输出为

isSorted: true
0.0292856418s

希尔排序 10 次平均所需的时间只有 0.03s，与选择排序和插入排序不是一个等级上的。

归并排序

自顶向下的归并排序

归并排序的思想是将数组一分为二，然后对左、右两边的数组进行排序，然后将左右两边的已经有序数组进行融合成一个有序的数组，而左右两边的排序问题也可以按照上面的思想进行，直到数组只剩下一个元素，我们认为已经是有序的了，然后向上进行融合

下面的代码简要的简述了上面的过程

import java.util.Arrays;

public class MergeSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return ;
        }

        mergeSort(arr,0, arr.length-1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        //如果只有一个元素，可认为是有序的了
        if (left == right) {
            return ;
        }
		
        int mid = left + (right - left) / 2;
        //对左右两边进行排序
        mergeSort(arr,left,mid);
        mergeSort(arr,mid + 1, right);
		
        //融合左右两边的数组
        merge(arr,left,right);
    }
}

现在的关键是如何融合左右两个有序的数组为一个有序的数组，来看下面这个例子

private static void merge(int[] arr, int left, int right) {
    //要融合的数组
    int[] help = new int[right - left + 1];
    int mid = left + (right - left) / 2;
    //左右数组的首部
    int p1 = left;
    int p2 = mid + 1;
    //要融合数组的首部
    int i = 0;
    //如果两个数组都没有遍历完毕
    while (p1 <= mid && p2 <= right) {
        if (arr[p1] <= arr[p2]) {
            help[i++] = arr[p1++];
        } else {
            help[i++] = arr[p2++];
        }
    }
    //如果p2遍历完毕了，将p1中剩下的元素复制到融合的数组中
    while (p1 <= mid) {
        help[i++] = arr[p1++];
    }
    //同上
    while (p2 <= right) {
        help[i++] = arr[p2++];
    }
    //将融合的数组按序赋值给我们要排序的数组
    for (int j = left; j <= right; j++) {
        arr[j] = help[j - left];
    }
}

我们来测试一下 10 次平均所需时间为

isSorted: true
0.0334043239s

归并排序是 $O(N \log N)$ 级别的算法，比选择排序和插入排序要快很多。

优化

上面我们在对左右两个数组排好序之后，直接进行了 merge 操作

mergeSort(arr,left,mid);
mergeSort(arr,mid + 1, right);
merge(arr,left,right);

但是如果考虑到如下情况

mergeSort(arr,left,mid);
mergeSort(arr,mid + 1, right);
if (arr[mid] > arr[mid + 1])
    merge(arr,left,right);

我们还可以进行优化，在上面我们提到，插入排序在数组近乎有序的情况下排序的速度非常的快，所以我们可以考虑当数组被划分到小于一定的规模(当数组小于一定规模时，近乎有序的概率很大)时我们不在向下划分，而是转而用插入排序，所以我们在 Helper 中添加一个方法

public static void insertSort(int[] arr, int l, int r) {
    for (int i = l + 1; i <= r; i++) {
        int e = arr[i]; //保存要插入的元素
        int j; //记录要插入的位置
        for (j = i; j > l; j--) {
            if (arr[j - 1] > e) {
                arr[j] = arr[j - 1];
            } else {
                break;
            }
        }
        arr[j] = e;
    }
}

这个方法与插入排序的算法很相似，不过规定了对什么范围的数组进行排序，所以归并排序的算法可以修改如下

private static void mergeSort(int[] arr, int left, int right) {
    //当数组小于15时，使用插入排序
    if (right - left < 15) {
        Helper.insertSort(arr, left, right);
        return;
    }
    
    int mid = left + (right - left) / 2;
    mergeSort(arr,left,mid);
    mergeSort(arr,mid + 1, right);
    if (arr[mid] > arr[mid + 1])
        merge(arr,left,right);
}

再次测试 10 次平均所需时间

isSorted: true
0.028484280499999997s

自底向上的归并排序

我们在上面使用的归并排序是自顶向下使用递归来完成的，但是我们不一定要自顶向下的完成这个排序过程，而是可以自底向上进行排序，首先将底层的序拍好，然后进行 merge 一路向上完成排序

public static void sortBU(int[] arr) {
    if (arr == null || arr.length < 2) {
        return ;
    }
    //每轮2*sz个元素，为什么不直接sz = 2, 因为我们后面传入mid是要/2，所以这里的粒度就为sz
    for (int sz = 1; sz <= arr.length; sz += sz) {
        //mid <= arr.length - 1
        for (int i = 0; i + sz < arr.length; i += (sz + sz)) {
            //小数组使用插入排序
            if (2 * sz < 15) {
                Helper.insertSort(arr,i, i + sz + sz - 1);
                continue;
            }
            //只有当右边最小比左边最大还大时才需要merge
            if (arr[i + sz -1] > arr[Math.min(i + sz, arr.length - 1)]) //防止越界
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, arr.length - 1)); //防止越界
        }
    }
}
private static void merge(int[] arr, int left, int mid, int right) {
    int[] help = new int[right - left + 1];
    int p1 = left;
    int p2 = mid + 1;
    int i = 0;
    while (p1 <= mid && p2 <= right) {
        if (arr[p1] <= arr[p2]) {
            help[i++] = arr[p1++];
        } else {
            help[i++] = arr[p2++];
        }
    }
    while (p1 <= mid) {
        help[i++] = arr[p1++];
    }
    while (p2 <= right) {
        help[i++] = arr[p2++];
    }
    for (int j = left; j <= right; j++) {
        arr[j] = help[j - left];
    }
}

你可能发现这次的 merge 需要自己传入 mid 值，而不是自己计算。可以思考一下为什么? 现在我们测试一下自底向上排序所需要的时间

isSorted: true
0.031012182500000006s

自底向上的排序会比自顶向下的排序慢，但是自底向上的排序有一个非常重要的特点，它没有利用数组随机访问的特点，即数组通过下标对元素访问(插入排序中有，但是你可以不优化这里)，这意味着我们可以对链表使用自底向上的排序。

快速排序

基本算法

在看快速排序算法前我们先来看一个问题，给定一个数，要求数组左边的数都小于等于这个数，数组右边的数都大于这个数，请问这个算法怎么写。首先我们将数组标记为小于等于区和大于区，并用 less 和 more 标记区域的范围，所有 index <= less 的元素都小于指定数，所有 index >= more 的都大于指定数，下图将讲解具体的算法

上面的过程我们称为 partition，对应的代码如下

int e = 6;
public static int partition(int[] arr, int L, int R) {
    int less = L - 1;
    int more = R + 1;
    int cur = L;
    while (cur < more) {
        if (arr[cur] <= e) {
            //如果当前元素小于指定元素 less和cur向前移动
            less++;
            cur++;
        } else if (arr[cur] > e) {
            Helper.swap(arr,--more,cur);
        } else {
            cur++;
        }
    }
    //返回两个数组的分界处
    return less;
}

那么快速排序的思想就是选定一个数(一般我们选择要排序范围内的最后一个数 arr[R])，要求左边的数比这个数小(或等于)，右边的数比这个数大。然后又接着对左右两边的数进行上述的分割(partition)，直至分割后的数组只剩下一个元素，可认为是有序的，这时数组就是有序的了

public class QuickSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        quickSort(arr,0,arr.length-1);
    }

    public static void quickSort(int[] arr, int l, int r) {
        //当数组较小时，使用插入排序
        if (r - l < 15) {
            Helper.insertSort(arr, l, r);
            return;
        }
        
        if (l < r) {
            int p = partition(arr, l, r);
            quickSort(arr, l, p);
            quickSort(arr, p + 1, r);
        }
    }

    public static int partition(int[] arr, int L, int R) {
        int less = L - 1;
        int more = R + 1;

        int cur = L;
        while (cur < more) {
            if (arr[cur] <= arr[R]) {
                less++;
                cur++;
            } else if (arr[cur] > arr[R]) {
                Helper.swap(arr,--more,cur);
            }
        }
        
        return less;
    }
}

测试此时 10 次平均所需的时间

isSorted: true
0.023240137399999996s

随机快排

但是此时有一个问题，如果此时数组是近乎有序的，那么我们根据最后一个元素划分元素会划分出左右两边的数组失衡

所以我们不能选择最后一个元素，而是选择一个随机的元素，我们只要在上面的程序中加入下面的一行代码即可

if (l < r) {
    //随机一个下标和最后一个元素交换
    Helper.swap(arr, (int)Math.random() * (r - l + 1) + l, r); // 随机快排
    int p = partition(arr, l, r);
    quickSort(arr, l, p);
    quickSort(arr, p + 1, r);
}

三路快排

这时需要考虑这么一种情况，如果数组中有十分多的重复元素，那么就会有元素重复的子数组，这时应该就不应该排序了，但是我们的算法还是会把数组继续切分为更小的数组进行排序，这就有很大的改进潜力。所以我们考虑我们的 partition 算法不再划分为两部分，而是划分为三部分，小于，等于和大于三个区域

所以我们修改上面的排序算法如下

public static void quickSort(int[] arr, int l, int r) {
    if (r - l < 15) {
        Helper.insertSort(arr, l, r);
        return;
    }
    if (l < r) {
        Helper.swap(arr, (int)Math.random() * (r - l + 1) + l, r); // 随机快排
        //p得到的是等于区的范围
        int[] p = partition(arr,l,r);
        //对等于区不用排序
        quickSort(arr,l,p[0] - 1);
        quickSort(arr,p[1] + 1, r);
    }
}
public static int[] partition(int[] arr, int L, int R) {
    int less = L - 1;
    int more = R;
    int cur = L;
    while (cur < more) {
        if (arr[cur] < arr[R]) {
            //与less的前一个元素进行交换 并且less和cur向前移动
            Helper.swap(arr,++less,cur++);
        } else if (arr[cur] > arr[R]) {
            //与more的后一个元素进行交换 并且more向后移动，并且cur和less都不移动
            Helper.swap(arr,--more,cur);
        } else {
            //如果等于，将cur向前移动即可
            cur++;
        }
    }
    
    //最后将最后一个元素与more位置的元素进行交换
    Helper.swap(arr,R,more);
    //返回等于区的左右下标
    return new int[]{less+1,more};
}

堆排序

堆的有关知识可以参考数据结构–Java描述中优先队列与堆的内容，如果你已经仔细的阅读了话，相比你已经熟悉了堆的性质了，那么下面就直接上代码了

import java.util.Arrays;

public class HeapSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        //将数组变成堆结构
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }

        int heapSize = arr.length;
        while (heapSize > 0) {
            Helper.swap(arr,0,--heapSize);
            heapify(arr,0,heapSize);
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index-1)/2]) {
            Helper.swap(arr,index,(index-1)/2);
            index = (index - 1)/2;
        }

    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = 2 * index + 1;

        while (left < heapSize) {
            int right = left + 1;
            //假设左更大
            int larger = left;
            //如果右比左大 改变larger为右
            if (right < heapSize && arr[right] > arr[left]) {
                larger = right;
            }

            //如果父比左右子节点都大，说明还是堆，直接退出循环
            if (arr[larger] < arr[index]) {
                break;
            }

            //如果不是，那么就和比较大的交换交换
            Helper.swap(arr,larger,index);
            index = larger;
            left = index * 2 + 1;
        }
    }

    public static void main(String[] args) {
        int n = 100000;
        int m = 10;
        double time = 0;
        for (int i = 0; i < m; i++) {
            int[] arr = Helper.generateArray(n, 0, n);
            time += Helper.testTime(arr, HeapSort::sort);
            System.out.println("isSorted: " + Helper.isSorted(arr));
        }
        time = time / m;
        System.out.println(time + "s");
    }
}

测试 10 次平均所需时间为

isSorted: true
0.060118443099999995s