Java七大排序算法（默认升序排列）

2023-11-21 13:13| 来源: 网络整理| 查看: 265

Java七大排序算法（默认升序排列） 1.冒泡排序（稳定）2.插入排序（稳定）3.选择排序（不稳定）4.计数排序（不稳定）5.快速排序（不稳定）6.归并排序（稳定）7.堆排序（不稳定）

1.冒泡排序（稳定）

属于交换类排序，比较两两相邻的元素，把大的放在右边。注意每一趟过后遍历中的最大元素都会放到最后边，注意遍历范围。这里放入代码

class Solution { public int[] bubblingSort(int[] nums) { if (nums == null || nums.length // 注意这里需要减去i // 如果左边的大于右边的值则交换 if (nums[j] public int[] sort(int[] nums) { if (nums == null || nums.length // 必须判断边界条件 nums[index] = nums[index - 1]; index--; } nums[index] = target; // 插入 } return nums; } } 3.选择排序（不稳定）

选择排序是给每个位置选择当前元素最小的，第一趟给第一个位置选择最小的，需要交换，第二趟需要个第二个位置选择第二小的，因为每次都存在交换，所以不稳定。这里给出具体代码。

class Solution{ public void selectSort(int[] nums) { if (nums == null || nums.length // 注意起始边界条件 if (nums[j] tmp = nums[i]; nums[i] = nums[min]; nums[min] = tmp; } } } } 4.计数排序（不稳定）

计数排序要求数组元素都为大于等于0的数,以空间换时间，主要是需要开辟一个新的数组，存储元素出现的次数。

class Solution{ public int[] countSort(int[] arr) { if (arr == null || arr.length sortArr[arr[i] - min] += 1; } // 计数索引 int index = 0; for (int i = 0; i arr[index++] = i + min; sortArr[i]--; } } return arr; } } 5.快速排序（不稳定）

采用分治递归的思想对冒泡排序的一种改进，每次和一个基准比较，小于该基准的放在左边，大于该基准的放在右边。给出详细代码。

class Solution{ public void fastSort(int[] nums, int low, int high) { if (low >= high) return; int i = low, j = high; int t = 0; int tmp = nums[low]; // 注意如果基准选的是最左边的数那么后边的循环必须先看右边 // 如果基准选的是最右边的数那么后边的循环必须先看左边； while (i j--; } while (i t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } nums[low] = nums[i]; nums[i] = tmp; fastSort(nums, low, i - 1); fastSort(nums, i + 1, high); } } 6.归并排序（稳定）

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。这里给出详细代码。

class Solution{ public int[] mergeSort(int[] arr, int low, int high) { if (arr == null || arr.length = high) return arr; int mid = (low + high) / 2; if (low int[] tmp = new int[high - low + 1]; //临时数组 int i = low; int j = mid + 1; // 注意这里必须加+1 int index = 0; while (i // 小的先赋值 tmp[index++] = arr[i++]; //注意所有索引++ } else { tmp[index++] = arr[j++]; //注意所有索引++ } } while (i tmp[index++] = arr[j++]; } for (int t = 0; t @Test public void testHeapSort() { int[] tree = {4, 10, 3, 5, 1, 2}; int n = tree.length; // heapify(tree, n, 0); // buildHeap(tree, n); heapSort(tree, n); System.out.println(Arrays.toString(tree)); } /** * 堆排序 * * @param tree 待排序的数组 * @param n 数组的长度 * @return 有无返回值都无所谓 */ public int[] heapSort(int[] tree, int n) { // 先判断特殊情况 if (tree == null || tree.length = 0; i--) { // 堆顶元素和最后一个元素交换 swap(tree, i, 0); // 前一部分数组重新heapify化 heapify(tree, i, 0); // 传入的是i 不是原始数组长度n } return tree; } /** * 构建最大堆 * * @param tree 数组 * @param n 数组长度 */ public void buildHeap(int[] tree, int n) { int parentNode = (n - 1) / 2; // 最后一个节点的父节点 // 从最后一个节点的父节点往前开始依次进行heapify for (int i = parentNode; i >= 0; i--) { heapify(tree, n, i); } } /** * heapify操作 * * @param tree * @param n 节点的个数 * @param i 当前父节点的位子 */ public void heapify(int[] tree, int n, int i) { if (i >= n) return; // i是当前父节点分别求出当前节点的左子节点和右子节点 int c1 = 2 * i + 1; // 左孩子节点 int c2 = 2 * i + 2; // 右孩子节点 int max = i; // 假设最大值节点为父节点 if (c1 tree[max]) max = c1; if (c2 tree[max]) max = c2; // 找到最大值的索引 if (max != i) { // 如果不相等则需要交换 swap(tree, i, max); heapify(tree, n, max); // 继续往下边进行heapify } } /** * 交换数组中的两个袁术 * * @param tree * @param i * @param j */ public void swap(int[] tree, int i, int j) { int tmp = tree[i]; tree[i] = tree[j]; tree[j] = tmp; } }

堆排序不太懂的话可以推荐看看这个视频，哈哈，我也是搬运工，如果错误欢迎指正，我是小菜鸡一枚。

【本文地址】

公司简介

联系我们