排序算法-01-冒泡排序排序算法-01-冒泡排序

Sep 14, 2017 | 排序

说明

该分类下的内容只是个人笔记而已，放这里只是为了方便查找，算不上博客。

非专业定义

每次比较两个元素，如果他们的顺序错误就把他们交换过来。

重复地进行直到没有元素再需要交换。

排序过程示例

[1, 3, 1, 4, 2, 7, 6, 2, 1] # input
[1, 1, 3, 1, 4, 2, 7, 6, 2] # 1
[1, 1, 1, 3, 2, 4, 2, 7, 6] # 2
[1, 1, 1, 2, 3, 2, 4, 6, 7] # 3
[1, 1, 1, 2, 2, 3, 4, 6, 7] # 4 其实到这里已经排好序了,但是不得不接着遍历,{最好,平均}时间复杂度是一样的
[1, 1, 1, 2, 2, 3, 4, 6, 7] # 5
[1, 1, 1, 2, 2, 3, 4, 6, 7] # 6
[1, 1, 1, 2, 2, 3, 4, 6, 7] # 7
[1, 1, 1, 2, 2, 3, 4, 6, 7] # 8
[1, 1, 1, 2, 2, 3, 4, 6, 7] # output

代码示例

public void sort(int[] arr) {
  
  for (int i = 1; i < arr.length; i++) {
    for (int j = arr.length - 1; j >= i; j--) {
      if (arr[j - 1] > arr[j])
        SortUtils.swap(arr, j - 1, j);
    }
  }
  
}

特点

平均时间复杂度 O(n^2)
最差时间复杂度 O(n^2)
空间复杂度 O(1)

排序