算法与数据结构-排序

// exchange a[i] and a[j]
public static void exch(Comparable[] a, int i, int j) {
	Comparable swap = a[i];
	a[i] = a[j];
	a[j] = swap;
}

// is v < w?	public static boolean less(Comparable v, Comparable w) {
	return v.compareTo(w) < 0;
}

public static void selectionSort(Comparable[] a) {
	if(a == null || a.length < 2) {
	return;
	}
		
	for(int i = 0; i<a.length; i++) {
		int min = i;
		for(int j=i+1; j<a.length; j++) {
			if(less(a[j], a[min])) {
				min = j;
			}
		}
		exec(a, i, min);
	}
}

public static void bubbleSort(Comparable[] a) {
	if (a == null || a.length < 2) {
		return;
	}

	int n = a.length;
	boolean isSort = false;
	for (int i = n; i > 1 && !isSort; i--) {
		isSort = true;
		for (int j = 0; j < i - 1; j++) {
			if (less(a[j + 1], a[j])) {
				exec(a, j + 1, j);
				isSort = false;
			}
		}
	}
}

public static void insertSort(Comparable[] a) {
	if (a == null || a.length < 2) {
		return;
	}

	int n = a.length;
	for (int i = 1; i < n; i++) {
		for (int j = i - 1; j >= 0 && less(a[j + 1], a[j]); j--) {
			exec(a, j + 1, j);
		}
	}
}

public static void shellSort(Comparable[] a) {
	if (a == null || a.length < 2) {
		return;
	}

	int n = a.length;

	// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
	int h = 1;
	while (h < n / 3) {
		h = 3 * h + 1;
	}

	while (h >= 1) {
		// h-sort the array
		for (int i = h; i < n; i++) {
			for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
				exec(a, j - h, j);
			}
		}

		h /= 3;
	}
}

// merging
public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

	// copy to aux[]
	for (int k = lo; k <= hi; k++) {
		aux[k] = a[k];
	}

	/*
	 * 1 3 5 7   2 4 6 8 
	 * i         j         
	*/
	int i = lo;
	int j = mid + 1;
		
	// merge back to a[]
	for (int k = lo; k <= hi; k++) {
		// 左边元素用尽
		if (i > mid) {
			a[k] = aux[j++];
		// 右边元素用尽
		} else if (j > hi) {
			a[k] = aux[i++];
		// 左边元素比右边小,先进行这一步，保证稳定性
		} else if (less(aux[i], aux[j])) {
			a[k] = aux[i++];
		// 右边元素比左边小
		} else {
			a[k] = aux[j++];
		}
	}
}

public static void mergeSort(Comparable[] a, Comparable[] aux, int lo, int hi) {
	// base case
	if (hi <= lo) {
		return;
	}

	int mid = lo + (hi - lo) / 2;
	mergeSort(a, aux, lo, mid);
	mergeSort(a, aux, mid + 1, hi);
	merge(a, aux, lo, mid, hi);
}

// merge sort (bottom up)
public static void mergeSort(Comparable[] a) {
	int n = a.length;
	Comparable[] aux = new Comparable[a.length];
	for (int sz = 1; sz < n; sz = sz + sz) {
		for (int lo = 0; lo < n - sz; lo += sz + sz) {
			merge(a, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
		}
	}
}

public static void quickSort(int[] a) {
	if(a == null || a.length < 2 ) {
		return;
	}
		
	quickSort(a, 0, a.length-1);
}

public static void quickSort(int[] a, int lo, int hi) {
	if (lo < hi) {
		swap(a, (int) (Math.random() * (hi - lo + 1)) + lo, hi);
		int[] position = partition(a, lo, hi);
		quickSort(a, lo, position[0] - 1);			quickSort(a, position[1] + 1, hi);
	}
}
	
	
public static int[] partition(int[] a, int lo, int hi) {
	int p1 = lo -1;
	int p2 = hi;
		
	while(lo < p2) {
		if(a[lo] < a[hi]) {
			swap(a, ++p1, lo++);
		} else if (a[lo] > a[hi]) {
			swap(a, --p2, lo);
		} else {
			lo++;
		}
	}
		
	swap(a, p2, hi);
		
	return new int[] {p1 +1, p2};
}

public static void swap(int[] a, int i, int j) {
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

public class HeapSort {
	
	public static void heapSort(int[] a) {
		if(a == null || a.length<2) {
			return;
		}
		
		// 构建堆
		int size = a.length;
		for(int i=0; i<size; i++) {
			heapInsert(a, i);
		}
		
		swap(a, 0, --size);
		while (size > 0) {
			heapify(a, 0, size);
			swap(a, 0, --size);
		}
	}
	

	public static void heapInsert(int[] a, int index) {
		while (a[index] > a[(index - 1) / 2]) {
			swap(a, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	public static void heapify(int[] a, int index, int size) {
		int left = index * 2 + 1;
		while (left < size) {
			// 一定要判断右孩子是否存在
			int max = left + 1 < size && a[left + 1] > a[left] ? left + 1 : left;
			max = a[max] > a[index] ? max : index;
			if (max == index) {
				break;
			}

			swap(a, max, index);
			// 一定要做这一步
			index = max;
			left = index * 2 + 1;
		}
	}

	public static void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
}