面试常用排序算法总结

前言

面试的死亡高发区是什么?手写快排.

其他的排序算法也经常会问到,虽然在工作中,我们很少有需要自己手写排序算法的机会,但是这种入门级的算法却是证明我们能力的一种简单方法.因此要熟悉掌握.

这篇文章,详细记录常用的一些排序算法,留以备忘.

本文所有代码可在github上下载查看.传送门

为了方便自己写,在测试过程中,使用了策略模式,感兴趣的童鞋可以移步设计模式之-策略模式

常用算法总结

图片来自:http://www.cnblogs.com/guoyaohua/p/8600214.html,
实在是懒得自己画一遍了.

本文测试使用数据

代码测试排序数据:[26,13,3,5,27,36,42,2,4,44,34,25,59,58]
文内举例测试数据:[5,2,4,3,1]

排序顺序为升序,即小数在前.

冒泡排序（Bubble Sort）

介绍(摘自百度百科):

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法描述

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

实现代码

public int[] sort(int[] input) {
  for (int i = 0; i < input.length - 1; i++) {
    for (int j = 0; j < input.length - i - 1; j++) {
      if (input[j] > input[j + 1]) {
        exchange(input, j, j + 1);
      }
    }
  }
  return input;
}

分析

最佳情况：T(n) = O(n)

最差情况：T(n) = O(n2)

平均情况：T(n) = O(n2)

稳定性

冒泡排序是相邻两个交换,当相等的时候不会交换,因此可以保证稳定性.

学习心得

冒泡排序通过,相邻元素的交换,可以每次将最大的元素移到数组末尾.

两层循环,第一层循环控制已经排序了多少位,即末尾有多少个排序好的较大值.

第二层循环控制从0开始,逐次比较当前位置与下一位置,拿到当前最大值,知道放在已经排序好的较大值序列前.

选择排序（Selection Sort）

介绍

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

算法描述

1. 遍历一遍数组(0-n),拿到最小的值,放在第一位.
2. 遍历一遍数组(1-n),拿到最小值,放在第二位.
3. 知道排序完成.

实现代码

public int[] sort(int[] input) {

  int minIndex = 0;
  for (int i = 0; i < input.length; i++) {
    minIndex = i; // 将当前位置作为最小值得下标
    for (int j = i; j < input.length; j++) {
      if (input[minIndex] > input[j]) {
        //如果发现比最小下标的值还小的位置,替换最小下标
        minIndex = j;
      }
    }
    //将当前位置和最小下标位置的值交换
    exchange(input, minIndex, i);
  }
  return input;
}

分析

选择排序表现十分稳定了可以说,不管输入是逆序还是正序,他都需要对每一个进行逐次比较,稳定的O(n2).

最佳情况：T(n) = O(n2)

最差情况：T(n) = O(n2)

平均情况：T(n) = O(n2)

稳定性

选择排序不稳定

举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

学习心得

选择排序其实可以理解为:用一个额外空间,一直记录着当前最小的元素,第一遍结束后,该位置就是最小的,将第一个位置和该位置交换.

选择排序的两层循环,第一层循环控制当前序列的前多少位已经有序.

第二层循环控制从已经有序的下一位开始到结束,找到最小的

插入排序（Insertion Sort）

介绍

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

算法描述

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

实现代码

public int[] sort(int[] input) {
  for (int i = 1; i < input.length; i++) {
    int j = i - 1;
    //拿到当前待插入的值
    int current = input[i];
    //从当前位置向前遍历,逐一比较
    while (j >= 0) {
      //如果当前值大于该位置的值
      if (current > input[j]) {
        //在该位置之后放入当前值,跳出循环
        input[j + 1] = current;
        break;
      } else {
        //将该位置的值后移一位
        input[j + 1] = input[j];
      }
      if (j == 0){
        //如果该位置为0,且大于当前值,则将当前值放在第一位
        input[j] = current;
      }
      j--;
    }

  }
  return input;
}

分析

最佳情况：T(n) = O(n)

最坏情况：T(n) = O(n2)

平均情况：T(n) = O(n2)

稳定性

由于是从后向前按照顺序插入的,因此可以保证稳定性.

举个例子，序列5 8 5 2 9，在第三步时,将5插入5,8的有序序列,会放在5之后,不会影响两个5的相对位置.

学习心得

插入排序也算是一种比较容易理解的排序方式.对一百个数字的排序可以先排第一个.然后将第二个放入到已有的序列中,再将第三个放进来.

这样的思路很好理解,代码实现也较为简单,但是如果待排序序列是个反序的,即最坏情况下,时间复杂度较高,只能用于少量数据的排序.

希尔排序 (Shell Sort)

介绍

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 [1]

算法描述

排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

实现代码

public int[] sort(int[] input) {

  //初始步长
  int d = input.length / 2;

  //当步长大于等于1,保证最后作为一个数组排序过
  while (d >= 1) {
    //对每一种步长,遍历所有(步长为5,遍历1到5,即可遍历所有)
    for (int i = 0; i < d; i++) {
      //插入排序,普通插入排序每次递增1,这里递增步长d
      for (int j = i + d; j < input.length; j += d) {
        int tmp = input[j];
        int p;
        for (p = j - d; p >= 0 && input[p] > tmp; p -= d) {
          input[p + d] = input[p];
        }
        input[p + d] = tmp;
      }
    }
    //步长减半
    d=d/2;
  }
  return input;
}

分析

最佳情况：T(n) = O(nlog2 n)

最坏情况：T(n) = O(nlog2 n)

平均情况：T(n) =O(nlog2n)　

稳定性

不稳定.

虽然插入排序是稳定的,但是在分组的时候,可能导致两个相同数字的相对顺序有改变.

学习心得

希尔排序就是一种优化后的插入排序,插入排序越到后面越麻烦,因为要移动的位置更多.

希尔排序可以在开始的时候,通过分组,将待排序序列的”大致”顺序变得好一些.这样在最后合并为一个分组时,可以减少很多次的移动.以此来提升效率.

第一次分组,两个元素为一组,此时对每一个组的插入排序来说都很简单,因此只有两个元素,但是对于序列的有序度提升非常大.

归并排序（Merge Sort）

介绍

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

实现代码

public int[] sort(int[] input) {
  //当长度小于2,返回
  if (input.length < 2) {
    return input;
  }
  //分隔成左右两部分
  int mid = input.length / 2;
  int[] left = Arrays.copyOfRange(input, 0, mid);
  int[] right = Arrays.copyOfRange(input, mid, input.length);

  //分别进行归并排序并merge结果
  return merge(sort(left), sort(right));

}

public int[] merge(int[] A, int[] B) {
  //定义新数组,长度等于两个数组织和
  int[] result = new int[A.length + B.length];
  //定义三个指针,指向两个输入数组和结果数组
  int i = 0, j = 0, h = 0;
  //当A,B都没有遍历完的时候
  while (i < A.length && j < B.length) {
    //取较小的一个加入结果数组,然后将该数组的指针后移,结果数组指针后移
    if (A[i] <= B[j]) {
      result[h] = A[i];
      i++;
    } else {
      result[h] = B[j];
      j++;
    }
    h++;
  }
  //分别遍历两个数组,将剩余数字加入结果数组中.
  //这里其实只会执行一个,因为从while循环中出来,必然有一个数组被遍历完了.
  for (; i < A.length; i++, h++) {
    result[h] = A[i];
  }
  for (; j < B.length; j++, h++) {
    result[h] = B[j];
  }
  //返回结果
  return result;
}

分析

最佳情况：T(n) = O(n)

最差情况：T(n) = O(nlogn)

平均情况：T(n) = O(nlogn)

稳定性

稳定.

在分隔的过程中,不会影响稳定性.合并的过程中,也不会影响.

学习心得

归并排序是分治思想的体现,先将带排序数组分隔成两半,然后分别进行归并排序.最后将这两部分合并起来.

其实相当于,将每个元素作为一个序列,不断的进行两个序列的合并过程,在合并的过程中,保持了有序.

快速排序（Quick Sort）

哈哈,这就是面试杀手,手写快排了!

介绍

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

实现代码

public int[] sort(int[] input) {
  quickSort(input, 0, input.length - 1);
  return input;
}

private void quickSort(int[] a, int start, int end) {
  if (start < end) {
    //如果不止一个元素，继续划分两边递归排序下去
    int partition = partition(a, start, end);
    quickSort(a, start, partition - 1);
    quickSort(a, partition + 1, end);
  }
}

public int partition(int[] a, int start, int end) {
  //以最左边的值为基准
  int base = a[start];
  //start一旦等于end，就说明左右两个指针合并到了同一位置，可以结束此轮循环。
  while (start < end) {
    while (start < end && a[end] >= base) {
      //从右边开始遍历，如果比基准值大，就继续向左走
      end--;
    }
    //上面的while循环结束时，就说明当前的a[end]的值比基准值小，应与基准值进行交换
    if (start < end) {
      //交换
      exchange(a, start, end);
      //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位
      start++;
    }
    while (start < end && a[start] <= base) {
      //从左边开始遍历，如果比基准值小，就继续向右走
      start++;
    }
    //上面的while循环结束时，就说明当前的a[start]的值比基准值大，应与基准值进行交换
    if (start < end) {
      //交换
      exchange(a, start, end);
      //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值右边)，因此右边也要同时向前移动一位
      end--;
    }
  }
  //这里返回start或者end皆可，此时的start和end都为基准值所在的位置
  return end;
}

分析

最佳情况：T(n) = O(nlogn)

最差情况：T(n) = O(n2)

平均情况：T(n) = O(nlogn)　

稳定性

不稳定.

27 23 27 3
以第一个27作为pivot中心点，则27与后面那个3交换，形成
3 23 27 27，排序经过一次结束，但最后那个27在排序之初先于初始位置3那个27，所以不稳定。

学习心得

快排真的是蛮麻烦的…

中心思想就是可以指定一个基准位,比它大的放右边,比它小的放左边,然后对左右分别进行快排.

这个放的过程,每次看都能理解,但是老是记不住..

快排有个问题,基准的选择对效率的影响很大,极限情况下你每次都选最大的,效率就很差了.可以通过随机选取基准的方法略微的规避一下这个问题.

堆排序（Heap Sort）

堆排序利用了堆这一数据结构,这里只写”堆排序”中关于”排序”的部分,对堆的详细解释在其他文章中进行.

介绍

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

1. 堆化数组.
2. 第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。
3. 第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆.
4. 重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。

实现代码

int len;


@Override
public int[] sort(int[] input) {

  len = input.length;
  if (len < 1) {
    return input;
  }
  //1.构建一个最大堆
  buildMaxHeap(input);
  //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
  while (len > 0) {
    exchange(input, 0, len - 1);
    len--;
    adjustHeap(input, 0);
  }
  return input;
}


/**
 * 建立最大堆
 */
private void buildMaxHeap(int[] array) {
  //从最后一个非叶子节点开始向上构造最大堆
  for (int i = (len / 2 - 1); i >= 0; i--) {
    adjustHeap(array, i);
  }
}

/**
 * 调整使之成为最大堆
 */
private void adjustHeap(int[] array, int i) {
  int maxIndex = i;
  //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
  if (i * 2 < len && array[i * 2] > array[maxIndex]) {
    maxIndex = i * 2;
  }
  //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
  if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) {
    maxIndex = i * 2 + 1;
  }
  //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
  if (maxIndex != i) {
    exchange(array, maxIndex, i);
    adjustHeap(array, maxIndex);
  }
}

分析

最佳情况：T(n) = O(nlogn)

最差情况：T(n) = O(nlogn)

平均情况：T(n) = O(nlogn)

稳定性

不稳定.

学习心得

堆排序的难点其实不在排序上,而在与堆上.]

1. 如何构造一个最大(最小堆)?

2. 移除堆顶元素后如何调整堆?

计数排序（Counting Sort）

介绍

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

实现代码

public int[] sort(int[] input) {
  if (input.length == 0) {
    return input;
  }
  //求出最大最小值
  int bias, min = input[0], max = input[0];
  for (int i = 1; i < input.length; i++) {
    if (input[i] > max) {
      max = input[i];
    }
    if (input[i] < min) {
      min = input[i];
    }
  }
  //最小值距离0的距离
  bias = 0 - min;
  //计数用的数组
  int[] bucket = new int[max - min + 1];
  Arrays.fill(bucket, 0);
  //计数
  for (int i = 0; i < input.length; i++) {
    bucket[input[i] + bias]++;
  }
  //
  int index = 0, i = 0;
  while (index < input.length) {
    if (bucket[i] != 0) {
      //下标数字存在,注意放入结果中
      input[index] = i - bias;
      bucket[i]--;
      index++;
    } else {
      //下标数字不存在,后移一位
      i++;
    }
  }
  return input;
}

分析

最佳情况：T(n) = O(n+k)

最差情况：T(n) = O(n+k)

平均情况：T(n) = O(n+k)

稳定性

稳定

学习心得

线性时间的排序方法,看起来真的很美好.但是限制太大了,主要有两点.

1. 必须是整数之间的排序

2. 待排序序列的范围不能太大,比如排序(1,2,3,4)就很好.如果排序(1,10000,10000000)就会占用太大的内存.

桶排序（Bucket Sort）

介绍

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

算法描述

1. 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
4. 从不是空的桶里把排好序的数据拼接起来。

实现代码

public int[] sort(int[] input) {
  //分桶，这里采用映射函数f(x)=x/10。
  //输入数据为0~99之间的数字
  int bucketCount =10;
  Integer[][] bucket = new Integer[bucketCount][input.length];  //Integer初始为null,以与数字0区别。
  for (int i=0; i<input.length; i++){
    int quotient = input[i]/10;   //这里即是使用f(x)
    for (int j=0; j<input.length; j++){
      if (bucket[quotient][j]==null){
        bucket[quotient][j]=input[i];
        break;
      }
    }
  }
  //小桶排序
  for (int i=0; i<bucket.length; i++){
    //insertion sort
    for (int j=1; j<bucket[i].length; ++j){
      if(bucket[i][j]==null){
        break;
      }
      int value = bucket[i][j];
      int position=j;
      while (position>0 && bucket[i][position-1]>value){
        bucket[i][position] = bucket[i][position-1];
        position--;
      }
      bucket[i][position] = value;
    }

  }
  //输出
  for (int i=0, index=0; i<bucket.length; i++){
    for (int j=0; j<bucket[i].length; j++){
      if (bucket[i][j]!=null){
        input[index] = bucket[i][j];
        index++;
      }
      else{
        break;
      }
    }
  }
  return input;
}

分析

最佳情况：T(n) = O(n+k)

最差情况：T(n) = O(n+k)

平均情况：T(n) = O(n2)

稳定性

桶排序的稳定性取决于每个桶使用的排序算法,像上面的例子中使用了插入排序.就是稳定的,如果使用了快排,那就是不稳定的.

学习心得

其实我个人感觉,桶排序更像是一种思路,而不是像快速排序,插入排序等是一种具体的算法.

桶排序,思路就是将待排序数组,按照一定的映射规则分桶,比如,f(x)=x/10,那么就是按十位分组,12,13在一个桶,25,23在一个桶.然后对每个桶使用其他排序算法进行排序,当然你也可以对每个桶继续使用桶排序.

桶排序有一些限制,即数据必须比较均匀.假设待排序数组为1,2,3,50000.依然按照十位分桶,那么会生成5000个桶,其中只有一个桶里有3个数字,一个桶里有一个数字,其余完全为空.不仅浪费了大量的内存,也没有起到提高效率的作用.

基数排序（Radix Sort）

介绍

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）

实现代码

public int[] sort(int[] input) {
  if (input == null || input.length < 2)
    return input;
  // 1.先算出最大数的位数；
  int max = input[0];
  for (int i = 1; i < input.length; i++) {
    max = Math.max(max, input[i]);
  }
  int maxDigit = 0;
  while (max != 0) {
    max /= 10;
    maxDigit++;
  }

  int mod = 10, div = 1;
  //二维数组,第一维是桶,第二维是桶里的元素
  ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
  for (int i = 0; i < 10; i++)
    bucketList.add(new ArrayList<Integer>());

  for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
    //对mod取模,除以div,可以获得数字在当前位的数字,放进合适的桶里.
    for (int j = 0; j < input.length; j++) {
      int num = (input[j] % mod) / div;
      bucketList.get(num).add(input[j]);
    }
    int index = 0;
    //将每个通内的元素按顺序拿出来,此时的顺序已经是按照当前位排序后的元素
    for (int j = 0; j < bucketList.size(); j++) {
      for (int k = 0; k < bucketList.get(j).size(); k++)
        input[index++] = bucketList.get(j).get(k);
      bucketList.get(j).clear();
    }
  }
  return input;
}

分析

最佳情况：T(n) = O(n * k)

最差情况：T(n) = O(n * k)

平均情况：T(n) = O(n * k)

稳定性

稳定,分桶和从桶里取出都可以保证稳定性.

学习心得

基数排序也是通过分桶的思路,不过在上面例子中,桶的数量固定为10.因为每一位上的数字只有10种可能.

利用桶,每次排序一个位,当最高位也排序之后,序列变为有序序列.

基数排序 计数排序 桶排序

看代码可以发现,这三种排序都用到了桶.

基数排序: 桶固定为10个,用来放置当前位等于桶下标的数字.

计数排序: 每个桶只有一系列相同的数字,桶的数量为最大元素减去最小元素的数量.

桶排序: 每个桶放置一定范围内的数字,具体范围可以自定义.

参考链接

http://www.cnblogs.com/guoyaohua/p/8600214.html

百度百科

ChangeLog

2019-01-11 添加第一题

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十