学步园

以升序排序为例：

• 实现方法

将所有的待排序的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)。