排序算法（冒泡、選擇、插入、希爾、歸并、快排、堆排序）

package Sort;

public class sort {
	// https://www.cnblogs.com/onepixel/articles/7674659.html
	public static void main(String[] args) {
		int[] arr = { 2, 6, 3, 5, 7, 3, 6, 8 };
		HeapSort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	// 冒泡
	// 每次比較相鄰的元素，如果第一個比第二個大就交換他們兩個
	// 這樣交換到最後，最後的元素是最大的
	// 針對除了最後一個元素以外的所有元素重複以上步驟
	public static void BubbleSort(int[] arr) {
		int len = arr.length;
		for (int i = 0; i < len - 1; i++) {
			for (int j = 0; j < len - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j + 1];
					arr[j + 1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}

	// 選擇排序
	// 在未排序序列中找到最小的元素，放到排序序列的起始位置，
	// 然後再從剩餘未排序元素中繼續尋找最小的元素，放在已排序的末尾
	public static void SelectionSort(int[] arr) {
		int len = arr.length;
		int min = 0;
		for (int i = 0; i < len - 1; i++) {
			min = i;
			for (int j = i + 1; j < len; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = arr[i];
				arr[i] = arr[min];
				arr[min] = temp;
			}
		}
	}

	// 插入排序
	// 從第一個元素開始，該元素可以認為已經被排序
	// 取出下一個元素，在已經排序的元素序列中從後向前掃描
	// 找到他在已排序的序列中的位置
	public static void InsertSort(int[] arr) {
		int len = arr.length;
		for (int i = 1; i < len; i++) {
			for (int j = i; j > 0; j--) {
				if (arr[j] < arr[j - 1]) {
					int temp = arr[j];
					arr[j] = arr[j - 1];
					arr[j - 1] = temp;
				}
			}
		}
	}

	// 希爾排序
	// 插入排序的改進版，會優先比較距離較遠的元素
	public static void Shell(int[] arr) {
		int n = arr.length;
		int h = 1;
		while (h < n / 3) {
			// 1,4,13……
			h = h * 3 + 1;
		}
		while (h >= 1) {
			for (int i = h; i < n; i++) {
				for (int j = i; j >= h; j--) {
					if (arr[j] < arr[j - h]) {
						int temp = arr[j];
						arr[j] = arr[j - h];
						arr[j - h] = temp;
					}
				}
				h = h / 3;
			}
		}
	}

	// 歸并排序
	// 把長度為n的輸入序列分成兩個長度為n/2的子序列
	// 對這兩個子序列分别采用歸并排序
	// 将兩個排序好的子序列合并成一個最終的排序序列
	public static void MergeSort(int[] arr, int start, int end) {
		if (arr == null || start >= end) {
			return;
		}
		int middle = (start + end) / 2;
		// 遞歸
		MergeSort(arr, start, middle);
		MergeSort(arr, middle + 1, end);
		// 歸并
		Merge(arr, start, middle, end);
	}

	public static void Merge(int[] arr, int start, int mid, int end) {
		int[] array = new int[end + 1]; // 定義一個臨時數組，用來存儲排序後的結果
		int k = start; // 臨時數組的索引
		int i = start;
		int j = mid + 1;
		// 取出最小值放入臨時數組中
		while (i <= mid && j <= end) {
			array[k++] = arr[i] > arr[j] ? arr[j++] : arr[i++];
		}

		// 若還有段序列不為空，則将其加入臨時數組末尾
		while (i <= mid) {
			array[k++] = arr[i++];
		}
		while (j <= end) {
			array[k++] = arr[j++];
		}

		// 将臨時數組中的值copy到原數組中
		for (int m = start; m <= end; m++) {
			arr[m] = array[m];
		}

	}

	// 快速排序
	// 從數列中挑選一個數作為基準
	// 所有元素比基準小的放在基準前面，比基準大的放在基準後面，退出後，基準在中間位置
	// 遞歸
	public static void QuickSort(int[] a, int start, int end) {
		// 1,找到遞歸算法的出口
		if (start > end) {
			return;
		}
		// 2, 存
		int i = start;
		int j = end;
		// 3,key
		int key = a[start];
		// 4，完成一趟排序
		while (i < j) {
			// 4.1 ，從右往左找到第一個小于key的數
			while (i < j && a[j] > key) {
				j--;
			}
			// 4.2 從左往右找到第一個大于key的數
			while (i < j && a[i] <= key) {
				i++;
			}
			// 4.3 交換
			if (i < j) {
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		// 4.4，調整key的位置
		int temp = a[i];
		a[i] = a[start];
		a[start] = temp;
		// 5, 對key左邊的數快排
		QuickSort(a, start, i - 1);
		// 6, 對key右邊的數快排
		QuickSort(a, i + 1, end);
	}

	// 堆排序
	// 父節點的鍵值大于子節點
	// 建構大根堆：将array看成完全二叉樹的順序存儲結構
	private static int[] buildMaxHeap(int[] array) {
		// 從最後一個節點array.length-1的父節點（array.length-1-1）/2開始，直到根節點0，反複調整堆
		for (int i = (array.length - 2) / 2; i >= 0; i--) {
			adjustDownToUp(array, i, array.length);
		}
		return array;
	}

	// 将元素array[k]自下往上逐漸調整樹形結構
	private static void adjustDownToUp(int[] array, int k, int length) {
		int temp = array[k];
		for (int i = 2 * k + 1; i < length - 1; i = 2 * i + 1) { // i為初始化為節點k的左孩子，沿節點較大的子節點向下調整
			if (i< length && array[i] < array[i + 1]) { // 取節點較大的子節點的下标
				i++; // 如果節點的右孩子>左孩子，則取右孩子節點的下标
			}
			if (temp >= array[i]) { // 根節點 >=左右子女中關鍵字較大者，調整結束
				break;
			} else { // 根節點 <左右子女中關鍵字較大者
				array[k] = array[i]; // 将左右子結點中較大值array[i]調整到雙親節點上
				k = i; // 【關鍵】修改k值，以便繼續向下調整
			}
		}
		array[k] = temp; // 被調整的結點的值放人最終位置
	}

	// 堆排序
	public static void HeapSort(int[] array) {
		array = buildMaxHeap(array); // 初始建堆，array[0]為第一趟值最大的元素
		for (int i = array.length - 1; i >=1; i--) {
			int temp = array[0]; // 将堆頂元素和堆低元素交換，即得到目前最大元素正确的排序位置
			array[0] = array[i];
			array[i] = temp;
			adjustDownToUp(array, 0, i); // 整理，将剩餘的元素整理成堆
		}
	}


}