专栏首页ACM算法日常基础算法系列之排序算法-2.冒泡排序

基础算法系列之排序算法-2.冒泡排序

上篇文章给大家讲述了二分查找算法,现在让我们来一起学习另一个基础算法——冒泡排序算法。它是一个排序算法,可以将一个无序的序列排成有序。它将会是我们以后常用到的算法,所以学会它,用好它对我们以后学习高级算法是很有益处的,那让我们开始冒泡排序算法的学习吧。


冒泡排序

冒泡排序,顾名思义,就像冒泡泡一样,不断将小的数往上"冒"(左移),大的数不断往下"坠落"(右移),最终得到一个一个有序的序列。它是一种简单的排序算法。


冒泡排序的算法思想

通过两两比较相邻的数,如果发现这两个数不满足次序要求使,则将这两个数进行交换,从而实现"冒泡"。


冒泡排序的实现过程

从序列的最后一个数开始,不断地将小的数往上冒,通过n-1(假设有n个数)次循坏之后,这组序列就成了一个有序的序列。


代码实现

public static void bubbleSort (int[] a) {
        for(int i =0;i<a.length-1;i++)  //控制循坏的次数为n-1次
            for(int j = a.length-1;j>i;j--){  //从序列的最后一个数开始,逐渐将小的数往上"冒"
                if(a[j]<a[j-1]){
                    a[j] = a[j-1]+a[j]-(a[j-1]=a[j]);   //将两个数进行交换,也可以通过中间值temp进行交换
                }
            }
    }

运行下面代码,让我们来进行测试一下吧。

public static void main(String[] args) {
        int[] a = new int[]{4,3,2,1,8,6,5,10};
        bubbleSort(a);
        for(int i =0;i<a.length;i++){
            System.out.print(a[i]+"  ");
        }
        System.out.println();
    }

是不是与预期的一样呢?!其实还有第二种实现冒泡排序的方法,就是你可以这样想,它既然是从最后一个数开始逐渐将小的数往上"冒",那我们可不可以从第一个数开始,逐渐将大的数往下"坠落"呢?抱着这种想法让我们来试试吧。

public static void bubbleSort(int[] a ) {
        for(int i=0;i<a.length-1;i++)  //控制循坏的次数为n-1次
            for(int j=0;j<a.length-1-i;j++){   //从序列的第一个数开始,逐渐将大的数往下坠落
                if(a[j]>a[j+1]){
                    a[j] = a[j] + a[j+1] -(a[j+1] = a[j]);   //将两个数进行交换,也可以通过中间值temp进行交换
                }
            }
    }

让我们继续用上面的测试代码来测试看看吧。

果然,和我们预期的一样,大家以后学习算法的时候也可以逆着想想,看看能不能达到一样的效果,这就是所谓的逆向思维嘛,既然我们已经学了冒泡排序算法,那让我们来做道题,试试手吧。


HDU 2689 Sort it

Problem Description

You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need. For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

Output

For each case, output the minimum times need to sort it in ascending order on a single line.

Sample Input

3 
1 2 3 
4 
4 3 2 1

Sample Output

0 6

问题大意:排序一个序列,并统计要进行交换的次数。

问题分析:这道题是不是让我们想起了之前我们测试用的例子,用我们刚才学习的冒泡排序算法,只要在两个数交换顺序的时候,添加一个计数器count,不就完成了题目的要求嘛。

代码实现:

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入元素个数:");
        int n = input.nextInt();
        int[] a = new int[n]; //定义数组来存储我们输入的值
        System.out.println("请依次输入元素:");
        for(int i =0;i<n;i++){
            a[i] = input.nextInt();
        }
        int count=0;  //定义计数器count
        count = bubbleSort(a);
        for(int i =0;i<a.length;i++){
            System.out.print(a[i]+"  ");
        }
        System.out.println();
        System.out.println("需要交换的次数为:"+count);
    }

    public static int bubbleSort(int[] a ) {
        int count=0; //定义计数器count
        for(int i=0;i<a.length-1;i++)  //控制循环次数为n-1次
            for(int j=0;j<a.length-1-i;j++){ //从序列的第一个数开始,逐渐将大的数往下"坠落"
                if(a[j]>a[j+1]){
                    a[j] = a[j] + a[j+1] -(a[j+1] = a[j]); //将两个数进行交换,也可以通过中间值temp进行交换
                    count++; //计数器自增
                }
            }
        return count;
    }

让我们来测试一下吧。

总述

通过以上的学习,你是否学会了冒泡排序算法呢~相信以你的聪明才智肯定学会了ヾ(◍°∇°◍)ノ゙

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:Pimithe

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-05

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ-3275:奶牛排序Ranking the Cows(Floyd、bitset)

    Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positi...

    ACM算法日常
  • 对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

    本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的(保证了这个点的距离就是最短路),如果有负边权,当前找到的就不一定是最近的了。

    ACM算法日常
  • POJ1258:Agri-Net-最小生成树

    Farmer John has been elected mayor of his town! One of his campaign promises was...

    ACM算法日常
  • 图论--最短路--Floyd(含路径输出)

    风骨散人Chiam
  • C++-入门语法(二)

    cwl_java
  • hdu1014

    @坤的
  • Integer Inquiry UVA-424(大整数)

    _DIY
  • c++之内存模型

    堆区:由程序员分配释放,若程序员不释放,则程序结束时由系统释放。在c++中主要利用new在堆区开辟内存。

    绝命生
  • C++核心准则ES.64:使用T{e}记法构造对象

    The T{e} construction syntax makes it explicit that construction is desired. The...

    面向对象思考
  • 剑指offer第11题:机器人运动范围

    此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。

    鹏-程-万-里

扫码关注云+社区

领取腾讯云代金券