美文网首页程序员
优化冒泡排序(JAVA)

优化冒泡排序(JAVA)

作者: 林天涯 | 来源:发表于2018-01-02 17:57 被阅读0次

算法


  冒泡排序作为最基础最简单的排序算法,实质是相邻两元素比较,若有序则跳过,若无序则交换。最多需n-1趟排序,第i趟需比较n-i次。所以时间复杂度为o(n*n),是一种比较低效率的排序算法。不过对于初学者来说是必须掌握的一种算法。
  冒泡排序有一点可以改进的地方,初学者可能没注意到。就是当序列已经整体有序时,就不需要再作不必要的比较了。可以设置一个布尔变量,当一趟下来未发生交换时,直接跳出循环,能够提高排序效率。

Codes


package com.fairy.InnerSort;

import java.util.Scanner;
/**
 * 冒泡排序
 * @author Fairy2016
 *
 */
public class BubbleSort {
    
    public static void sort(int a[], int n) {
        boolean flag = false;
        for(int i = 1; i <= n-1; i++) {
            flag = false;
            for(int j = 1; j <= n-i; j++) {
                if(a[j] > a[j+1]) {
                    //交换a[j]与a[j+1]
                    a[0] = a[j];
                    a[j] = a[j+1];
                    a[j+1] = a[0];
                    //标记发生了交换
                    flag = true;
                }
            }
            //若未发生交换,直接退出,排序已完成
            if(!flag) {
                break;
            }
        }
    }

    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
        scanner.close();
    }
}

相关文章

  • 冒泡排序的C语言实现

    冒泡排序 优化后的冒泡排序

  • 经典排序算法总结

    经典排序算法集锦 冒泡法 排序算法入门之冒泡排序 排序算法入门之冒泡排序优化

  • 优化冒泡排序(JAVA)

    算法   冒泡排序作为最基础最简单的排序算法,实质是相邻两元素比较,若有序则跳过,若无序则交换。最多需n-1趟排序...

  • 冒泡排序(ios和前端script)

    ios之冒泡排序 未优化之前 优化之后 前端冒泡排序(与上同理) 方式一: 方式二:

  • 排序算法-swift实现

    1.冒泡排序 时间复杂度:O(n^2) 1.1初级 1.2正宗冒泡排序 1.3冒泡排序优化 问题:排序过程中,如果...

  • 排序算法-2(javascript) 快速排序的实现

    快速排序 快速排序是冒泡排序的优化,与冒泡排序不同的是,使用了分治法,进行优化。会随机选取一个值pivot(基准元...

  • Python之算法LOB三人组

    一、冒泡排序 a、冒泡排序----优化 如果冒泡排序中执行一趟而没有交换,则列表已经是有序状态,可以...

  • Java入门--冒泡排序

    Java入门--冒泡排序

  • 双线程冒泡排序算法

    双线程冒泡排序算法是对冒泡排序的优化,对冒泡排序加入了另外一个线程。 冒泡排序可以从数组的第0个元素开始排列,同样...

  • 从0开始——排序

    0.排序的复杂度比较 1.冒泡排序 冒泡排序基础版本1 正宗冒泡排序优化版本 2.选择排序 3.插入排序算法 4....

网友评论

    本文标题:优化冒泡排序(JAVA)

    本文链接:https://www.haomeiwen.com/subject/qbjqnxtx.html