交换排序

交换排序的基本思想：两两比较待排序关键字，一旦发现两个记录不满足次序要求则进行交换，知道整个队列全部满足要求为止

冒泡排序

冒泡排序是一种最简单的交换排序，他通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”，或者往下沉。

 1 public class BubbleSort {
 2     
 3     public static void main(String [] args) {
 4         int[] array = new int[]{2, 6, 3, 8, 9, 0, 1, 7, 4};
 5         BubbleSort(array);
 6     }
 7     
 8     public static void BubbleSort(int[] array) {
 9         printArray(array);
10         for(int i = 0; i < array.length; i++) {
11             boolean flag = true;    // 标记本次循环没有数据交换
12             for(int j = 0; j < array.length - i - 1; j++) {
13                 if(array[j] > array[j+1]) {
14                     int tmp = array[j];
15                     array[j] = array[j+1];
16                     array[j+1] = tmp;
17                     flag = false;   // 发生了数据交换
18                 }
19             }
20             printArray(array);
21             if(flag) {
22                 // 如果本次循环没有发生任何数据交换
23                 break;
24             }
25         }
26     }
27     
28     public static void printArray(int[] array) {
29         for(int i : array) {
30             System.out.printf("%d	", i);
31         }
32         System.out.println();
33     }
34 }

时间复杂度：O(n²)

空间复杂度：O(1)

算法特点：

稳定排序
可用于链式存储结构
移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，记录数较大时，不宜采用。