11、数据结构与算法 - 基础:排序算法之冒泡排序

1、冒泡排序基本介绍#

冒泡排序(Bubble Sorting)是一种简单的排序算法,通过重复循环要进行排序的元素,依次比较相邻元素的值,如果发现逆序就进行交换,使值较大的元素后移。

排序过程中,各元素不断接近自己的位置,如果一趟比较没有进行交换,说明序列是有序的,可以在排序过程中设置一个 flag 判断元素是否进行交换。

2、冒泡排序规则#

  • 一共进行数组大小 - 1 次循环
  • 每一趟排序的次数在逐渐减少,比较相邻元素的值,第一个比第二个大就进行交换
  • 持续对越来越少的元素进行比较,直到没有任何元素需要进行比较
  • 如果我们发现在某趟排序中,没有发生一次交换,可以提前结束冒泡排序

3、冒泡排序代码示例#

// 排序规则:从第一个下标位置开始,对相邻元素的值依次进行比较,大的值后移一位继续比较,直到比后一位元素小为止
int arr[] = {
   
     2,4,6,1,5,8, -3}; // 原始数组数据
int temp = 0;
// 进行一次排序,第一次排序,将数组内最大的数排在最后
for (int i = 0; i < arr.length - 1; i++) {
   
     
    // 前后相邻位置数进行比较,如果前面的数比后面的数大,进行交换
    if (arr[i] > arr[i + 1]) {
   
     
        temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
    }
}

冒泡排序具体实现:每次循环次数 arr.length - 1;

public static void main(String[] args) {
   
     
    int arr[] = {
   
     2,-1,6,1,5,8, -3}; // 原始数组数据
    int temp = 0;
    // 冒泡排序的时间复杂度为 O(n^2)
    // 外层循环控制遍历次数
    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]) {
   
     
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

原来顺序就是正常,或者一部分已经排好序了,可以通过标识符 flag 判断

public static void main(String[] args) {
   
     
    int arr[] = {
   
     2,-1,6,1,5,8, -3}; // 原始数组数据
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}
// 冒泡排序
public static void bubbleSort(int[] arr) {
   
     
    int temp = 0;
    boolean flag = false;
    for (int i = 0; i < arr.length; i++) {
   
     
        for (int j = 0; j < arr.length - i - 1; j++) {
   
     
            if (arr[j] > arr[j + 1]) {
   
     
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 通过标识符判断在排序中有没有进行过交换
        if (!flag) {
   
      // 进行过交换继续下一次
            break;
        } else {
   
      // 没有进行过交换,序列有序
            flag = false;
        }
    }
}