这篇文章主要记录几种排序方式，描述他们的排序过程，复杂度，代码实现，使用比较。

主要包括以下几种：

• 冒泡排序
• 插入排序
• 选择排序
• 归并排序
• 快速排序
• 桶排序
• 基数排序
• 计数排序

我们首先来了解一个概念：稳定性。

假如我们有以下几个数：(3,3,2,1)。我们把第一个3称为3a,第二个称为3b。经过排序后结果是(1,2,3a,3b)，即保持了相同大小元素的先后顺序，则把这种排序算法称为稳定的排序算法。

首先记录一下几种最开始学习的排序方式，这几种的复杂度都是o(n²)。

冒泡排序

这个应该是最开始学习的一种排序方法之一，从头开始比较两个相邻的元素，如果前面的元素比后面的大则互换位置，经过一次排序，最大的元素就到了数组的最后位置。然后我们比较从头到倒数第二个的位置，就这样一直到比较完毕。每一次排序都将剩余数组中的最大值移动到了数组的尾部。

代码实现如下：

public void bubbleSort(int[] a) {
  int n = a.length;
  //入参判断
  if (n <= 1) {
    return;
  }
  for (int i = 0; i < n; i++) {
    //经过一次排序后，只剩下 n-i个未排序，下标再减一
    for (int j = 0; j < n -i- 1; j++) {
      if (a[j] > a[j + 1]) {
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }
  }
}

其实这个代码还有一些优化的地方，当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后面的冒泡操作了。比如下面的这个例子，它在执行到中间过程就依然有序了，不需要继续向下执行。

我们来进行优化一下代码：

public void bubbleSortBetter(int[] a) {
  int n = a.length;
  if (n <= 1) {
    return;
  }
  for (int i = 0; i < n; i++) {
    boolean flag = true;
    for (int j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
        // 表示有数据交换
        flag = true;
      }
    }
    if (!flag) {
      //没有数据交换时，提前退出
      break;
    }
  }
}

在这里面添加了一个标识，如果在一次冒泡中没有交换就退出。

复杂度分析：

• 空间复杂度：

  由于未用到额外空间，所以冒泡排序的空间复杂度是o(1)

• 时间复杂度：

  我们要看几种情况

最好情况：也就是数组已经是排好序的，这时需要一次冒泡，时间复杂度为o(n)。

最坏情况：当数组是逆序的，这时的时间复杂度为o(n²)。

而在平均情况下它的时间复杂度也是o(n²)。

• 稳定性

  我们在进行比较的时候只有当第一个元素比第二个元素小时才会交换，相等时不会交换，所以可以保证冒泡排序是稳定的排序算法

插入排序

假设这么一个场景，我们有一个已经排好序的数组，现在要插入一个新元素并仍然保持有序，要怎么做呢？

很简单，我们只有遍历数组，找到数据应该插入的位置将其插入即可。

那么我们按照这个方法，将数组分为两个区间，已排序区间和未排序区间。第一次将第一个元素作为数组也就是已排序区间，将第二个元素插入到已排序数组中。一次插入后，再将第三个元素插入到已经排好序的前两个元素构成的有序数组中。依次进行直到没有数据。

代码实现如下：

public void insertionSort(int[] a) {
  int n = a.length;
  //入参判断
  if (n <= 1) {
    return;
  }
  //从第二个开始插入到已排序数组中，（前面i个为已排序数组）
  for (int i = 1; i < n; i++) {
    int value = a[i];
    int j = i - 1;
    //查找插入的位置
    //从后向前查找要插入的位置，最坏情况是需要移动已排序数组的长度
    //因为如果从前开始也要先找到位置，然后从这个位置开始向后挪，移动的次数固定为已排序数组的长度。
    for (; j >= 0; j--) {
      if (a[j] > value) {
        a[j + 1] = a[j];
      } else {
        break;
      }
    }
    //进行插入
    a[j + 1] = value;
  }
}

第一层循环是从第二个元素开始插入到已排序数组中，第二层循环是找到要插入元素的位置，并且是从后向前查找。

复杂度分析

• 空间复杂度

  没有使用到额外的存储空间，所以空间复杂度是o(1)

• 稳定性

  在第二层循环中寻找插入位置时，当元素相同时不再进行查找，所以可以保持相同值原有的前后顺序不变。所以插入排序是稳定的排序算法。

• 时间复杂度

最好情况：原数组依然有序，我们第二层循环执行一次就会退出，第一层仍然需要全部执行，所以时间复杂度为o(n)。

最坏情况：原数组为逆序，我们这时要走满两层循环，即时间复杂度为o(n²)。

而在平均情况下它的时间复杂度也是o(n²)。

优化

插入排序是这三种中最常用的一个算法，因为他的时间复杂度与初始状态有关。

插入排序有一些优化的算法，比如希尔排序。希尔排序的思想是使数组中任意间隔为h的元素都是有序的。希尔排序比插入排序和选择排序快得多，并且数组越大，优势越大

代码：

public static void shellSort(int[] a) {
  int n = a.length;
  int h = 1;
  //增量计算
  while (h < n / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    //对一个组的元素进行排序
    for (int i = h; i < n; i++) {
      for (int j = i; j >= h; j -= h) {
        if (a[j] < a[j - h]) {
          int temp = a[j - h];
          a[j - h] = a[j];
          a[j] = temp;
        }
      }
    }
    //增量递减，逐渐缩小数组
    h = h / 3;
  }
}

空间复杂度为o(1)，不是稳定的排序算法，并且他的时间复杂度也与增量有关。

选择排序

选择排序与插入排序有点类似，也分为已排序区间和未排序区间，但是它是每次从未排序区间找到最小的元素，将其放到已排序区间的末尾。

代码实现：

public void selectionSort(int[] a) {
  int n = a.length;
  for (int i = 0; i < n; i++) {
    int minIndex = i;
    //找到未排序数组中最小的元素
    for (int j = i + 1; j < n; j++) {
      if (a[j] < a[minIndex]) {
        minIndex = j;
      }
    }
    //将找到的元素与已排序数组的尾部进行交换。
    int temp = a[minIndex];
    a[minIndex] = a[i];
    a[i] = temp;
  }
}

复杂度分析

• 稳定性

  选择排序不是稳定的排序算法

  我们以下面这个例子说明：6(a),5,6(b),4,2,3。

  在第一次循环中，它会将2与6(a)进行交换位置，这时6(b)就在6(a)前了。在后面的排序中，它俩的顺序也不会改变，所以选择排序不是稳定的排序算法。

• 空间复杂度

  没有额外的存储空间，所以选择排序的空间复杂度为o(1)

• 时间复杂度

  即便是已经排好序的数组，在选择排序中它仍然要执行两层循环，即它的时间复杂度为o(n²),在逆序的情况下也是o(n²)

  所以选择排序的时间复杂度固定为o(n²)。

归并排序

归并排序使用了分治思想，将数组进行划分成小数组，然后将小数组进行排序，再将小数组进行合并，合并时再进行排序一次。

它的过程我用动画表示一下：

主要过程包括拆分，合并。两个主要过程，

代码实现：

public void mergeSort(int[] a) {
  if (a == null) {
    return;
  }
  mergeSortHelp(a, 0, a.length - 1);
}

private void mergeSortHelp(int[] a, int start, int end) {
  if (start >= end) {
    return;
  }
  int mid = (start + end) / 2;
  mergeSortHelp(a, start, mid);
  mergeSortHelp(a, mid + 1, end);
  mergeHelp(a, start, mid, end);
}
//合并
private void mergeHelp(int[] a, int left, int mid, int right) {
  //初始化一个排序长度的数组
  int[] temp = new int[right - left + 1];
  int i = left, j = mid + 1, k = 0;
  //将{left-mid},{mid-right}两个数组按照顺序放到temp中
  while (i <= mid && j <= right) {
    if (a[i] <= a[j]) {
      temp[k++] = a[i++];
    } else {
      temp[k++] = a[j++];
    }
  }
  //将左边剩余元素填充到temp中
  while (i <= mid) {
    temp[k++] = a[i++];
  }
  //将右边剩余元素填充到temp中
  while (j <= right) {
    temp[k++] = a[j++];
  }
  //将temp中的元素全部拷贝到原数组中对应位置
  System.arraycopy(temp, 0, a, left, k);
}

复杂度分析

• 稳定性

  在合并函数中进行合并比较时，上面代码的第23行的判断中，当两种相等时，先将左侧的元素放入临时数组中，这时就保证了先后顺序。

  所以，归并排序是一个稳定的排序算法。

• 空间复杂度

  我们可以看出，每次合并都需要创建临时数组，所以归并排序的空间复杂度为o(n)

• 时间复杂度

  归并排序的效率与初始状态无关，并且是非常稳定的，它的时间复杂度是o(nlogn)。

快速排序

快速排序也是利用的分治思想。

它是先在数组中找到一个元素(随便找一个，一般是数组最后一个元素)，作为分区点(pivot)。然后将小于分区点元素的放到左边，大于分区的元素的放到右边，将分区点放到两者之间。那么就这个数组就变成了三部分，比分区点元素小的一个数组，比分区点元素大的一个数组，还有一个分区点。

然后再分别将两个数组进行拆分，最后整个数组就有序了。

分区的过程可以用下面这张图展示：

代码实现：

public void quickSort(int[] a) {
  int n = a.length;
  quickSortHelp(a, 0, n - 1);
}

private void quickSortHelp(int[] a, int start, int end) {
  //递归函数边界退出条件
  if (start >= end) {
    return;
  }
  int p = partition(a, start, end);
  quickSortHelp(a, start, p - 1);
  quickSortHelp(a, p + 1, end);
}

private int partition(int[] a, int left, int right) {
  //设置分区点为数组最后一个元素
  int pivot = a[right];
  //开始分区
  int i = left;
  for (int j = left; j < right - 1; j++) {
    if (a[j] < pivot) {
      //如果元素比分区点小，则将元素从左侧开始放，将原来左侧的数据换到现在这个位置上
      //i表示左侧的位置，交换后就加一
      swap(a, i, j);
      i++;
    }
  }
  //最后将分区点放到对应位置上
  //交换后，i左侧为比分区点小的元素，右侧为比分区点大的元素
  swap(a, i, right);
  return i;
}

private void swap(int[] a, int first, int second) {
  int temp = a[first];
  a[first] = a[second];
  a[second] = temp;
}

复杂度分析

• 稳定性：

  在选取分区点过程中会把后面的元素放到分区点上，这时会破坏先后顺序。所以快速排序不是一个稳定的排序算法

• 空间复杂度

  没有用到额外的空间，所以空间复杂度为o(1)

• 时间复杂度

  快速排序的时间复杂度是o(nlogn)

与归并排序区别

快速排序与归并排序都是利用分治的思想，它们两个有什么区别呢？

我们仔细看一下流程图，可以看出，归并排序是直接分到最小单位，然后再进行合并，最终完成，处理过程主要是merge方法，是由下向上的。

快速排序是主要过程是partition函数，它先将大数组找出分区点，然后再进行递归，所以它的过程是由上向下的。

还有一个问题就是空间复杂度，快速排序可以实现o(1)的空间复杂度，而归并排序的空间复杂度为o(n)

练习

在o(n)的时间复杂度内求无序数组中的第k大元素

利用快速排序方法，进行分区，得到分区点provit的下标p，然后用k和p进行比较，如果k=p+1，那么a[p]就答案。如果k>p+1，则继续在a[p+1,n-1]这个区间找，如果k< p+1则在a[0,p-1]的区间继续查找。

桶排序

下面要记录的几个就是时间复杂度为o(n)的排序算法，也可以成为线性排序。这几个能做到线性的时间复杂度，主要原因是，他们是基于非比较的排序算法，不涉及元素直接的比较操作。

桶排序，顾名思义会用到'桶'，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序后，再把每个桶里的数据按照顺序依次取出，组成有序序列。

桶排序的时间复杂度为什么是o(n)？

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个 桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因 为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

那么既然有了o(n)的桶排序是不是就可以替换之前的排序算法了呢？

答案是否定的，肯定有有一些弊端的，否则其他算法肯定是会被淘汰的，桶排序有有一些局限性。

我们举一个例子，现在有一个数组，取值范围为0 ~ 100，我们是不是就要分成100个桶，但是我的数据里面并不是均匀分布的，我里面有10个0 ~10的，其余的全部都是99 ~ 100的。这时我们大部分数据都在一个桶里面，这个算法的弊端就体现出来了。而且我们还需要这些桶直接有着天然的大小顺序，这样才能在每个桶排序完成后，桶与桶直接不再需要合并排序。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

基数排序

假设我们需要对电话号码进行从小到大的排序。用之前的快排，时间复杂度可以做到o(nlogn)。可不可以用桶排序呢实现o(n)的复杂度呢？因为手机号有11位，范围太大，我们需要创建10¹¹个桶。当然可以继续优化，但是数量级仍然还是很高。所以这时候就需要一种新的排序方法，基数排序。

我们在比较电话号码时，在前面几位中，如果a号码已经比b号码大了，那么后面就不用看了。这里需要借助稳定排序算法，不然在第二次排序中会打乱一次排序的先后顺序，那就没有意义了。

用一个字符串排序的例子来代替手机号的例子：

根据每一位来排序，我们可以用桶排序，他的时间复杂度可以做到o(n)。如果要排序的数据有k位，比如手机号有11位，那么我们就需要k次桶排序。总的时间复杂度就是o(kn)。所以基数排序的时间复杂度就近似于o(n)*

实际操作中，有时候数据并不是等长的，就拿英文单词来说，长度不统一。对于这种情况，我们可以采用补齐的方式，找到最长的位数，然后对其它位数不够的可以在前面或后面补'0'。这样就可以继续用基数排序了。

基数排序对要排序是数据也是有要求的，需要可以分割出独立的"位"来比较，并且位之间有递进的关系。如果a数据的高位比b数据大，那么剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则基数排序的时间复杂度也无法做到o(n).

计数排序

计数排序也是一种o(n)的线性排序，我还没有完全理解他的过程，后序会对这一部分做补充。

总结

按照复杂度分为可以分为三类：

o(n²)：冒泡排序，插入排序，选择排序

o(nlongn)：快速排序，归并排序

o(n)：桶排序，基数排序，计数排序

时间复杂度为o(n)的排序算法对于数据有要求，所以在未知情况下可以使用快速排序，不使用归并排序的原因是归并排序需要额外的空间。

而且后面的桶排序，基数排序也都是基于其他的排序算法来进行的，就拿桶排序来说，他桶内排序依赖快速排序，所以能做到近似o(n)，如果使用冒泡也能达到o(n)。后面的这几个线性排序是一种更高层级的思想。

参考

• 数据结构与算法之美

所用图片大部分来自王铮的算法专栏，也有从网上找的一个动图，如有冒犯，联系我更改。

本文由博客一文多发平台 OpenWrite 发布！
博主邮箱：liunaijie1996@163.com，有问题可以邮箱交流。