排序算法面试官：手撕十大排序算法，你会几种？( 二 ) |int|

插入排序（Insertion Sort）插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
（1）算法步骤
步骤1：从第一个元素开始，该元素可以认为已经被排序；步骤2：取出下一个元素，在已经排序的元素序列中从后向前扫描；步骤3：如果该元素（已排序）大于新元素，将该元素移到下一位置；步骤4：重复步骤3 ，直到找到已排序的元素小于或者等于新元素的位置；步骤5：将新元素插入到该位置后；步骤6：重复步骤2~5；
（2）过程演示

本文插图
（3）代码实现
public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length) // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 for (int i = 1 i &lt arr.length i++) { // 记录要插入的数据 int tmp = arr[i] // 从已经排序的序列最右边的开始比较，找到比其小的数 int j = i while (j &gt 0 &amp&amp tmp &lt arr[j - 1]) { arr[j] = arr[j - 1] j-- } // 存在比其小的数，插入 if (j != i) { arr[j] = tmp } } return arr }}
希尔排序（Shell Sort）
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
（1）算法步骤
步骤1：选择一个增量序列 t1 ， t2 ， …… ， tk ，其中 ti &gt tj, tk = 1；步骤2：按增量序列个数 k ，对序列进行 k趟排序；步骤3：每趟排序，根据对应的增量 ti ，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1时，整个序列作为一个表来处理，表长度即为整个序列的长度；
（2）过程演示

本文插图
（3）代码实现

public class ShellSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝 ， 不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length) int gap = 1 while (gap &lt arr.length) { gap = gap * 3 + 1 } while (gap &gt 0) { for (int i = gap i &lt arr.length i++) { int tmp = arr[i] int j = i - gap while (j &gt= 0 &amp&amp arr[j] &gt tmp) { arr[j + gap] = arr[j] j -= gap } arr[j + gap] = tmp } gap = (int) Math.floor(gap / 3) } return arr }}

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