Java資料結構和算法（九）

快速排序

基本思想

快速排序(Quicksort）是對冒泡排序的一種改進。基本思想是:通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列

動畫示範

代碼實作

public class QuickSort {

	public static void main(String[] args) {
		int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr));
		quickSort(arr, 0, arr.length - 1);
		System.out.println("排序後");
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr, int left, int right) {
		int l = left; // 左下标
		int r = right; // 右下标
		// pivot 中軸值
		int pivot = arr[(left + right) / 2];
		int temp = 0; // 臨時變量，作為交換時使用
		// while循環的目的是讓比pivot 值小放到左邊
		// 比pivot 值大放到右邊
		while (l < r) {
			// 在pivot的左邊一直找,找到大于等于pivot值,才退出
			while (arr[l] < pivot) {
				l += 1;
			}
			// 在pivot的右邊一直找,找到小于等于pivot值,才退出
			while (arr[r] > pivot) {
				r -= 1;
			}
			// 如果l >= r說明pivot 的左右兩的值，已經按照左邊全部是
			// 小于等于pivot值，右邊全部是大于等于pivot值
			if (l >= r) {
				break;
			}
			// 交換
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
			// 如果交換完後，發現這個arr[l] == pivot值 相等 r--， 前移
			if (arr[l] == pivot) {
				r -= 1;
			}
			// 如果交換完後，發現這個arr[r] == pivot值 相等 l++， 後移
			if (arr[r] == pivot) {
				l += 1;
			}
		}
		// 如果 l == r, 必須l++, r--, 否則為出現棧溢出
		if (l == r) {
			l += 1;
			r -= 1;
		}
		// 向左遞歸
		if (left < r) {
			quickSort(arr, left, r);
		}
		// 向右遞歸
		if (right > l) {
			quickSort(arr, l, right);
		}
	}
}

           

歸并排序

基本思想

歸并排序(MERGE-SORT)是利用歸并的思想實作的排序方法，該算法采用經典的分治(divide-and-conquer)政策（分治法将問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則将分的階段得到的各答案"修補"在一起，即分而治之)。

動畫示範

代碼實作

在這裡插入代碼片
           

基數排序

基本思想

1. 基數排序(radix sort)屬于“配置設定式排序”( distribution sort)，又稱“桶子法”(bucket sort）或bin sort,顧名思義，它是通過鍵值的各個位的值，将要排序的元素配置設定至某些“桶”中，達到排序的作用
2. 基數排序法是屬于穩定性的排序，基數排序法的是效率高的穩定性排序法
3. 基數排序(Radix Sort)是桶排序的擴充
4. 基數排序是1887年赫爾曼·何樂禮發明的。它是這樣實作的:将整數按位數切割成不同的數字，然後按每個位數分别比較。

動畫示範

代碼實作