“365算法每日学计划”:05打卡-图解冒泡排序(多解法)

一、思路

在进行冒泡法排序(升序)时,需要将数组元素(len)两两比较,如果 前面的元素大于后面的元素,则交换两个数,否则,比较下一个元素和它的下一个元素的大小,依次执行,执行一次循环,可以找到当前数组中最大的一个元素,然后问题规模变小,然后找出len-1个元素里的最大值,使之成为第二大元素,依次执行,需要在外层嵌套一层循环。

二、优化

考虑如果数组中的数据已经是排好序的,那么就不需要遍历那么多次,定义一个标志位,如果没有执行交换,则说明数组中的元素已经排好序了,这时直接跳出循环。

三、图解

这里写图片描述

四、代码实现

假如有几个数字int score[] = {67, 69, 75, 88}; 按照从大到小排序。

有2种思路

第一种score[j]score[j+1] 比较 如果 前者比后者小,把前者和后者调换顺序,两两调换后一轮下来 最小的会被排到最后去。每一轮j都从0开始,当i轮排序,就有最后面的i个数字因为他是最小的,所以后面的每轮都不用理他了,也就是 score.length-1-i 往后的数不用管了,如上,第一轮有4个数字 i为0 ,那么score.length-1-i 为3,也就是下标是3以后的可以不用管,3往后没有数字,所以第一轮所有的数字都要参加比较,第二轮I=1 score.length-1-i 为2 也就是说 下标2后面的 下标为3的数字不用比了,因为两两比较厚,67会到 score[3],实现代码如下:

 for(int i =0;i < score.length - 1;i++)  
            {  
                for(int j = 0;j <  score.length - 1-i;j++)// j开始等于0,  
                {  
                    if(score[j] < score[j+1])  
                    {  
                        int temp = score[j];  
                        score[j] = score[j+1];  
                        score[j+1] = temp;  
                    }  
                }  
            }  

第二种思路,用88 和 75 比较,在和69 比较 在和 67 比较,发现88是最大的,吧他排到第一位(index=0的位置),然后i=1,也就是第二轮,就不用看下标为0的88了因为他是老大,然后接着比较。;

    for(int i =0;i < score.length - 1;i++)  
            {  
                for(int j = (score.length - 2);j >= i;j--)  
                {  
                    if(score[j] < score[j+1])  
                    {  
                        int temp = score[j];  
                        score[j] = score[j+1];  
                        score[j+1] = temp;  
                    }  
                }  
            }  

说明下j为啥=

 (score.length - 2)

因为length=4,我最多能让下标2和下标3的数字比较(j+1最大等于3),也就是4-2=2 j最大=2,2和2+1比较 然后1和2比较,然后 0和1 比较。

五、时间复杂度分析

最好的情况下时间复杂度为O(n):当待排序的数据已经按顺序排好的情况下

最坏的情况下时间复杂度为O(n^2):因为要比较n-1趟,,每一趟又要比较(n-1-i)次

参考资料
  • https://blog.csdn.net/qq_34992845/article/details/53271184
  • https://blog.csdn.net/shuaizai88/article/details/73250615

原文发布于微信公众号 - 好好学java(SIHAIloveJAVA)

原文发表时间:2018-06-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

1031
来自专栏和蔼的张星的图像处理专栏

488. 快乐数

一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

1573
来自专栏赵俊的Java专栏

搜索插入位置

1701
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

1963
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

1581
来自专栏韦弦的偶尔分享

Swift 旋转数组 - LeetCode

例如,如果 n = 7 , k = 3,给定数组 [1,2,3,4,5,6,7] ,向右旋转后的结果为 [5,6,7,1,2,3,4]。

1675
来自专栏python3

python random模块

随机输出一个0~4的数字和range()输出的数字,去比较。猜对了,就是字母,否则是数字

822
来自专栏机器学习从入门到成神

2014百度研发真题及其解析-求比指定数大且最小的“不重复数”

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1462
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

3367
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

3069

扫码关注云+社区

领取腾讯云代金券