冒泡排序，每次比较两个相邻的元素, 如果他们的顺序错误就把他们交换位置，核心是 冒泡。把数组中最大的那个往上冒，冒的过程就是和他相邻的元素交换。这个冒的过程就是内循环，循环次数为元素个数 - 外循环的次数 - 2（因为数组的后面冒出已经是有序的并且为了保证对于数组下标+1时不会索引异常）；经过了一个冒的过程，可以使一个最小的元素冒出来，如果数组里面有 n 个元素，就得冒 n-1 次，这就是外循环。时间复杂度为O(n*n)。
- java实现
public class Bubble {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - i - 1; j++) {
if (!less(a[j], a[j + 1])) {
exch(a, j, j + 1);
}
}
}
}
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
String[] a = {"80", "30", "60", "40", "20", "10", "50", "70"};
sort(a);
assert isSorted(a);
show(a);
}
}
- python实现
class Bubble:
def sort(self, data):
for i in range(len(data)):
for j in range(len(data) - i - 1):
if not self.less(data[j], data[j + 1]):
self.exch(data, j, j + 1)
def less(self, x, y):
return x < y
def exch(self, data, i, min_index):
data[i], data[min_index] = data[min_index], data[i]
if __name__ == "__main__":
s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
bubble = Bubble()
bubble.sort(s)
print(s)
可以对冒泡排序进行两个阶段优化：
1. 优化外循环
当里面一层循环在某次扫描中没有执行交换，则说明此时数组已经全部有序列，无需再扫描了。因此，增加一个标记，每次发生交换，就标记，如果某次循环完没有标记，则说明已经完成排序。例如n个元素已经是有序的，只循环一次判断是否需要冒泡即可，不需要再接着循环。
- java实现
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
boolean flag = true;
for (int j = 0; j < N - i - 1; j++) {
if (!less(a[j], a[j + 1])) {
exch(a, j, j + 1);
flag = false;
}
}
if (flag) break;
}
}
- python实现
def sort(self, data):
for i in range(len(data)):
flag = True
for j in range(len(data) - i - 1):
if not self.less(data[j], data[j + 1]):
self.exch(data, j, j + 1)
flag = False
if flag:
break
2. 优化内循环
目前的内部循环次数是[0...N - i - 2]，因为后面的元素已经是有序的不需要再查询了。其实内部循环的界限也是可以再优化的：例如，如果R[i...n]已是有序区间，上次的扫描区间是R[0..i]，记上次扫描时最后 一次执行交换的位置为lastIndex，则lastIndex在0与i之间，不难发现R[lastIndex...n]区间也是有序的，否则这个区间也会发生交换；所以下次扫描区间就可以由R[0...i] 缩减到[0...lastIndex]。
另外，可以与优化方式1的标志位结合起来。创建temp 和lastIndex两个变量，当外部循环开始时将temp赋值给lastIndex，如果内部循环没有发生顺序更换，则lastIndex 与temp是相等的，直接break掉外部循环。
- java实现
public static void sort(Comparable[] a) {
int N = a.length;
int temp = N - 1;
int lastIndex;
for (int i = 0; i < N; i++) {
lastIndex = temp;
for (int j = 0; j < lastIndex; j++) {
if (!less(a[j], a[j + 1])) {
exch(a, j, j + 1);
temp = j;
}
}
if (lastIndex == temp) break;
}
}
- python 实现
def sort(self, data):
temp = len(data) - 1
for i in range(len(data)):
last_index = temp
for j in range(last_index):
if not self.less(data[j], data[j + 1]):
self.exch(data, j, j + 1)
temp = j
if last_index == temp:
break
插入排序与冒泡排序很相似，都是O(n*n)时间复杂度，但是两者的原理是不同的：插入排序是先使前面的有序，后面的每一个插入到前面的有序数组里，当索引到最后一个元素时，整个序列就变成有序的了；冒泡排序是一直相邻两个元素比较，将较大的冒到后面，直到整个序列有序。
