“walk beside you ”
前言
山外青山楼外楼， 西湖歌舞几时休！ 暖风熏得游人醉， 直把杭州作汴州。 林升 《题临安邸》
正文
冒泡排序（Bubble Sort），是一种计算机科学领域的一种简单的排序算法。 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，所以称之为“冒泡”。
原理分析
- 假如 N 个数。从头开始，比较相邻的两个数。如果前面的比后面的大，则交换位置。
- 重复前一个动作，直到比较完最后一对相邻的数。则后一位的数字为最大的数。
- 除却最后一位最大的数。剩下 N - 1 为数。重复以上的动作。直到剩下最后一个数，则为最小是数
时间复杂度
规定整个过程比较次数为 C 、记录移动次数为 M 。
- 若需排序的元素，正好为正序的排列。如
1,2,3,4,5,...,n-1,n，则 C = n-1 , M = 0 。时间复杂度为 O(n) - 若需排序的元素，正好为倒序的排序。如
n,n-1,...,5,4,3,2,1，则 C = (n-1) + (n-2) + …+ 2 + 1 = (n-1)n/2 ,由于每次比较移动了三次数据则 M = 3(n-1)*n/2 。时间复杂度为 O(n^2) 所以，冒泡排序最好的时间复杂度为 O(n),冒泡排序的最坏时间复杂度为 O(n^2),因此冒泡排序总的平均时间复杂度为 O(n^2) 。
代码
int tmp = 0;
for(int i = bubble.length - 1;i > 0; i-- ){
for(int j = 0;j < i; j++){
if(bubble[j] > bubble[j+1]){
tmp = bubble[j+1];
bubble[j+1] = bubble[j];
bubble[j] = tmp;
}
}
}