思维导图
文章已收录Github精选，欢迎Star ：https://github.com/yehongzhi/learningSummary
前言 算法和数据结构是一个程序员的内功，所以经常在一些笔试中都会要求手写一些简单的排序算法，以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法，一起学习一下。
一、冒泡排序 思路：
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
排除最大的数，接着下一轮继续相同的操作，确定第二大的数...
动画演示：
实现代码：
/**@author Ye Hongzhi 公众号：java技术爱好者@name BubbleSort@date 2020-09-05 21:38 public class BubbleSort extends BaseSort public static void main (String[] args) new BubbleSort();@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];1 ];1 ] = temp;//10万个数的数组，耗时：21554毫秒 平均时间复杂度：O(n²)
空间复杂度：O(1)
算法稳定性：稳定
二、插入排序 思路：
取出下一个元素，在前面已排序的元素序列中，从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
动画演示：
实现代码：
/**@author Ye Hongzhi 公众号：java技术爱好者@name InsertSort@date 2020-09-05 22:34 public class InsertSort extends BaseSort public static void main (String[] args) new InsertSort();@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]) {//把比当前遍历的数大的数字往后移动 1 ] = 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) new SelectSort();@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]) {if (minIndex != i) {int temp = nums[i];//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) new ShellSort();@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++) {int preIndex = i - gap;while (preIndex >= 0 && nums[preIndex] > temp) {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) new QuickSort();@Override protected void sort (int [] nums) if (nums == null || nums.length < 2 ) {return ;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) {while (i < j && nums[i] <= key) {if (i < j) {int temp = nums[i];1 );1 , end);//10万个数的数组，耗时：50毫秒 平均时间复杂度：O(nlogn)
算法空间复杂度：O(1)
算法稳定性：不稳定
六、归并排序 归并排序是采用分治法的典型应用，而且是一种稳定的排序方式，不过需要使用到额外的空间。
思路：
把数组不断划分成子序列，划成长度只有2或者1的子序列。
然后利用临时数组，对子序列进行排序，合并，再把临时数组的值复制回原数组。
归并排序的优点在于最好情况和最坏的情况的时间复杂度都是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) new MergeSort();@Override protected void sort (int [] nums) if (nums == null || nums.length < 2 ) {return ;//归并排序 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 ;//左边进行归并排序 //右边进行归并排序 1 , end, 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]) {else {while (i <= mid) {while (j <= end) {//把临时数组中已排序的数复制到nums数组中 if (index >= 0 ) System.arraycopy(temp, 0 , nums, star, index);//10万个数的数组，耗时：26毫秒 平均时间复杂度：O(nlogn)
算法空间复杂度：O(n)
算法稳定性：稳定
七、堆排序 大顶堆概念：每个节点的值都大于或者等于它的左右子节点的值，所以顶点的数就是最大值。
思路：
构建大顶堆的思路，可以看代码注释。
动画演示：
实现代码：
/**@author Ye Hongzhi 公众号：java技术爱好者@name HeapSort@date 2020-09-08 23:34 public class HeapSort extends BaseSort public static void main (String[] args) new HeapSort();@Override protected void sort (int [] nums) if (nums == null || nums.length < 2 ) {return ;private void heapSort (int [] nums) if (nums == null || nums.length < 2 ) {return ;//构建大根堆 int size = nums.length;while (size > 1 ) {//大根堆的交换头尾值，固定最大值在末尾 0 , size - 1 );//末尾的索引值往左减1 //重新构建大根堆 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]) {//交换当前遍历的值与父节点的值 //把父节点的索引指向当前遍历的索引 //往上计算父节点索引 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]) {else {//如果父节点大于最大值，则把父节点索引指向最大值索引 if (nums[index] > nums[largestIndex]) {//如果父节点索引指向最大值索引，证明已经是大根堆，退出循环 if (largestIndex == index) {break ;//如果不是大根堆，则交换父节点的值 //把最大值的索引变成父节点索引 //重新计算左节点索引 2 * index + 1 ;//重新计算右节点索引 2 * index + 2 ;private void swap (int [] nums, int i, int j) int temp = nums[i];//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) new BucketSort();@Override protected void sort (int [] nums) if (nums == null || nums.length < 2 ) {return ;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) {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;//添加到指定下标的桶里，并且使用插入排序排序 int k = 0 ;//合并全部桶的 for (int [] bucketArray : bucketArrays) {if (bucketArray == null || bucketArray.length == 0 ) {continue ;for (int i : bucketArray) {//把值放回到nums数组中 //每个桶使用插入排序进行排序 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++) {//找到一个位置，插入，形成新的有序的数组 int i;for (i = temp.length - 2 ; i >= 0 && temp[i] > num; i--) {1 ] = temp[i];//插入需要添加的值 1 ] = num;//返回 return temp;//10万个数的数组，耗时：8750毫秒 平均时间复杂度：O(M+N)
算法空间复杂度：O(M+N)
算法稳定性：稳定(取决于桶内的排序算法，这里使用的是插入排序所以是稳定的)。
总结
动画演示来源于算法学习网站：https://visualgo.net
讲完这些排序算法后，可能有人会问学这些排序算法有什么用呢，难道就为了应付笔试面试？平时开发也没用得上这些。
我觉得我们应该换个角度来看，比如高中时我们学物理，化学，数学，那么多公式定理，现在也没怎么用得上，但是高中课本为什么要教这些呢？
我的理解是：第一，普及一些常识性的问题。第二，锻炼思维，提高解决问题的能力。第三，为了区分人才。
回到学排序算法有什么用的问题上，实际上也一样。这些最基本的排序算法就是一些常识性的问题，作为开发者应该了解掌握。同时也锻炼了编程思维，其中包含有双指针，分治，递归等等的思想。最后在面试中体现出来的就是人才的划分，懂得这些基本的排序算法当然要比不懂的人要更有竞争力。
建议大家看完之后，能找时间动手写一下，加深理解。
上面所有例子的代码都上传Github了：
https://github.com/yehongzhi/mall
觉得有用就点个赞吧，你的点赞是我创作的最大动力 ~
拒绝做一条咸鱼，我是一个努力让大家记住的程序员。我们下期再见！！！
能力有限，如果有什么错误或者不当之处，请大家批评指正，一起学习交流！
