数据结构和算法-9-冒泡排序

你的名字 2022-01-12 02:03 115阅读 0赞

开始学习最简单的几个排序算法，学习完排序算法，就要学习二叉树。其实我曾经也想到过去刷题，但是我看一下题目之后，我还是觉得很有必要回来复习下数据结构和算法的入门基础知识。冒泡排序很重要，特别是对于测试人员，很多公司不能拿太复杂的算法去考察测试人员，冒泡就成了大概率要会写的代码。

1.什么是冒泡排序

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

2.冒泡排序的过程和图解分析

冒泡排序算法的运作如下：  
1）比较相邻的元素，如果第一个比第二个大（升序），就交换他们两个位置。  
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完，最后的元素会是最大的数。  
3）针对所有的元素重复以上步骤，除了最后一个。  
4）持续每次对越来越少的元素重复上面步骤，直到没有任何一对数字需要比较。

下面这个图，表示第一个步骤和第二个步骤的过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

上面一遍走下来之后，确保最大的数字93已经排到最末尾了，下次就排序93之前的数据就可以。依次，第二次走完一遍，数字77会放到93的前面，也就是整个数列倒数第二个位置。以此类推，每下一次要排序的数列都会缩短一个元素，需要交换的次数也越来越小，直到不需要交换位置，这个时候排序结束。

3.冒泡排序代码实现

先来看看python代码实现

def bubble_sort(alist):
        n = len(alist)
        for i in range(0, n - 1):
            for j in range(0, n-i-1):
                if alist[j] > alist[j + 1]:
                    alist[j], alist[j + 1] = alist[j + 1], alist[j]
    
    
    if __name__ == "__main__":
        alist = [3, 89, 35, 56, 19, 29, 1]
        print(alist)
        bubble_sort(alist)
        print(alist)

运行结果

[3, 89, 35, 56, 19, 29, 1]
    [1, 3, 19, 29, 35, 56, 89]

再看看Java代码实现

import java.util.Arrays;
    
    public class BubberSort {
    
        public static void main(String[] args){
            int[] arr = {3, 89, 35, 56, 19, 29, 1};
            mySort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void mySort(int[] arr){
            int tmp;
            for (int i =0; i < arr.length -1; i ++){
                for(int j=0; j < arr.length -1-i; j ++){
                    if(arr[j] > arr[j+1]){
                        tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                    }
                }
            }
        }
    }

上面在打印输出的时候，我偷懒没用for循环遍历排序后的元素，直接用Arrays这个类，其实这个类有一个sort方法，支持排序的。如果面试的时候，关于排序没有指明特定排序算法，你就可用这个类的sort方法进行排序。

[1, 3, 19, 29, 35, 56, 89]

关于上面写的冒泡排序算法的时间复杂度，由于我们使用两层嵌套for循环，所以最差的时间复杂度是O(n^2). 这里我们优化一下，如果传入的一个列表刚刚是排序好的，使用我们的冒泡排序算法，时间复杂度依然是O(n^2)，这个就不合理了，修改如下。

def bubble_sort(alist):
        n = len(alist)
        for i in range(0, n - 1):
            count = 0
            for j in range(0, n-i-1):
                if alist[j] > alist[j + 1]:
                    alist[j], alist[j + 1] = alist[j + 1], alist[j]
                    count += 1
            if 0 == count:
                break
    
    
    if __name__ == "__main__":
        alist = [1, 3, 19, 29, 35, 56, 89]
        print(alist)
        bubble_sort(alist)
        print(alist)

Java那边就不写这个，看得懂这个count的作用就行，就是为了能处理，以及排好序的数列，防止处理有序的数列时间复杂度还是O(n^2)，这样的时间复杂度就是O(n).

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20220109/96335fc4dcbb458eaea22b9afee2e144.png