冒泡排序

思想： 不断地从头到尾的比较前后两个数

  • 如果前面的数大于后面的数，则执行交换两个元素，然后继续往后比较
  • 如果前面的数小于或等于后面的数，则直接往后继续比较

冒泡排序 - 图1
每一次冒泡的过程都会将当前数组的最大值放到当前数组的最后一个位置。 因此，通过为了减少比较的次数。每次冒泡排序数组的长度都是上一轮数组长度减一。

时间复杂度：
冒泡过程需要比较
冒泡排序 - 图2冒泡排序 - 图3%20%3D%20O(N)#card=math&code=O%28N%20%2A%201%29%20%3D%20O%28N%29)冒泡排序 - 图4%20%3D%20O(N%20%5E%202)#card=math&code=O%28N%20%2A%20N%29%20%3D%20O%28N%20%5E%202%29)

空间复杂度：

排序过程不申请额外的空间，因此空间复杂度为O(1)

稳定性：
如果两个元素相等，那么冒泡过程不执行交换操作，因此谁在前谁在后都是一样的。因此，冒泡排序是稳定的。

Java代码实现：

  1. public int[] BubbleSort(int[] arr){
  2.     if(arr.length  < 2){
  3.         return arr;
  4.     }
  6.     for (int i = 0; i < arr.length - 1; i++) {
  7.         // 哨兵
  8.         boolean flag = true;
  9.         for(int j = 0; j < arr.length - 1 - i; j++){
  10.             if(arr[j] > arr[j + 1]){
  11.                 swap(arr, j, j+ 1);
  12.                 flag = false;
  13.             }
  14.         }
  15.         // 如果此次没有发生交换，说明数组已经有序
  16.         if(flag == true){
  17.             break;
  18.         }
  19.         System.out.println(Arrays.toString(arr));
  20.     }
  21.     return arr;
  22. }
  24. public void swap(int[] arr, int i, int j) {
  25.     int temp = arr[i];
  26.     arr[i] = arr[j];
  27.     arr[j] = temp;
  28. }

Python代码实现

  1. def bubble_sort(nums):
  2.     l = len(nums)
  3.     for i in range(0, l - 1):
  4.         flag = True
  5.         for j in range(0, l - i):
  6.             if nums[j] > nums[j + 1]:
  7.                 nums[j], nums[j + 1] = nums[j + 1], nums[j]
  8.                 flag = False
  9.         print('index: {} -- {}'.format(i, nums))
  11.         # flag用于标记当前轮是否有元素的交换执行
  12.         if flag == True:
  13.             return nums
  15.     return nums
  17. if __name__ == "__main__":
  18.     nums = [5, 2, 9, 7, 6, 12, 3, 4]
  20.     # 冒泡排序
  21.     print('-' * 20)
  22.     print ('bubble sort result is: ', bubble_sort(nums))