前言
算法和数据结构是一个程序员的内功 ， 所以经常在一些笔试中都会要求手写一些简单的排序算法 ， 以此考验面试者的编程水平 。下面我就简单介绍八种常见的排序算法 ， 一起学习一下 。一、冒泡排序
思路：- 比较相邻的元素 。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
- 排除最大的数，接着下一轮继续相同的操作，确定第二大的数...
- 重复步骤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();}@Overrideprotected 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(n2)空间复杂度：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();}@Overrideprotected 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(n2)空间复杂度：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();}@Overrideprotected 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(n2)算法空间复杂度：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();}@Overrideprotected 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();}@Overrideprotected 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步骤，直到排序完成 。
动画演示：
实现代码：
/** * @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();}@Overrideprotected 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毫秒算法复杂度：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();}@Overrideprotected 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);//末尾的索引值往左减1size--;//重新构建大根堆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();}@Overrideprotected 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数组的长度+1int[] 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
讲完这些排序算法后，可能有人会问学这些排序算法有什么用呢，难道就为了应付笔试面试？平时开发也没用得上这些 。
我觉得我们应该换个角度来看，比如高中时我们学物理，化学，数学，那么多公式定理，现在也没怎么用得上，但是高中课本为什么要教这些呢？
我的理解是：第一 ， 普及一些常识性的问题 。第二，锻炼思维，提高解决问题的能力 。第三 ， 为了区分人才 。
回到学排序算法有什么用的问题上，实际上也一样 。这些最基本的排序算法就是一些常识性的问题，作为开发者应该了解掌握 。同时也锻炼了编程思维，其中包含有双指针，分治，递归等等的思想 。最后在面试中体现出来的就是人才的划分 ， 懂得这些基本的排序算法当然要比不懂的人要更有竞争力 。
建议大家看完之后，能找时间动手写一下，加深理解 。
