小胡博客

冒泡排序及其优化

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

平均时间复杂度 n^2 最坏的时间复杂度 n^2 最好时间复杂度n 空间复杂度1 稳定性 稳

代码:

最简单的代码

package com.xiaohu.suanfa.sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 小胡哥哥
 * NO BB show your code
 *
 * 简单版，无优化
 */
public class BubbleSort {
    public static void main(String[] args) {
        print();
    }

    private static void print() {
        int[] array = getArray();
        System.out.println("排序之前的数组:" + Arrays.toString(array));
        long startTime = System.currentTimeMillis();
        int[] sort = sort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("排序之后的数组:" + Arrays.toString(sort));
        System.out.println("总共花费:"+(endTime-startTime)+"毫秒");
    }

    private static int[] getArray() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一串数字，以,为 间隔");
        String str = sc.nextLine();
        //以,切割获得数组
        String[] strArray = str.split(",");
        int[] arr = new int[strArray.length];
        for (int i = 0; i < strArray.length; i++) {
            //将原先的字符串数组转换为数字数组
            arr[i] = Integer.parseInt(strArray[i]);
        }
        return arr;
    }
    //进行数组排序

    private static int[] sort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length-1; i++) {
            System.out.println("这是第"+(i+1)+"次轮回");
            for (int j=0;j<arr.length-1-i;j++) {
                 if (arr[j]>arr[j+1]) {
                     temp = arr[j];
                     arr[j] = arr[j+1];
                     arr[j+1] = temp;
                 }
                System.out.println("这是第"+(j+1)+"次遍历"+Arrays.toString(arr));
            }
        }
        return arr;
    }
}

简单优化:

package com.xiaohu.suanfa.sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 小胡哥哥
 * NO BB show your code
 * 优化版设置flag标志位
 * 缺点:之后的数组范围仍然遍历了
 */
public class BubbleSortPlus {

    public static void main(String[] args) {
       print();
    }

    private static int[] getArray() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一串数字，以,为 间隔");
        String str = sc.nextLine();
        //以,切割获得数组
        String[] strArray = str.split(",");
        int[] arr = new int[strArray.length];
        for (int i = 0; i < strArray.length; i++) {
            //将原先的字符串数组转换为数字数组
            arr[i] = Integer.parseInt(strArray[i]);
        }
        return arr;
    }

    private static void print() {
        int[] array = getArray();
        System.out.println("排序之前的数组:" + Arrays.toString(array));
        long startTime = System.currentTimeMillis();
        int[] sort = sort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("排序之后的数组:" + Arrays.toString(sort));
        System.out.println("总共花费:"+(endTime-startTime)+"毫秒");
    }

    private static int[] sort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length-1; i++) {
            //标记，当为true,则代表已经发生交换
            System.out.println("这是第"+(i+1)+"次轮回");
            boolean flag = true;
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            System.out.println("这是第"+(j+1)+"次遍历"+Arrays.toString(arr));
            }
            if (flag) {
                //当为true则结束比较，代表已经交换
                break;
            }
        }
        return arr;
    }
}

再加工:

package com.xiaohu.suanfa.sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 小胡哥哥
 * NO BB show your code
 * 优化版设置flag标志位,并且还设置无序的边界
 */
public class BubbleSortPluss {


    public static void main(String[] args) {
       print();
    }

    private static int[] getArray() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一串数字，以,为 间隔");
        String str = sc.nextLine();
        //以,切割获得数组
        String[] strArray = str.split(",");
        int[] arr = new int[strArray.length];
        for (int i = 0; i < strArray.length; i++) {
            //将原先的字符串数组转换为数字数组
            arr[i] = Integer.parseInt(strArray[i]);
        }
        return arr;
    }

    private static void print() {
        int[] array = getArray();
        System.out.println("排序之前的数组:" + Arrays.toString(array));
        long startTime = System.currentTimeMillis();
        int[] sort = sort(array);
        long endTime = System.currentTimeMillis();
        System.out.println("排序之后的数组:" + Arrays.toString(sort));
        System.out.println("总共花费:"+(endTime-startTime)+"毫秒");
    }

    private static int[] sort(int[] arr) {
        int temp;
        //设置无序边界，遍历到这后面不再遍历
        int unorderedArray = arr.length-1;
        //设置最后交换的位置
        int lastIndexSwap = 0;
        for (int i = 0; i < arr.length-1; i++) {
            //标记，当为true,则代表已经发生交换
            System.out.println("这是第"+(i+1)+"次轮回");
            boolean flag = true;
            for (int j = 0; j < unorderedArray; j++) {
                if (arr[j]>arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                    //记录当期最后一次的交换位置
                    lastIndexSwap = j;
                }
                System.out.println("这是第"+(j+1)+"次遍历"+Arrays.toString(arr));
            }
            //进行交换，把最后一次交换的位置赋值给无序边界，之后就不用再遍历
            unorderedArray = lastIndexSwap;
            if (flag) {
                //当为true则结束比较，代表已经交换
                break;
            }
        }
        return arr;
    }
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦