java 冒泡排序

Wesley13
• 阅读 562

思路

  1. 将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;( 第一轮结束后,序列最后一个元素一定是当前序列的最大值;)
  2. 对序列当中剩下的n-1个元素再次执行步骤1。
  3. 对于长度为n的序列,一共需要执行n-1轮比较

时间复杂度

最佳情况:T(n) = O(n) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

代码

import java.util.Arrays;

/**
 * 冒泡排序
 * @author remainsu
 * @version 1.0 2019-05-29
 */
public class BubbleSort {

    /**
     * 排序方法
     * @param arr 要排序的数组
     * @return toString 方便输出
     */
    public static String bubbleSort(int[] arr) {

        int tmp;
        //int count = 0;
        // 冒泡次数
        for(int a=0; a<arr.length-1; a++ ) {
            
            //count = a+1;
            boolean flag = false;
            // 比较未移动的
            for(int b=0; b<arr.length-a-1; b++ ) {
                // 后面的小于前面的,则互换位置
                if(arr[b+1] < arr[b]) {
                    tmp = arr[b];
                    arr[b] = arr[b+1];
                    arr[b+1] = tmp;
                    
                    //有数据移动,则状态标位true
                    flag = true;
                }
            }
            //没有数据移动,即数组已经有序,直接退出
            if(!flag) break;
        }
        
        //System.out.println("冒泡的次数:"+ count);
        return Arrays.toString(arr);
    }
    
    public static void main(String[] args) {
        
        int[] arr = {111, 3, 5, 52, 74, 312, 75, 3, 764, 3, 2111, 7, 31};
        //int[] arr = {1,2,10,3,4,5,6,7,8,9};
        
        System.out.println("排序后的数组:"+ bubbleSort(arr));
    }
    

参考

  1. https://blog.csdn.net/hellozhxy/article/details/79911867
点赞
收藏
评论区
推荐文章
待兔 待兔
2星期前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
BichonCode BichonCode
3年前
List集合
Java的List集合一、ArrayList1.插入java/在元素序列尾部插入/publicbooleanadd(Ee){//1.检测是否需要扩容ensureCapacityInternal(size1);//IncrementsmodCount//2.将新元素插入序列尾
Wesley13 Wesley13
2年前
JAVA 中数组的几种排序方法
1、数组的冒泡排序publicvoidbubbleSort(inta){intna.length;for(inti0;i<n1;i){for(intj0;j<n1;j)
Stella981 Stella981
2年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Wesley13 Wesley13
2年前
Java面试总结(排序算法)
1.冒泡排序算法描述:两两比较,大的放后面2.选择排序算法描述:在m元数组中找到最小值的位置,然后将最小值的位置和第n(n0,1,2,....m1)位的值对调,排序k次则m元数组中前k(k<m)位的值已经排序好,m元数组中前k位的值不需要再进行排序,此时需要排序的元素只有mk个3.插入排序算
Wesley13 Wesley13
2年前
AGC 041D
考虑限制一定是对于前缀和后缀的,并且显然相交的前后缀可以不考虑。然后还可以发现只用考虑最长的那一段的条件,即$\\lfloor\\frac{n1}{2}\\rfloor$和$\\lfloor\\frac{n1}{2}\\rfloor1$的长度。可以将原序列分成两个部分。如下:$${AA|(C)|B}$$我们把
Wesley13 Wesley13
2年前
BFPRT线性查找算法
介绍:BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂度,五位算法作者做了精妙的处理。时间复杂度O(N)算法步骤
Stella981 Stella981
2年前
Lua 排序算法
冒泡排序(BubbleSort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。算法步骤1.有一个长度为n
菜园前端 菜园前端
1年前
什么是顺序搜索?
原文链接:什么是顺序搜索?顺序搜索是一种比较低效的搜索算法,但是实现起来相对简单。主要步骤如下:1.遍历数组2.找到跟目标值相等的元素,就返回它的下标3.遍历结束后,如果没有搜索到目标值,则返回1基础案例时间复杂度:O(n)空间复杂度:O(1)javasc
京东云开发者 京东云开发者
8个月前
时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队
归并排序归并排序遵循分治的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下:划分:分解待排序的n个元素的序列成各具n/2个元素的两个子序列,将长数组的排序问题转换为短数