面试官：六大排序算法你懂吗？我拿出这篇文章后 面试官傻眼了！

前言

我们在面试的时候总会被问到一些算法，虽然算法是一些基础知识，但是难起来也会让人非常头疼。

排序算法应该算是一些简单且基本的算法，那么，我们在面试过程被问到排序算法也不用怕，看完这篇文章，相信你的回答一定会让面试官傻眼的。

下面我们就看一下6大排序算法：

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序-代码实现

publicclassSelectionSort implements IArraySort { @Overridepublicint[] sort(int[] sourceArray) throws Exception {int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 总共要经过 N-1 轮比较for (int i = 0; i < arr.length - 1; i++) {int min = i; // 每轮需要比较的次数 N-ifor (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[min]) { // 记录目前能找到的最小值元素的下标 min = j; } } // 将找到的最小值和i位置所在的值进行交换if (i != min) {int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } }return arr; }}

选择排序-动态效果图

插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序-代码实现

publicclassInsertSort implements IArraySort { @Overridepublicint[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的for (int i = 1; i < arr.length; i++) { // 记录要插入的数据int tmp = arr[i]; // 从已经排序的序列最右边的开始比较，找到比其小的数int j = i;while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数，插入if (j != i) { arr[j] = tmp; } }return arr; }}

插入排序-动态效果图

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序

希尔排序-代码实现

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

希尔排序-动态效果图

冒泡排序

冒泡排序是一种简单直观的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序-代码实现

publicclassBubbleSort implements IArraySort { @Overridepublicint[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);for (int i = 1; i < arr.length; i++) { // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。boolean flag = true;for (int j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) {int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false; } }if (flag) {break; } }return arr; }}

冒泡排序-动态效果图

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序-代码实现

publicclassMergeSort implements IArraySort { @Overridepublicint[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);if (arr.length < 2) {return arr; }int middle = (int) Math.floor(arr.length / 2);int[] left = Arrays.copyOfRange(arr, 0, middle);int[] right = Arrays.copyOfRange(arr, middle, arr.length);return merge(sort(left), sort(right)); }protectedint[] merge(int[] left, int[] right) {int[] result = newint[left.length + right.length];int i = 0;while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } else { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } }while (left.length > 0) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); }while (right.length > 0) { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); }return result; }}

归并排序-动态效果图

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。

在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。

事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序-代码实现

publicclassQuickSort implements IArraySort { @Overridepublicint[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);return quickSort(arr, 0, arr.length - 1); }privateint[] quickSort(int[] arr, int left, int right) {if (left < right) {int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); }return arr; }privateint partition(int[] arr, int left, int right) { // 设定基准值（pivot）int pivot = left;int index = pivot + 1;for (int i = index; i <= right; i++) {if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1);return index - 1; }privatevoid swap(int[] arr, int i, int j) {int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}

快速排序-动态效果图

排序时间复杂度

写在最后

此次分享到这里又要结束 了，不知道对你有没有帮助，欢迎大家留言！

想了解更多精彩内容，快来关注程序猿的内心独白