数据结构与算法-冒泡排序

数据结构与算法-冒泡排序

核心思路： 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。package edu.sort; import cn.hutool.core.util.ArrayUtil; /** * 冒泡排序 * 时间复杂度：O(n^2) * 空间复杂度：O(n) * 思路：冒泡排序智慧操作相邻的的两个数据， * 每次冒泡操作都会对相邻的两个元素进行比较， * 看是否满足大小关系要求，不满足，则直接交换一次， * 一次冒泡会让至少一个元素移动到改在的位置 * 重复N此就完成了排序的工作 *

* 稳定排序 （没有等号） *

* 优化:加标记，如果已经是有序的队列，则直接跳出排序 * * @author: LHT * @date: 2020/12/20 17:13 */ public class BubbleSort { public static void main(String[] args) { long start = System.currentTimeMillis(); int a[] = {1, 23, 123, 54234, 121, 1, 231, 45, 1, 23}; //优化方案，加标记 for (int i = 0; i < a.length - 1; i++) { boolean flag = false; for (int j = 0; j < a.length - 1 - i; j++) { if (a[j] > a[j + 1]) { // //交换 // int temp = a[j + 1] + a[j]; // a[j] = a[j + 1]; // a[j + 1] = temp; //节省空间开辟 a[j] = a[j] + a[j + 1]; a[j + 1] = a[j] - a[j + 1]; a[j] = a[j] - a[j + 1]; flag = true; } } if (!flag) { break; } } System.out.println("用时：" + (System.currentTimeMillis() - start)); System.out.println(ArrayUtil.toString(a)); } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。