一、各种排序算法
1.java自带的排序
int[] nums = new int[]{8,4,3,7,5,6};
Arrays.sort(nums);
AI 代码解读
## 2.冒泡排序 ```java public class BubbleSort { public static void main(String[] args) { int[] nums = {5, -1, 0, 9, -4, 5, 3}; System.out.println("排序前：" + Arrays.toString(nums)); nums = bubbleSort(nums); System.out.println("排序后：" + Arrays.toString(nums)); } /** * 冒泡排序 * * @param nums：要排序的数组 * @return 返回排序后的数组 */ public static int[] bubbleSort(int[] nums) { //System.out.println("排序过程："); for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length - 1 - i; j++) { if (nums[j] > nums[j + 1]) { //交换位置 int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } return nums; } } ```
## 3.堆排序 ```java public class HeapSort { public static void main(String[] args) { int[] nums = {5, -1, 0, 9, -4, 5, 3}; System.out.println("排序前：" + Arrays.toString(nums)); nums = heapSort(nums); System.out.println("排序后：" + Arrays.toString(nums)); } // public static int[] heapSort(int[] nums) { int start = (nums.length - 1) / 2; //调整为大顶堆 for (int i = start; i >= 0; i--) { maxHeap(nums, nums.length, i); } // for (int i = nums.length - 1; i >= 0; i--) { int temp = nums[0]; nums[0] = nums[i]; nums[i] = temp; maxHeap(nums, i, 0); } return nums; } //转大顶堆的方法 public static void maxHeap(int[] nums, int size, int index) { //当前节点 int self = index; //左子节点 int left = 2 * index + 1; //和左子节点进行对比，选出最大的节点放到自身位置 if (left < size && nums[self] < nums[left]) { int temp = nums[self]; nums[self] = nums[left]; nums[left] = temp; maxHeap(nums, size, left); } //右子节点 int right = 2 * index + 2; //和右子节点进行对比，选出最大的节点放到自身位置 if (right < size && nums[self] < nums[right]) { int temp = nums[self]; nums[self] = nums[right]; nums[right] = temp; maxHeap(nums, size, right); } } } ```
## 4.插入排序 ```java public class InsertSort { public static void main(String[] args) { int[] nums = {5, -1, 0, 9, -4, 5, 3}; System.out.println("排序前：" + Arrays.toString(nums)); nums = insertSort(nums); System.out.println("排序后：" + Arrays.toString(nums)); } public static int[] insertSort(int[] nums) { for (int i = 0; i < nums.length; i++) { //把当前遍历的数字存起来 int temp = nums[i]; //遍历当前数字前面所有的数字 int j; for (j = i - 1; j >= 0 && nums[j] > temp; j--) { //把前一个数字赋给后一个数字 nums[j + 1] = nums[j]; } //把临时变量赋给不满足条件的后一个元素 nums[j + 1] = temp; } return nums; } } ```
## 5.归并排序 ```java public class MergeSort { public static void main(String[] args) { int[] nums = {5, -1, 0, 9, -4, 5, 3}; System.out.println("排序前：" + Arrays.toString(nums)); nums = mergeSort(nums, 0, nums.length - 1); System.out.println("排序后：" + Arrays.toString(nums)); } public static int[] mergeSort(int[] nums, int low, int high) { int mid = (low + high) / 2; if (low < high) { mergeSort(nums, low, mid); mergeSort(nums, mid + 1, high); merge(nums, low, mid, high); } return nums; } public static void merge(int[] nums, int low, int mid, int high) { //临时数组 int[] temp = new int[high - low + 1]; //记录左边的数组的最左位置 int i = low; //记录右边数组的最左位置 int j = mid + 1; //记录放入temp数组中的位置,从0开始放，每次放 就++ int index = 0; while (i <= mid && j <= high) { if (nums[i] < nums[j]) { temp[index++] = nums[i++]; } else { temp[index++] = nums[j++]; } } //处理多余的数组 while (i <= mid) { temp[index++] = nums[i++]; } while (j <= high) { temp[index++] = nums[j++]; } //将临时数组中的值赋给nums数组中对应位置 for (int k = 0; k < temp.length; k++) { nums[k + low] = temp[k]; } } } ```
## 6.快速排序 ```java public class QuickSort { public static void main(String[] args) { int[] nums = {5, -1, 0, 9, -4, 5, 3}; System.out.println("排序前：" + Arrays.toString(nums)); nums = quickSort(nums, 0, nums.length - 1); System.out.println("排序后：" + Arrays.toString(nums)); } /** * @param nums 被排序的数组 * @param start 排序开始位置 * @param end 排序结束位置 * @return 返回排序后的数组 */ public static int[] quickSort(int[] nums, int start, int end) { if (start < end) { //低位置 int low = start; //高位置 int high = end; //取开始位置元素作为标准数 int standard = nums[start]; while (low < high) { //如果右边的数组比标准数大 while (nums[high] >= standard && low < high) { high--; } //使用右边的数字替换左边的数字 nums[low] = nums[high]; //如果左边的数组比标准数小 while (nums[low] <= standard && low < high) { low++; } //使用左边的数字替换右边的数字 nums[high] = nums[low]; } //把标准数赋回给低位置或者高位置（此时低位置和高位置已经重合） nums[low] = standard; //处理标准数左边的数字 nums = quickSort(nums, start, low); //处理标准数右边的数字 nums = quickSort(nums, low + 1, end); } return nums; } } ```
## 7.选择排序 ```java public class SelectSort { public static void main(String[] args) { int[] nums = {5, -1, 0, 9, -4, 5, 3}; System.out.println("排序前：" + Arrays.toString(nums)); nums = selectSort(nums); System.out.println("排序后：" + Arrays.toString(nums)); } public static int[] selectSort(int[] nums) { for (int i = 0; i < nums.length; i++) { int min = nums[i]; int minIndex = i; for (int j = i + 1; j < nums.length; j++) { if (nums[j] < min) { min = nums[j]; minIndex = j; } } //把找到的最小值和当前i位置替换 int temp = nums[i]; nums[i] = nums[minIndex]; nums[minIndex] = temp; } return nums; } } ```
## 8.希尔排序 ```java public class ShellSort { public static void main(String[] args) { int[] nums = {5, -1, 0, 9, -4, 5, 3}; System.out.println("排序前：" + Arrays.toString(nums)); nums = shellSort(nums); System.out.println("排序后：" + Arrays.toString(nums)); } // 升序排序 public static int[] shellSort(int[] nums) { //遍历所有步长 for (int d = nums.length / 2; d > 0; d /= 2) { //遍历所有元素 for (int i = 0; i < nums.length; i++) { //遍历本组中所有元素 for (int j = i - d; j >= 0; j -= d) { //如果当前元素大于加上步长后的那个元素 if (nums[j] > nums[j + d]) { int temp = nums[j]; nums[j] = nums[j + d]; nums[j + d] = temp; } } } } return nums; } // 降序排序 public static int[] shellSort2(int[] nums) { //遍历所有步长 for (int d = nums.length / 2; d > 0; d /= 2) { //遍历所有元素 for (int i = 0; i < nums.length; i++) { //遍历本组中所有元素 for (int j = i - d; j >= 0; j -= d) { //如果当前元素大于加上步长后的那个元素 if (nums[j] < nums[j + d]) { int temp = nums[j]; nums[j] = nums[j + d]; nums[j + d] = temp; } } } } return nums; } } ```
## 9.二叉排序树排序 ```java public class BinarySortTree { public Node root; public int len; public BinarySortTree() { } //返回根节点的高度 public int height() { if (root == null) { return -1; } else { return root.height(); } } //添加节点 public void add(Node node) { if (root == null) { return; } root.add(node); } //中序遍历 public void midShow() { if (this.root == null) { return; } root.midShow(); } //中序遍历 public List midShow2() { if (this.root == null) { return null; } List nums = new ArrayList<>(); root.midShow2(nums); System.out.println(nums.size() + " ---"); return nums; } //查找前序查找 public Node frontSearch(int value) { if (root == null) { return null; } return root.frontSearch(value); } //删除指定值的节点 public void remove(int value) { if (root == null) { return; } else { root.remove(value); } } } ``` ```java public class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } //返回当前节点的高度 public int height() { return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1; } //当前节点左子树的高度 public int leftHeight() { if (left == null) { return 0; } else { return left.height(); } } //当前节点右子树的高度 public int rightHeight() { if (right == null) { return 0; } else { return right.height(); } } //中序遍历 public void midShow() { if (this == null) { return; } //左 if (this.left != null) { this.left.midShow(); } //自身 System.out.println(this.value); //右 if (this.right != null) { this.right.midShow(); } } //中序遍历 public void midShow2(List nums) { if (this == null) { return; } //左 if (this.left != null) { this.left.midShow2(nums); } //自身 nums.add(this.value); //右 if (this.right != null) { this.right.midShow2(nums); } } //添加节点 public void add(Node node) { if (this == null || node == null) { return; } if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else { if (this.right == null) { this.right = node; } else { this.right.add(node); } } //是否要控制排序树平衡(查询平衡会增加排序的时间,但是以后的查找速度会提升) if (true) { if (leftHeight() - rightHeight() >= 2) { if (left != null && left.leftHeight() < left.rightHeight()) { //双旋转 left.leftRotate(); rightRotate(); } else { //左子树高度与右子树高度之差大于等于2，则进行右旋转 rightRotate(); } } else if (rightHeight() - leftHeight() >= 2) { if (right != null && right.rightHeight() < right.leftHeight()) { //双旋转 right.rightRotate(); leftRotate(); } else { //左旋转 leftRotate(); } } } } //左旋转 private void leftRotate() { //创建一个新节点，值就为当前节点的值 Node node = new Node(this.value); //将当前节点的左节点设置为新节点的左节点 node.left = this.left; //将新节点的右节点设置为当前节点的右节点的左节点 node.right = this.right.left; //将当前节点的值设置为当前节点的右节点的值 this.value = this.right.value; //将当前节点的右节点设置为当前节点右节点的右节点 this.right = this.right.right; //将当前节点的左子树设置为新节点 this.left = node; } //右旋转 private void rightRotate() { //创建一个新节点，值就为当前节点的值 Node node = new Node(this.value); //将当前节点的右节点设置为新节点的右节点 node.right = this.right; //将新节点的左节点设置为当前节点的左节点的右节点 node.left = this.left.right; //将当前节点的值设置为当前节点的左节点的值 this.value = this.left.value; //将当前节点的左节点设置为当前节点左节点的左节点 this.left = this.left.left; //将当前节点的右子树设置为新节点 this.right = node; } //查找前序查找 public Node frontSearch(int value) { if (this == null) { return null; } //自身 if (this.value == value) { return this; } //左 if (left != null) { return left.frontSearch(value); } //右 if (right != null) { return right.frontSearch(value); } return null; } //删除指定值的节点 public void remove(int value) { if (this == null) { return; } else { } } @Override public String toString() { return "Node{" + "value=" + value + '}'; } } ``` ```java BinarySortTree binarySortTree = new BinarySortTree(); binarySortTree.len = nums.length; binarySortTree.root = new Node(nums[0]); for (int i = 1; i < nums.length; i++) { binarySortTree.root.add(new Node(nums[i])); } ```
# 二、各种算法的速度对比 ```java public class SortCompare { public static void main(String[] args) { //创建测试数组 int[] nums = new int[12000]; for (int i = 0; i < nums.length; i++) { nums[i] = new Random().nextInt(100); } System.out.println("原始数组：" + Arrays.toString(nums)); long start = System.currentTimeMillis(); System.out.println("Arrays自带排序："); int[] nums2 = nums.clone(); Arrays.sort(nums2); System.out.println(Arrays.toString(nums2)); long end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- System.out.println("冒泡排序："); System.out.println(Arrays.toString(BubbleSort.bubbleSort(nums.clone()))); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- start = System.currentTimeMillis(); System.out.println("快速排序："); System.out.println(Arrays.toString(QuickSort.quickSort(nums.clone(), 0, nums.length - 1))); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- start = System.currentTimeMillis(); System.out.println("插入排序："); System.out.println(Arrays.toString(InsertSort.insertSort(nums.clone()))); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- start = System.currentTimeMillis(); System.out.println("希尔排序："); System.out.println(Arrays.toString(ShellSort.shellSort(nums.clone()))); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- start = System.currentTimeMillis(); System.out.println("选择排序："); System.out.println(Arrays.toString(SelectSort.selectSort(nums.clone()))); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- start = System.currentTimeMillis(); System.out.println("归并排序："); System.out.println(Arrays.toString(MergeSort.mergeSort(nums.clone(), 0, nums.length - 1))); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- start = System.currentTimeMillis(); System.out.println("堆排序："); System.out.println(Arrays.toString(HeapSort.heapSort(nums.clone()))); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- start = System.currentTimeMillis(); System.out.println("二叉排序树："); BinarySortTree binarySortTree = new BinarySortTree(); binarySortTree.len = nums.length; binarySortTree.root = new Node(nums[0]); for (int i = 1; i < nums.length; i++) { binarySortTree.root.add(new Node(nums[i])); } System.out.println((binarySortTree.midShow2())); end = System.currentTimeMillis(); System.out.println("用时：" + (end - start) / 1000.0 + "秒"); //-------------------------------------------------------------- } } ``` ```java Arrays自带排序：用时：0.01秒 冒泡排序：用时：0.327秒 快速排序：用时：0.007秒 插入排序：用时：0.024秒 希尔排序：用时：0.159秒 选择排序：用时：0.063秒 归并排序：用时：0.005秒 堆排序：用时：0.043秒 二叉排序树排序：用时：1.354秒 ```
# 三、总结 1、 java自带的数组排序接口速度已经足够快了 2、总体而言，归并排序和快速排序的速度最快，但当数组长度过大的时候容易发生栈溢出 3、 二叉排序树速度最慢，但是其适用于长度可变的排序场景（类似于优先队列）
