資料結構和算法－排序

一、簡單排序

1.冒泡排序O(n^2)

兩兩比較，反序交換

public static int[] bubbleSort(int[] arr) {
	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]) {
				arr[j]   = arr[j] ^ arr[j+1];
				arr[j+1] = arr[j] ^ arr[j+1];
				arr[j]   = arr[j] ^ arr[j+1];
			}
		}
	}
	return arr;
}
           

2.選擇排序O(n^2)

public static int[] selectSort(int[] arr) {
		int minIndex = -1;
		for (int i = 0; i < arr.length - 1; i++) {
			minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if(arr[minIndex] > arr[j]) {
					minIndex = j;
				}
			}
			if(i != minIndex) {
				arr[i]        = arr[minIndex] ^ arr[i];
				arr[minIndex] = arr[minIndex] ^ arr[i];
				arr[i]        = arr[minIndex] ^ arr[i];
			}
		}
		return arr;
	}
           

3.插入排序

将一個記錄插入到已經排好序的有序表中得到一個新的、記錄增1的有序表

public static int[] insertSort(int[] arr) {
		int sentinel;
		int index = -1;
		for (int i = 1; i < arr.length; i++) {
			sentinel = arr[i];
			if(arr[i] < arr[i - 1]) {
				// loop compare
				for (int j = 0; j < i; j++) {
					if(arr[i] < arr[j]) {
						index = j;
						break;
					}
				}
				// move
				for (int k = i; k > index; k--) {
					arr[k]   = arr[k] ^ arr[k-1];
					arr[k-1] = arr[k] ^ arr[k-1];
					arr[k]   = arr[k] ^ arr[k-1];
				}
				arr[index] = sentinel;
			}
		}
		return arr;
	}
           

二、複雜排序

1.希爾排序O(n^(3/2))

增量序列最後一個增量值必須等于1，初次取序列的一半為增量，以後每次減半，使序列基本有序，直到增量為1。

不實作了，在直接排序的基礎上增加了一個增量，序列的增量比較。

2.堆排序O(nlogn)

是在選擇排序基礎上的改進，将序列建構成一個大頂堆，将堆頂元素移走，再将剩下的元素重新建構一個堆

堆：完全二叉樹，節點大于或等于其左右節點的值稱為大頂堆，小于或等于稱為小頂堆

public static int[] heapSort(int[] arr) {
		int len = arr.length;
		// 建構大頂堆
		for (int i = len / 2; i > 0 ; i--) {
			adjustHeap(arr, i-1, len);
		}
		
		for (int i = len - 1; i > 0; i--) {
			// 将堆頂資料與最後一個資料交換
			arr[0] = arr[0] ^ arr[i];
			arr[i] = arr[0] ^ arr[i];
			arr[0] = arr[0] ^ arr[i];
			
			adjustHeap(arr, 0, i);
		}
		return arr;
	}
	
	// 調整堆結構
	public static int[] adjustHeap(int[] arr, int curInd, int len) {
		int tmp = arr[curInd];
		// 目前節點與其自節點比較交換 子節點：2*curIndex 2*curIndex+1 
		for(int i = (curInd + 1) * 2; i <= len; i++) {
			// 判斷左右節點大小，将i設定為較大值index
			if (i < len && arr[i-1] < arr[i]) {
				++i;
			}
			
			// 父節點與較大子節點比較
			if (arr[curInd] > arr[i-1]) {
				break;
			}
			arr[curInd] = arr[curInd] ^ arr[i-1];
			arr[i - 1]  = arr[curInd] ^ arr[i-1];
			arr[curInd] = arr[curInd] ^ arr[i-1];
			curInd = i - 1;
		}
		arr[curInd] = tmp;
		return arr;
	}
           

 3.歸并排序

用遞歸和分而治之的技術将資料序列劃分成為越來越小的半子表，再對半子表排序，最後再用遞歸步驟将排好序的半子表合并成為越來越大的有序序列

public static int[] mergeSort(int[] arr, int first, int last) {
		if ((first + 1) < last) {
			int mid = (first + last) / 2;
			mergeSort(arr, first, mid);
			mergeSort(arr, mid, last);
			merge(arr, first, mid, last);
		}
		return arr;
	}
	
	public static void merge(int[] arr, int first, int mid, int last) {
		int[] tmp = new int[last - first];
		int indexL = first, indexR = mid, index = 0;
		
		while(indexL < mid && indexR < last) {
			if (arr[indexL] < arr[indexR]) {
				tmp[index] = arr[indexL];
				indexL ++;
			} else {
				tmp[index] = arr[indexR];
				indexR ++;
			}
			index ++;
		}
		
		while (indexL < mid) {
			tmp[index] = arr[indexL];
			index ++;
			indexL ++;
		}
		
		while (indexR < last) {
			tmp[index] = arr[indexR];
			index ++;
			indexR ++;
		}
		
		index = 0;
		for (int i = first; i < last; i++) {
			arr[i] = tmp[index];
			index ++;
		}
		
	}
           

 4.快速排序O(nlogn)

經過一次排序分割成2部分，一部分大于另一部分

public static int[] quickSort(int[] arr, int low, int high) {
		int privot;
		if (low < high) {
			privot = partition(arr, low, high);
			quickSort(arr, low, privot - 1);
			quickSort(arr, privot + 1, high);
		}
		return arr;
	}

	public static int partition(int[] arr, int low, int high) {
		int privotKey = arr[low];
		while (low < high) {
			while (low < high && privotKey <= arr[high]) {
				high--;
			}
			swap(arr, low, high);
			while (low < high && privotKey >= arr[low]) {
				low++;
			}
			swap(arr, low, high);
		}
		return low;
	}

	public static void swap(int[] arr, int i1, int i2) {
		if (i1 != i2) {
			arr[i1] = arr[i1] ^ arr[i2];
			arr[i2] = arr[i1] ^ arr[i2];
			arr[i1] = arr[i1] ^ arr[i2];
		}
	}
           

 優化：随機選取、三數取中