冒泡排序&选择排序

发表于 | 更新于 | 分类于

本篇介绍冒泡排序、选择排序两种排序算法

冒泡排序

冒泡排序（Bubble Sort）:是一种简单的交换排序方法，它通过两两比较相邻记录的关键子，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐网上“漂浮”（左移），或者使关键字大的记录如石块一样逐渐向下“坠落”（右移）。

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

动画演示

图片来源：https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg

冒泡排序

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class BubbleSort {
    public static void bubbleSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }

        for(int i = 0; i< arr.length-1; i++){
            for(int j = i+1; j < arr.length; j++){
                if(arr[i] > arr[j]){
                    swap(arr, i, j);
                }
            }
        }
    }
    public static void swap(int[]arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
算法改进

标志变量用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换，说明序列已经有序了，不必继续进行下去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort_imp(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    boolean flag  = true;
    for(int i = 0; i< arr.length-1 && flag; i++){
        for(int j = i+1; j < arr.length; j++){
            if(arr[i] > arr[j]){
                swap(arr, i, j);
                flag = true;
            }
        }
    }
}
算法分析

  1. 时间复杂度

    当原始序列“正序”排列时，冒泡排序总的比较次数为$n-1$，移动次数为0，也就是说冒泡排序在最好情况下的时间间复杂度为$O(n)$；

    当原始序列“逆序”排序时，冒泡排序总的比较次数为$n(n-1)/2$，移动次数为$3n(n-1)/2$次，所以冒泡排序在最坏情况下的时间复杂度为$O(n^2)$；

    所在在平均情况下冒泡排序的平均时间复杂度为$O(n^2)$。

  2. 空间复杂度

    冒泡排序排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)。

  3. 算法特点：

    1. 冒泡排序是一种稳定的排序算法。
    2. 可用于链式存储结构
    3. 移动记录次数较多，算法平均时间性能比较直接插入排序差。当初始记录无序，n较大时，此算法不宜采用。

选择排序

　简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，

算法步骤
  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  • 重复第二步，直到所有元素均排序完毕。
动画演示

选择排序

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class SelectSort {
    public static void selectSort(int[] arr){
        if(arr == null && arr.length < 2){
            return;
        }
        for(int i = 0; i < arr.length - 1; i++){
            // 用于存放较小元素的数组下标
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            //如果minIndex 未发生变化，则不需要交换
            if(minIndex != i){
                swap(arr, i, minIndex);
            }   
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
算法分析

  1. 时间复杂度

    最好情况（正序）：不移动；最坏情况（逆序）：移动3(n-1)此。所以选择排序的时间复杂度也是$O(n^2)$

  2. 空间复杂度

    只有在两个记录交换时需要一个辅助空间，所以空间复杂度为O(1)。

  3. 算法特点

    1. 选择排序是一种不稳定的排序
    2. 可用于链式存储结构
    3. 移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序块。
0%