思维导图
文章已收录Github精选，欢送Star：https://github.com/yehongzhi/learningSummary
前言
算法和数据结构是一个程序员的内功，所以常常在一些口试中都会要求手写一些简略的排序算法，以此考验面试者的编程程度。上面我就简略介绍八种常见的排序算法，一起学习一下。
一、冒泡排序
思路：
- 比拟相邻的元素。如果第一个比第二个大，就替换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最初一对，这样在最初的元素就是最大的数；
- 排除最大的数，接着下一轮持续雷同的操作，确定第二大的数...
- 反复步骤1-3，直到排序实现。
动画演示：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name BubbleSort * @date 2020-09-05 21:38 **/public class BubbleSort extends BaseSort { public static void main(String[] args) { BubbleSort sort = new BubbleSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } for (int i = 0; i < nums.length - 1; i++) { for (int j = 0; j < nums.length - i - 1; j++) { if (nums[j] > nums[j + 1]) { int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } }}//10万个数的数组，耗时：21554毫秒均匀工夫复杂度：O(n²)
空间复杂度：O(1)
算法稳定性：稳固
二、插入排序
思路：
- 从第一个元素开始，该元素能够认为曾经被排序；
- 取出下一个元素，在后面已排序的元素序列中，从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一地位；
- 反复步骤3，直到找到已排序的元素小于或者等于新元素的地位；
- 将新元素插入到该地位后；
- 反复步骤2~5。
动画演示：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name InsertSort * @date 2020-09-05 22:34 **/public class InsertSort extends BaseSort { public static void main(String[] args) { BaseSort sort = new InsertSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } for (int i = 0; i < nums.length - 1; i++) { //以后值 int curr = nums[i + 1]; //上一个数的指针 int preIndex = i; //在数组中找到一个比以后遍历的数小的第一个数 while (preIndex >= 0 && curr < nums[preIndex]) { //把比以后遍历的数大的数字往后挪动 nums[preIndex + 1] = nums[preIndex]; //须要插入的数的下标往前挪动 preIndex--; } //插入到这个数的前面 nums[preIndex + 1] = curr; } }}//10万个数的数组，耗时：2051毫秒均匀工夫复杂度：O(n²)
空间复杂度：O(1)
算法稳定性：稳固
三、抉择排序
思路：
第一轮，找到最小的元素，和数组第一个数替换地位。
第二轮，找到第二小的元素，和数组第二个数替换地位...
直到最初一个元素，排序实现。
动画演示：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name SelectSort * @date 2020-09-06 22:27 **/public class SelectSort extends BaseSort { public static void main(String[] args) { SelectSort sort = new SelectSort(); sort.printNums(); } @Override protected void sort(int[] nums) { for (int i = 0; i < nums.length; i++) { int minIndex = i; for (int j = i + 1; j < nums.length; j++) { if (nums[j] < nums[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = nums[i]; nums[minIndex] = temp; nums[i] = nums[minIndex]; } } }}//10万个数的数组，耗时：8492毫秒均匀工夫复杂度：O(n²)
算法空间复杂度：O(1)
算法稳定性：不稳固
四、希尔排序
思路：
把数组宰割成若干(h)个小组(个别数组长度length/2)，而后对每一个小组别离进行插入排序。每一轮宰割的数组的个数逐渐放大，h/2->h/4->h/8，并且进行排序，保障有序。当h=1时，则数组排序实现。
动画演示：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name SelectSort * @date 2020-09-06 22:27 **/public class ShellSort extends BaseSort { public static void main(String[] args) { ShellSort sort = new ShellSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } int length = nums.length; int temp; //步长 int gap = length / 2; while (gap > 0) { for (int i = gap; i < length; i++) { temp = nums[i]; int preIndex = i - gap; while (preIndex >= 0 && nums[preIndex] > temp) { nums[preIndex + gap] = nums[preIndex]; preIndex -= gap; } nums[preIndex + gap] = temp; } gap /= 2; } }}//10万个数的数组，耗时：261毫秒均匀工夫复杂度：O(nlog2n)
算法空间复杂度：O(1)
算法稳定性：稳固
五、疾速排序
快排，面试最喜爱问的排序算法。这是使用分治法的一种排序算法。
思路：
- 从数组当选一个数做为基准值，个别选第一个数，或者最初一个数。
- 采纳双指针(头尾两端)遍历，从左往右找到比基准值大的第一个数，从右往左找到比基准值小的第一个数，替换两数地位，直到头尾指针相等或头指针大于尾指针，把基准值与头指针的数替换。这样一轮之后，右边的数就比基准值小，左边的数就比基准值大。
- 对右边的数列，反复下面1，2步骤。对左边反复1，2步骤。
- 左右两边数列递归完结后，排序实现。
动画演示：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name SelectSort * @date 2020-09-06 22:27 **/public class QuickSort extends BaseSort { public static void main(String[] args) { QuickSort sort = new QuickSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } quickSort(nums, 0, nums.length - 1); } private void quickSort(int[] nums, int star, int end) { if (star > end) { return; } int i = star; int j = end; int key = nums[star]; while (i < j) { while (i < j && nums[j] > key) { j--; } while (i < j && nums[i] <= key) { i++; } if (i < j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } nums[star] = nums[i]; nums[i] = key; quickSort(nums, star, i - 1); quickSort(nums, i + 1, end); }}//10万个数的数组，耗时：50毫秒均匀工夫复杂度：O(nlogn)
算法空间复杂度：O(1)
算法稳定性：不稳固
六、归并排序
归并排序是采纳分治法的典型利用，而且是一种稳固的排序形式，不过须要应用到额定的空间。
思路：
- 把数组一直划分成子序列，划成长度只有2或者1的子序列。
- 而后利用长期数组，对子序列进行排序，合并，再把长期数组的值复制回原数组。
- 重复操作1~2步骤，直到排序实现。
归并排序的长处在于最好状况和最坏的状况的工夫复杂度都是O(nlogn)，所以是比较稳定的排序形式。
动画演示：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name MergeSort * @date 2020-09-08 23:30 **/public class MergeSort extends BaseSort { public static void main(String[] args) { MergeSort sort = new MergeSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } //归并排序 mergeSort(0, nums.length - 1, nums, new int[nums.length]); } private void mergeSort(int star, int end, int[] nums, int[] temp) { //递归终止条件 if (star >= end) { return; } int mid = star + (end - star) / 2; //右边进行归并排序 mergeSort(star, mid, nums, temp); //左边进行归并排序 mergeSort(mid + 1, end, nums, temp); //合并左右 merge(star, end, mid, nums, temp); } private void merge(int star, int end, int mid, int[] nums, int[] temp) { int index = 0; int i = star; int j = mid + 1; while (i <= mid && j <= end) { if (nums[i] > nums[j]) { temp[index++] = nums[j++]; } else { temp[index++] = nums[i++]; } } while (i <= mid) { temp[index++] = nums[i++]; } while (j <= end) { temp[index++] = nums[j++]; } //把长期数组中已排序的数复制到nums数组中 if (index >= 0) System.arraycopy(temp, 0, nums, star, index); }}//10万个数的数组，耗时：26毫秒//10万个数的数组，耗时：26毫秒
均匀工夫复杂度：O(nlogn)
算法空间复杂度：O(n)
算法稳定性：稳固
七、堆排序
大顶堆概念：每个节点的值都大于或者等于它的左右子节点的值，所以顶点的数就是最大值。
思路：
- 对原数组构建成大顶堆。
- 替换头尾值，尾指针索引减一，固定最大值。
- 从新构建大顶堆。
- 反复步骤2~3，直到最初一个元素，排序实现。
构建大顶堆的思路，能够看代码正文。
动画演示：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name HeapSort * @date 2020-09-08 23:34 **/public class HeapSort extends BaseSort { public static void main(String[] args) { HeapSort sort = new HeapSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } heapSort(nums); } private void heapSort(int[] nums) { if (nums == null || nums.length < 2) { return; } //构建大根堆 createTopHeap(nums); int size = nums.length; while (size > 1) { //大根堆的替换头尾值，固定最大值在开端 swap(nums, 0, size - 1); //开端的索引值往左减1 size--; //从新构建大根堆 updateHeap(nums, size); } } private void createTopHeap(int[] nums) { for (int i = 0; i < nums.length; i++) { //以后插入的索引 int currIndex = i; //父节点的索引 int parentIndex = (currIndex - 1) / 2; //如果以后遍历的值比父节点大的话，就替换值。而后持续往下层比拟 while (nums[currIndex] > nums[parentIndex]) { //替换以后遍历的值与父节点的值 swap(nums, currIndex, parentIndex); //把父节点的索引指向以后遍历的索引 currIndex = parentIndex; //往上计算父节点索引 parentIndex = (currIndex - 1) / 2; } } } private void updateHeap(int[] nums, int size) { int index = 0; //左节点索引 int left = 2 * index + 1; //右节点索引 int right = 2 * index + 2; while (left < size) { //最大值的索引 int largestIndex; //如果右节点大于左节点，则最大值索引指向右子节点索引 if (right < size && nums[left] < nums[right]) { largestIndex = right; } else { largestIndex = left; } //如果父节点大于最大值，则把父节点索引指向最大值索引 if (nums[index] > nums[largestIndex]) { largestIndex = index; } //如果父节点索引指向最大值索引，证实曾经是大根堆，退出循环 if (largestIndex == index) { break; } //如果不是大根堆，则替换父节点的值 swap(nums, largestIndex, index); //把最大值的索引变成父节点索引 index = largestIndex; //从新计算左节点索引 left = 2 * index + 1; //从新计算右节点索引 right = 2 * index + 2; } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}//10万个数的数组，耗时：38毫秒均匀工夫复杂度：O(nlogn)
算法空间复杂度：O(1)
算法稳定性：不稳固
八、桶排序
思路：
- 找出最大值，最小值。
- 依据数组的长度，创立出若干个桶。
- 遍历数组的元素，依据元素的值放入到对应的桶中。
- 对每个桶的元素进行排序(可应用快排，插入排序等)。
- 按程序合并每个桶的元素，排序实现。
对于数组中的元素散布平均的状况，排序效率较高。相同的，如果散布不平均，则会导致大部分的数落入到同一个桶中，使效率升高。
动画演示(来源于五分钟学算法，侵删)：
实现代码：
/** * @author Ye Hongzhi 公众号：java技术爱好者 * @name BucketSort * @date 2020-09-08 23:37 **/public class BucketSort extends BaseSort { public static void main(String[] args) { BucketSort sort = new BucketSort(); sort.printNums(); } @Override protected void sort(int[] nums) { if (nums == null || nums.length < 2) { return; } bucketSort(nums); } public void bucketSort(int[] nums) { if (nums == null || nums.length < 2) { return; } //找出最大值，最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int num : nums) { min = Math.min(min, num); max = Math.max(max, num); } int length = nums.length; //桶的数量 int bucketCount = (max - min) / length + 1; int[][] bucketArrays = new int[bucketCount][]; //遍历数组，放入桶内 for (int i = 0; i < length; i++) { //找到桶的下标 int index = (nums[i] - min) / length; //增加到指定下标的桶里，并且应用插入排序排序 bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]); } int k = 0; //合并全副桶的 for (int[] bucketArray : bucketArrays) { if (bucketArray == null || bucketArray.length == 0) { continue; } for (int i : bucketArray) { //把值放回到nums数组中 nums[k++] = i; } } } //每个桶应用插入排序进行排序 private int[] insertSortArrays(int[] arr, int num) { if (arr == null || arr.length == 0) { return new int[]{num}; } //创立一个temp数组，长度是arr数组的长度+1 int[] temp = new int[arr.length + 1]; //把传进来的arr数组，复制到temp数组 for (int i = 0; i < arr.length; i++) { temp[i] = arr[i]; } //找到一个地位，插入，造成新的有序的数组 int i; for (i = temp.length - 2; i >= 0 && temp[i] > num; i--) { temp[i + 1] = temp[i]; } //插入须要增加的值 temp[i + 1] = num; //返回 return temp; }}//10万个数的数组，耗时：8750毫秒均匀工夫复杂度：O(M+N)
算法空间复杂度：O(M+N)
算法稳定性：稳固(取决于桶内的排序算法，这里应用的是插入排序所以是稳固的)。
总结
动画演示来源于算法学习网站：https://visualgo.net
讲完这些排序算法后，可能有人会问学这些排序算法有什么用呢，难道就为了应酬口试面试？平时开发也没用得上这些。
我感觉咱们应该换个角度来看，比方高中时咱们学物理，化学，数学，那么多公式定理，当初也没怎么用得上，然而高中课本为什么要教这些呢？
我的了解是：第一，遍及一些常识性的问题。第二，锤炼思维，进步解决问题的能力。第三，为了辨别人才。
回到学排序算法有什么用的问题上，实际上也一样。这些最根本的排序算法就是一些常识性的问题，作为开发者应该理解把握。同时也锤炼了编程思维，其中蕴含有双指针，分治，递归等等的思维。最初在面试中体现进去的就是人才的划分，懂得这些根本的排序算法当然要比不懂的人要更有竞争力。
倡议大家看完之后，能找工夫入手写一下，加深了解。
下面所有例子的代码都上传Github了：
https://github.com/yehongzhi/mall
感觉有用就点个赞吧，你的点赞是我创作的最大能源~
回绝做一条咸鱼，我是一个致力让大家记住的程序员。咱们下期再见！！！
能力无限，如果有什么谬误或者不当之处，请大家批评指正，一起学习交换！