Bubble Sort
最后更新于：2022-04-02 01:06:42
# Bubble Sort - 冒泡排序
核心：**冒泡**，持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。
### Implementation
### Python
~~~
#!/usr/bin/env python
def bubbleSort(alist):
for i in xrange(len(alist)):
print(alist)
for j in xrange(1, len(alist) - i):
if alist[j - 1] > alist[j]:
alist[j - 1], alist[j] = alist[j], alist[j - 1]
return alist
unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
print(bubbleSort(unsorted_list))
~~~
### Java
~~~
public class Sort {
public static void main(String[] args) {
int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
bubbleSort(unsortedArray);
System.out.println("After sort: ");
for (int item : unsortedArray) {
System.out.print(item + " ");
}
}
public static void bubbleSort(int[] array) {
int len = array.length;
for (int i = 0; i < len; i++) {
for (int item : array) {
System.out.print(item + " ");
}
System.out.println();
for (int j = 1; j < len - i; j++) {
if (array[j - 1] > array[j]) {
int temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
}
~~~
### 复杂度分析
平均情况与最坏情况均为 O(n2)O(n^2)O(n2), 使用了 temp 作为临时交换变量，空间复杂度为 O(1)O(1)O(1).
### Reference
- [冒泡排序 - 维基百科，自由的百科全书](http://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F)
';