數組排序(1) 冒泡排序

目錄

       算法思想

       代碼實作

       時間複雜度

算法思想：(以從小到大為例）

1. 從數組頭部開始，不斷比較相鄰的兩個元素，讓較大的那個元素後移，直到數組的末尾。 經過第一輪的比較，就可以找到最大的元素，并将它移動到最後一個位置。
2. 從數組頭部開始，不斷比較相鄰的兩個元素，讓較大的那個元素後移，直到與數組的倒數第二個元素比完。經過第二輪的比較，就可以找到第二大的元素，并将它移動到倒數第二個位置。
3. 以此類推，一共要找(n-1)次元素。（n為數組長度）

代碼實作：（Java）

//從arr[0]開始比較
public void BubbleSort1(int arr[]) {
	if(arr!=null) {
		int length=arr.length;
		for(int i=0; i<length; i++) {
			for(int j=0; j<length-i-1; j++) {
				//從小到大排序
				if(arr[j]>arr[j+1]) {
					arr[j]*=arr[j+1];
					arr[j+1]=arr[j]/arr[j+1];
					arr[j]/=arr[j+1];
				}
				//從大到小排序
				/*if(arr[j]<arr[j+1]) {
					arr[j]*=arr[j+1];
					arr[j+1]=arr[j]/arr[j+1];
					arr[j]/=arr[j+1];
				}
				*/
			}
		}
		for(int i=0; i<length; i++) {
			System.out.println(arr[i]+" ");
		}
	}
}


//從arr[arr.length-1]開始比較
public void BubbleSort2(int arr[]) {
	if(arr!=null) {
		int length=arr.length;
		for(int i=length-1; i>0; i--) {
			for(int j=length-1; j>length-i-1; j--) {
				//從小到大排序
				if(arr[j]<arr[j-1]) {
					arr[j]*=arr[j-1];
					arr[j-1]=arr[j]/arr[j-1];
					arr[j]/=arr[j-1];
				}
				//從大到小排序
				/*if(arr[j]>arr[j-1]) {
					arr[j]*=arr[j-1];
					arr[j-1]=arr[j]/arr[j-1];
					arr[j]/=arr[j-1];
				}
				*/
			}
		}
		for(int i=0; i<length; i++) {
			System.out.println(arr[i]+" ");
		}
    }
}
           

時間複雜度：

外層for循環要循環執行（n-1）次，内層for循環最多的時候循環執行（n-1）次，最少的時候循環執行1次，一共執行

次

是以其時間複雜度為O(n^2)。