【排序算法】冒泡排序的实现与分析
以升序排序为例：
实现方法代码实现将所有的待排序的n个数字放入数组中。从第1个数字开始遍历数组，两两比较数组中的元素，如果前者大于后者，则将两者位置进行交换。一次遍历后，最大值将排在最后一个位置上。然后对前n-1个元素做第二次遍历和交换，遍历后第二大的数字将被排到数组的倒数第二个位置。以此类推。
public class BubbleSort {public static void main(String args[]) { int[] numbers={-1, 0, 50, 44, -90};sort(numbers);for(int number : numbers) { System.out.println(number); } }static void sort(int[] numbers){int temp;//n-1次遍历for(int i=0;i<numbers.length-1;i++){for(int j=0; j<numbers.length-1-i;j++){if(numbers[j]>numbers[j+1]){temp=numbers[j];numbers[j]=numbers[j+1];numbers[j+1]=temp;}}}}}空间复杂度时间复杂度主要从判断的次数来进行分析。
由代码可知，判断的次数为(n-1)+(n-2)+...+2+1 = n(n-1)/2 = (n^2)/2-n/2
证明时间复杂度为O(n^2):
首先需要确定常数c1, c2, n0, 使得对于所有的n>=n0，都有c1*(n^2) <= (n^2)/2-n/2 <= c2*(n^2)
将用n^2除不等式得c1< = 1/2-1/2n <= c2
对于左边的不等式c1< = 1/2-1/2n，c1<=1/4时对所有的n>=2都成立。
对于右边的不等式1/2-1/2n <= c2，c2>=1/2时对所有的n>=2都成立。
我们取c1=1/4,c2=1/2,n0=2，此时对于所有的n>=n0，都有c1*(n^2) <= (n^2)/2-n/2 <= c2*(n^2)
因此冒泡排序的时间复杂度为O(n^2)
值得注意的是，尽管判断次数为O(n^2)，但交换的次数会由于原始数据的顺序不同而有很大的区别。当原始数据的排列顺序刚好是有序的，交换次数为0，若原始数据的排列顺序是倒序的，交换次数和判断次数相同，为O(n^2)。
由于只用了一个临时变量，空间复杂度为O(1)。