資料結構與算法Java實作（1）——冒泡排序

經過阿裡的摧殘，決定重新學習下資料結構與算法。

最近也有和同學聊面試的事，上個月有同學去東軟面試，讓他手撕算法寫個冒泡排序。第一個學的排序算法就是冒泡排序，大一學C語言的時候就是冒泡排序，那就從冒泡排序開始我的學習之旅吧。

冒泡排序是一種穩定的，交換排序。

原理：比較兩個相鄰的元素，根據需求，将值大的元素交換至右/左端。

思路：依次比較相鄰的兩個數，将小數放在前面，大數放在後面。(小到大)

時間複雜度:O(n2)最好情況O(n)

空間複雜度:O(l)

代碼實作

import java.util.Arrays;
/**
 * 冒泡排序，從小到大
 * @author scz
 */
public class BubbleSort {
		public static void bubbleSort(int[] a){
			int i,j = 0;
			for(i = 0; i < a.length; i++){//數組多長就循環多少次
				int temp;//臨時存儲空間
				for(j = 1; j < a.length-i; j++){
					if(a[j-1] > a[j])
					{
						temp = a[j-1];
						a[j-1] = a[j];
						a[j] =temp;//核心
					}					
				}	
				System.out.println(Arrays.toString(a));			
			}			
		}
		
		public static void main(String[] args){
			int[] a = {5,4,7,6,2,8};
			BubbleSort.bubbleSort(a);		
		}
}


           

效果

冒泡排序的優點：每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。即每一趟之後等至少會多有一個元素處于正确位置。

缺點:時間複雜度高，效率低，每次隻能每一趟排序操作隻能找到一個最大值或最小值，為了解決這個問題，我們将改進冒泡排序，也就是下一篇中要說的快速排序。