冒泡，选择，插入，希尔，归并，快速排序大合集，面试收藏必备 _快速排序

在很多大厂的面试中，算法是最基本的要求，像基础的算法，冒泡，选择，插入等，基本上都会问到。
很多同学往往忽略了其重要程度，只注重编程语言，小编并不建议这样子，今天我们来梳理一下算法，汇总一下面试的一些基础算法。
冒泡排序原理：每次冒泡排序操作都会将相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足，就交换这两个相邻元素的次序，一次冒泡至少让一个元素移动到它应该排列的位置，重复N次，就完成了冒泡排序。

文章插图

代码实现：

/*** 冒泡算法* @author：溪云阁* @date：2020年5月3日* 冒泡排序只会操作相邻的两个数据 。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求 。* 如果不满足就让它俩互换 。一次冒泡会让至少一个元素移动到它应该在的位置，重复n 次，* 就完成了 n 个数据的排序工作 。*/public static void bubbleSort(Integer[] arr) {// 如果只有一个元素就不用排序了if (arr.length <= 1) {return;} else {// 打印排序后的数组System.out.println("排序前的数组：" + Arrays.toString(arr));for (int i = 0; i < arr.length; ++i) {// 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了boolean flag = false;// 此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，for (int j = 0; j < arr.length - i - 1; ++j) {// 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少if (arr[j] > arr[j + 1]) {// 即这两个相邻的数是逆序的，交换位置final int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = true;}}if (!flag)// 没有数据交换，数组已经有序，退出排序break;}// 打印排序后的数组System.out.println("排序后的数组：" + Arrays.toString(arr));}}

选择排序原理：先遍历数组，然后找到一个最大或者最小的元素（这个看需要），把这个元素放到第一个位置，接着在剩余的数组中继续找，找到比第一个大或者小的元素，放到第二个位置，依次这样子做，从而完成排序。

文章插图
【冒泡，选择，插入，希尔，归并，快速排序大合集，面试收藏必备】
代码实现：

 /*** 选择排序* @author 溪云阁* @param arr void* 先遍历数组，然后找到一个最大或者最小的元素（这个看需要）* 把这个元素放到第一个位置，接着在剩余的数组中继续找* 找到比第一个大或者小的元素，放到第二个位置* 依次这样子做，从而完成排序 。*/public static void selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {// 用来记录最小值的索引位置，默认值为iint minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {// 遍历 i+1~length 的值，找到其中最小值的位置minIndex = j;}}// 交换当前索引 i 和最小值索引 minIndex 两处的值if (i != minIndex) {final int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}

插入排序原理：这个比较抽象，但是我来划分来辅助理解
一组无序序列{A1,A2,........An}
先取出A1，然后从A2与A1比较，比较完之后序列状况是{A1,A2}{A3..........An}，这时候其中{A1,A2}就变成有序
然后取出A3 ，放到{A1,A2}有序序列合适位置，从而形成{A1,A2,A3}{A4........An}
重复这个过程，直到取出An放入{A1,A2........An-1}有序序列中

文章插图

代码实现：

 /*** 插入排序* @author 溪云阁* @param ins* @return int[]* 一组无序序列{A1,A2,........An}* 先取出A1，然后从A2与A1比较，比较完之后序列状况是{A1,A2}{A3..........An}，这时候其中{A1,A2}就变成有序* 然后取出A3 ，放到{A1,A2}有序序列合适位置，从而形成{A1,A2,A3}{A4........An}* 重复这个过程，直到取出An放入{A1,A2........An-1}有序序列中*/public static int[] insertSort(int[] ins) {for (int i = 1; i < ins.length; i++) {// 保存每次需要插入的那个数final int temp = ins[i];int j;for (j = i; j > 0 && ins[j - 1] > temp; j--) {// 吧大于需要插入的数往后移动 。最后不大于temp的数就空出来jins[j] = ins[j - 1];}// 将需要插入的数放入这个位置ins[j] = temp;}return ins;}

希尔排序原理：希尔排序是插入排序的改进版，它将数组按照约定的数量分成N列，对每一列执行插入排序，接着缩小步长，不断重复这过程，最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法。