[数据结构与算法]【算法入门系列】冒泡排序

活动地址：CSDN21天学习挑战赛

算法入门系列-冒泡排序

一、冒泡排序的概念

冒泡排序的基本思路是最后面的元素开始，对每两个相邻的关键字进行比较，且使关键字较小的元素换至关键字较大的元素之前，使得一趟冒泡排序后关键字最小的元素到达最上端, 接着，在剩下的元素中找关键字次小的元素，并把它换到第二个位置上,遍历n-1趟之后整个数组变为有序的

二、算法分析

1. 数据结构:数组

2. 输入:5,4,3,2,1

3. 算法实现:

• 创建一个n-1次的循环实现n-1趟排序
• 每趟排序都要创建一个循环用于从后往前交换元素位置,将无序区最小元素排到前面的有序区

4. 输出:1,2,3,4,5

5. 算法的时间复杂度:O(n²)

6. 算法的空间复杂度:O(1)

三、算法实现(java)

    private static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = arr.length-1; j > i; j--) {
                if (arr[j]<arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
        return arr;
    }

有些时候在排到第i (i<n-1)趟的时候,所有的元素已经排好,而程序还会执行,所以算法还可以优化,改进的算法如下:

private static int[] bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length-1; i++) {
        boolean exchange = false;
        for (int j = arr.length-1; j > i; j--) {
            if (arr[j]<arr[j-1]){
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                exchange = true;
            }
        }
        if (!exchange){
            break;
        }
    }
    return arr;
}

四、分析

1. 冒泡排序和直接选择排序的思路大题一致,都是从无序区找到最小元素排到前面的有序区,但是区别是冒泡排序是不断地与前面元素交换位置从而将最小元素排到有序区,而直接排序是将最小元素直接与无序区第一个元素交换位置. 冒泡排序还会在后面的无序区进行排序,减少后面的工作量

写在结尾: 冒泡排序是我认识的第一个算法,大约是两年前的事了,当时学的时候还是懵懵懂懂,在经历了这么久的沉淀之后我惊奇的发现我竟然还没有忘,仔细想想原因应该是自己对算法的理解程度加深导致的。所以还得靠积累,每天都要进步一点点。

刚开始写博客，文章中难免会有纰漏，如有不足，欢迎各位批评指点。?
?

活动地址：CSDN21天学习挑战赛