常见排序算法

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

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

欢迎访问我的个人博客Coder，有更优质的阅读体验，记得收藏哦。

准备工作

为了对实现的算法进行测试，我们准备一个工具类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(NlogN)的速度还要快。

希尔排序

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

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

上面的示例中，我们从每隔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(NlogN)级别的算法，比选择排序和插入排序要快很多。

优化

上面我们在对左右两个数组排好序之后，直接进行了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