3種簡單排序：冒泡排序、選擇排序和插入排序

1 冒泡排序

1.1 實作原理和過程

冒泡排序是所有排序中最基本的一種，其核心思想是交換排序，通過相鄰資料的交換來達到排序目的，缺點是效率低，時間複雜度為O（n^2）。具體過程如下：(1)依次比較數組中相鄰兩個元素的大小 （2）如果前面的資料大于後面的資料，則交換這兩個資料，經過一輪排序後，最大的資料就會占用數組最後一個位置。依此類推就可以實作升序排序。

1.2 完整代碼

public class BubbleSort {
	/**
	 * 冒泡排序
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		int temp; // 臨時變量，用于交換
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) { // 将大的元素置換在後面
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}
	
	/**
	 * 測試
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// 初始化數組
		int[] arr = { 10, 9, 8, 7, 6, 5, 4, 3, 1, 2 };


		// 測試冒泡排序
		bubbleSort(arr);
		System.out.println("冒泡排序的結果：" + Arrays.toString(arr));
	}
}

           

1.3 測試結果

2 選擇排序

2.1 實作原理和過程

選擇排序算法是通過選擇和交換來實作排序，因為交換的次數減少，是以選擇排序優于冒泡排序，但時間複雜度仍為O（n^2）。具體過程如下：1）假定a[0]為最小值min，與其他元素進行比較 2）若其他元素a[j]比min大則用臨時變量記錄下該坐标，并把a[j]賦予min，經次一輪，則可以擷取最小元素的值和位置，并将其與a[0]進行互換，依此類推就可以實作升序排序。

2.2 完整代碼

public class SelectionSort {
	/**
	 * 選擇排序 
	 * @param arr
	 */
	public static void selectionSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int min = arr[i];
			int temp;
			int index = i;
			for (int j = i + 1; j < arr.length; j++) { // 找出最小的坐标
				if (min > arr[j]) {
					index = j;
					min = arr[j];
				}
			}
			temp = arr[i]; // 元素交換
			arr[i] = min;
			arr[index] = temp;
		}
	}
	
	/**
	 * 測試
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// 初始化數組
		int[] arr = { 10, 9, 8, 7, 6, 5, 4, 3, 1, 2 };


		// 測試選擇排序
		selectionSort(arr);
		System.out.println("選擇排序的結果：" + Arrays.toString(arr));
	}


}
           

2.3 測試結果

3 插入排序

3.1 實作原理和過程

插入排序原理是通過對未排序的資料執行逐個插入至合适的位置而完成排序工作。當數組中存在較多局部有序資料時，插入排序的效果明顯優于冒泡排序和選擇排序，但時間複雜度仍為O（n^2）。具體過程如下：比較前2個數，如果第2個數大于第1個數，則将第二個數插入到a[1]位置，使得大的資料在右邊。同理将第3個數插入合适位置，直到所有資料都插完為止，依此類推就可以實作升序排序。

3.2 完整代碼

public class InsertionSort {


	/**
	 * 插入排序
	 * @param arr
	 */
	public static void insertSort(int[] arr) {
		int temp,j,i;
		for(i = 1; i < arr.length; i++){
			temp = arr[i];	//待插入的元素
			for(j = i-1; j >= 0 && arr[j] > temp; j--){	//待插入元素若比局部有序的元素小，則進行交換
				arr[j + 1] = arr[j];	//将數值較大的元素向後移動 
			}
			arr[j + 1] = temp;  //插入元素
		}
	}


	
	/**
	 * 測試
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// 初始化數組
		int[] arr = { 10, 9, 8, 7, 6, 5, 4, 3, 1, 2 };


		// 測試插入排序
		insertSort(arr);
		System.out.println("插入排序的結果：" + Arrays.toString(arr));
	}


}
           

3.3 測試結果

4 參考文獻

[1] Robert, Lafore., Java資料結構和算法.第2版 版. 2004: 中國電力出版社.

[2] Sedgewick Robert與Wayne  Kevin., 算法. 2012: 人民郵電出版社.