AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【排序算法】Java实现9大排序算法及其速度对比(附详细代码)

2022-12-07 96
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【排序算法】Java实现9大排序算法及其速度对比(附详细代码)

@TOC

一、各种排序算法

1.java自带的排序

int[] nums = new int[]{8,4,3,7,5,6};
Arrays.sort(nums);
## 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、 二叉排序树速度最慢，但是其适用于长度可变的排序场景（类似于优先队列）
文章标签：
Java
搜索推荐
算法
关键词：
Java代码
算法代码
算法java
Java算法
排序算法Java
WSKH0929
目录
相关文章
热爱技术的小郑
|
6天前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天（简述Redis事务实现---------＞负载均衡算法、类型）
这篇文章是关于Java面试中Redis相关问题的笔记，包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
热爱技术的小郑
24 1
一天五道Java面试题----第十天（简述Redis事务实现---------＞负载均衡算法、类型）
AI之家
|
2天前
|
机器学习/深度学习 人工智能 自然语言处理
【自然语言处理】TF-IDF算法在人工智能方面的应用，附带代码
TF-IDF算法在人工智能领域，特别是自然语言处理（NLP）和信息检索中，被广泛用于特征提取和文本表示。以下是一个使用Python的scikit-learn库实现TF-IDF算法的简单示例，并展示如何将其应用于文本数据。
AI之家
116 65
热爱技术的小郑
|
1天前
|
数据可视化 Java
使用ChatGPT实现可视化操作扫雷小游戏 【java代码实现】
这篇文章介绍了使用Java语言和Swing框架实现的扫雷小游戏的详细代码和实现过程。
热爱技术的小郑
4 1
使用ChatGPT实现可视化操作扫雷小游戏 【java代码实现】
李木子2024
|
1天前
|
前端开发 IDE Java
"揭秘前端转Java的秘径：SpringBoot Web极速入门，掌握分层解耦艺术，让你的后端代码飞起来，你敢来挑战吗？"
【8月更文挑战第19天】面向前端开发者介绍Spring Boot后端开发，通过简化Spring应用搭建，快速实现Web应用。本文以创建“Hello World”应用为例，展示项目基本结构与运行方式。进而深入探讨三层架构（Controller、Service、DAO）下的分层解耦概念，通过员工信息管理示例，演示各层如何协作及依赖注入的使用，以此提升代码灵活性与可维护性。
李木子2024
5 2
萝卜带泥
|
3天前
|
Java 开发者
Java中的Lambda表达式：简化你的代码之旅
【8月更文挑战第17天】 在编程的海洋中，简洁是航行的风帆。Lambda表达式，作为Java 8的一大亮点，为开发者提供了一种更为紧凑、易读的编码方式。本篇文章将带你领略Lambda表达式的魅力，从基础概念到实际应用，让你的代码像诗句一样流畅。
萝卜带泥
13 4
aliyun8599273441-30642
|
1天前
|
设计模式 算法 安全
Java编程中的设计模式：提升代码的可维护性和扩展性
【8月更文挑战第19天】在软件开发的世界里，设计模式是解决常见问题的一种优雅方式。本文将深入探讨Java编程语言中常用的几种设计模式，并解释如何通过这些模式来提高代码的可维护性和扩展性。文章不涉及具体的代码实现，而是侧重于理论和实践相结合的方式，为读者提供一种思考和改善现有项目的新视角。
aliyun8599273441-30642
3 1
热爱技术的小郑
|
1天前
|
设计模式 Java
常用设计模式介绍~~~ Java实现 【概念+案例+代码】
文章提供了一份常用设计模式的全面介绍，包括创建型模式、结构型模式和行为型模式。每种设计模式都有详细的概念讲解、案例说明、代码实例以及运行截图。作者通过这些模式的介绍，旨在帮助读者更好地理解源码、编写更优雅的代码，并进行系统重构。同时，文章还提供了GitHub上的源码地址，方便读者直接访问和学习。
热爱技术的小郑
6 0
常用设计模式介绍~~~ Java实现 【概念+案例+代码】
众所周知
|
1天前
|
Java 开发者
在Java编程的广阔天地中，if-else与switch语句犹如两位老练的舵手，引领着代码的流向，决定着程序的走向。
在Java编程中，if-else与switch语句是条件判断的两大利器。本文通过丰富的示例，深入浅出地解析两者的特点与应用场景。if-else适用于逻辑复杂的判断，而switch则在处理固定选项或多分支选择时更为高效。从逻辑复杂度、可读性到性能考量，我们将帮助你掌握何时选用哪种语句，让你在编程时更加得心应手。无论面对何种挑战，都能找到最适合的解决方案。
众所周知
6 1
AI之家
|
2天前
|
机器学习/深度学习 人工智能 算法
【人工智能】传统语音识别算法概述，应用场景，项目实践及案例分析，附带代码示例
传统语音识别算法是将语音信号转化为文本形式的技术，它主要基于模式识别理论和数学统计学方法。以下是传统语音识别算法的基本概述
AI之家
11 2
VipSoft
|
5天前
|
Java
MQTT(EMQX) - Java 调用 MQTT Demo 代码
MQTT(EMQX) - Java 调用 MQTT Demo 代码
VipSoft
9 0
MQTT(EMQX) - Java 调用 MQTT Demo 代码

热门文章

最新文章

  • 1
    一文让你了解AI产品的测试 评价人工智能算法模型的几个重要指标
  • 2
    经典算法题--求对策字符串的最大长度(第二版)
  • 3
    [算法题] 人民币大小写转换（阿拉伯数字和汉字转换）
  • 4
    “SRTT” DNS服务器选择算法介绍
  • 5
    字符串匹配算法之BF(Brute-Force)算法
  • 6
    一个从四秒到10毫秒，花了1年的算法问题？
  • 7
    JavaScript的6个算法实用小技巧
  • 8
    经典算法题每日演练——第二十五题 块状链表
  • 9
    如何让用户找到想要的内容？阿里文娱搜索算法实践
  • 10
    当年参加飞思卡尔自己写的双线识别算法
  • 1
    Java并发编程：理解并应用ReentrantLock
    42
  • 2
    Java并发编程：深入理解线程池
    24
  • 3
    Java 8新特性解析及应用区块链技术在供应链管理中的应用与挑战
    39
  • 4
    Java 效率编码 必备插件 Lombok 让代码更优雅
    21
  • 5
    Java代码一键生成数据库文档（案例详解）
    124
  • 6
    java一行代码实现RESTFul接口
    41
  • 7
    Java远程连接本地开源分布式搜索引擎ElasticSearch
    31
  • 8
    Spring Boot单元测试报错java.lang.IllegalStateException: Could not load TestContextBootstrapper [null]
    79
  • 9
    Java并发编程：深入理解线程池
    32
  • 10
    Java中 a+=b和a=a+b有什么区别？
    25

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 基于ECS搭建Java Web开发环境
  • 使用Aliyun Java Intializr进行项目开发
  • 搭建Java Web开发环境
  • 部署基于Dragonwell的Java运行环境
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
    • 下一篇
    通义千问API入门教程