排序方法有哪几种，八种经典排序算法介绍-易企推网

实现代码：

/** * @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)

算法稳定性：稳定(取决于桶内的排序算法，这里使用的是插入排序所以是稳定的)。

总结