当前位置:网站首页>冒泡排序及冒泡排序的优化
冒泡排序及冒泡排序的优化
2022-01-15 02:32:07 【朝上】
思想:
一个for循环遍历数组,让arr[ i ]和arr[ i+1 ]比较,如果arr[ i ] > arr[ i+1 ]就产生交换,
每一轮比较下来就是将该数组中最大的数冒出来,第几轮就是找第几大
时间复杂度 O(n)2
public class BubbleDemo {
public static void main(String[] args) {
int[] arr = {
8,4,2,1,23,344,12};
//i 比较轮数
for (int i = 0; i < arr.length-1; i++) {
//j 次数
for (int j = 0; j < arr.length-i-1 ; j++) {
//比较
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
//输出
for (int a : arr) {
System.out.println(a);
}
}
}
优化:
针对轮进行优化
- 思想:因为如果到了某一轮完全不产生交换(即全数组不满足 arr[ i ] > arr[ i+1 ] ),则表明该数组已经有序,我们可以直接再次处停下比较,拿一个boolean标记处理就好
针对每轮里面的比较次数进行优化
- 思想:如果该数组比较特殊,即数组后部分已经有序,那程序会产生很多次无效比较,为了针对这种特殊情况的优化,基于冒泡排序第几轮找第几大的前提下,我们可以记录上一轮最后一次产生交换的位置,即已经找到了第x大(该数据下标记录为index),这一轮找第x-1大的数,我们可以只在前部分找(0-index)
public class BubbleSort {
public static void main(String[] args) {
//int[] arr={16,49,23,56,4,11,12};
int[] arr={
2,19,18,16,20,21,62};
int index=arr.length-1;
for (int i = 0; i < arr.length-1; i++) {
//控制轮数
boolean flag=true;//用来记录是否产生交换,没产生交换则表明元素已经有序
int n=index; //用来减少每一轮比较 后面有有序序列 的重复比较次数,因为冒泡排序每次找最大
for (int j = 0; j < n ; j++) {
//控制每轮次数
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag=false;
index=j;
}
System.out.println(Arrays.toString(arr));
System.out.println(index);
}
System.out.println();
if(flag) break;
}
}
}
版权声明
本文为[朝上]所创,转载请带上原文链接,感谢
https://blog.csdn.net/m0_51051154/article/details/120100099
边栏推荐
- Analyse des données tichoo
- Tiktok data analysis platform
- Partage de l'industrie | tichoo Data to attend 2022 Overseas Short video Industry Summit
- [ticoo Information Station] tiktok and Cross - Border E - commerce Weekly Report
- Options d'analyse des données ticoo {infostation}
- Partage de l'industrie | Lu Shidong, PDG de tichoo Data Outlook Global Video e - commerce future Blueprint
- [ticoo Information Station]
- Noël Black Five
- YC Framework version update: v1.0 zero point two
- Lucene分词器
猜你喜欢
随机推荐
- JVM系列 -- 深入剖析垃圾收集器
- JVM系列--内存回收
- JVM系列--对象内存分配技术分析
- JVM系列--虚拟机的内存管理
- 系统性能瓶颈排查技术总结
- 使用redis的scan指令详解
- 实战--分布式id发号器
- 分布式事务之超详细的Seata实践记录
- TCP time_wait
- IP数据报头部
- 最大基环内向树
- MySQL实战45讲 学习笔记(七)
- MySQL实战45讲 学习笔记(六)
- Android从零开始搭建MVVM架构(1)(1),kotlin匿名函数
- Android事件分发机制五:面试官你坐啊,安卓上机面试题
- There will be two different stages between the breakthrough of science and technology and its real transformation into an inclusive technology
- [leetcode] force deduction 200 Number of islands
- HashShuffleManager
- Spark shuffle concept
- Go controls the metadata of grpc
- Altium Designer
- Android Event Distribution Mechanism 5: interviewer, you sit, Android on the machine Interview Question
- Android construit l'architecture mvvm à partir de zéro (1) (1), fonction anonyme kotlin
- MySQL Real Game 45 talk Learning notes (6)
- MySQL Real Game 45 talk Learning notes (7)
- Module 6 operation of the actual combat camp
- Android事件分發機制五:面試官你坐啊,安卓上機面試題
- Arbre intérieur maximal de l'anneau de base
- En - tête du datagramme IP
- TCP Time Attendez.
- Android内容提供器读取手机中的音乐文件信息,百度、阿里、滴滴、新浪的面试心经总结
- Android修炼系列(十一),kotlin静态方法
- Seata Practice record for Distributed transactions
- RSA basic principle and common attack methods
- Incremental replication of table data between two database servers
- Android修煉系列(十一),kotlin靜態方法
- Android Culture Series (11), kotlin Static Method
- Le fournisseur de contenu Android lit les informations des fichiers musicaux dans le téléphone mobile, baidu, Ali, Didi, Sina interview Summary
- Pratique - Distributed ID commander
- Explication détaillée de l'instruction Scan avec redis