此博客用于个人学习，来源于算法的书籍和网上的资料，对知识点进行一个整理。
1. 概述：
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
2. 算法描述：
比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。
3. 代码实现：
public class BubbleSort {
public static void sort(Comparable
[] a
){
int N
= a
.length
;
for (int i
= 0;i
< N
- 1;i
++){
for (int j
= 0;(j
< N
- 1 - i
) && less(a
[j
],a
[i
]);j
++){
exchange(a
,i
,j
);
}
if (isSorted(a
))
break;
}
}
private static boolean less(Comparable v
,Comparable w
){
return v
.compareTo(w
) < 0;
}
private static void exchange(Comparable
[] a
,int i
,int j
){
Comparable t
= a
[i
];
a
[i
] = a
[j
];
a
[j
] = t
;
}
private static void show(Comparable
[] a
){
for (int i
= 0;i
< a
.length
;i
++){
System
.out
.println(a
[i
]+" ");
}
System
.out
.println();
}
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;
}
}
4. 优点：
每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。比如，第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
5. 算法分析：
时间复杂度：推广到数量为 n 的规模的话，那就需要 (n-1) + (n-2) +…+2+1 次，即为一个等差数列，根据复杂度的规则，去掉低阶项（也就是 n/2）,并去掉常数系数，那复杂度就是 O(n^2) 了。
空间复杂度
：由于 temp 变量在一开始定义了，只有那一行对于内存进行了调用，
空间复杂度
为 O(1)。稳定性：因为在交换的时候，如果两个元素大小相同，那么就不交换[ less( a[j],a[i] ){交换}],相同元素不会因为算法中哪条语句相互交换位置的，因此是稳定的。
