排序算法Java实现

个人博客：小景哥哥

package top.jinglisen.algorithms;

public class Sorts {

	//1.直接插入排序
	public static void insertSort(int[] a) {
		for(int i = 1; i < a.length; i++) {
			int t = a[i];
			int j = i;
			for(; j >= 1; j--) {
				if(t < a[j - 1]) 
					a[j] = a[j - 1];
				else 
					break;
			}
			a[j] = t;
		}
	}
	
	//2.希尔排序
	public static void shellSort(int[] a) {
		int t;
		for(int gap = a.length / 2; gap > 0; gap /= 2) {
			for(int i = gap; i < a.length; i++) {
				t = a[i];
				int j = i;
				for(; j >= gap; j -= gap) {
					if(t < a[j - gap])
						a[j] = a[j - gap];
					else 
						break;
				}
				a[j] = t;
			}
		}
	}
	//3.简单选择排序
	//在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
	public static void selectSort(int[] a) {
		for(int i = 0; i < a.length; i++) {
			int min = i;
			for(int j = i + 1; j < a.length; j++) {
				if(a[min] > a[j]){
					min = j;
				}
			}
			int t = a[i];
			a[i] = a[min];
			a[min] = t;
		}
	}
	
	//4.堆排序
	public static void heapSort(int[] a) {
		buildMaxHeap(a);
		for(int i = a.length - 1; i > 0; i--) {
			swap(a, 0, i);
			percDown(a, 0, i);
		}
	}
	public static void buildMaxHeap(int[] a) {
		//最后一个有孩子的结点位置: i = (length - 1) / 2
		for(int i = a.length / 2 - 1; i >= 0; i--) {
			percDown(a, i, a.length);
		}
	}
	public static void percDown(int[] a, int i, int n) {
		int child;
		int tmp;
		for(tmp = a[i]; 2 * i + 1 < n; i = child) {
			child = 2 * i + 1;
			if(child != n - 1 && a[child] < a[child + 1])//选择两个孩子中较大者
				child++;
			if(tmp < a[child])//tmp比两个孩子中较大者还小，把较大者提升为父节点
				a[i] = a[child];
			else
				break;
		}
		a[i] = tmp;
	}
	public static void swap(int[]a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	//5.冒泡排序
	public static void bubbleSort(int[] a) {
		for(int i = 0; i < a.length; i++) {
			for(int j = i + 1; j < a.length; j++) {
				if(a[i] > a[j]) {
					int tmp = a[i];
					a[i] = a[j];
					a[j] = tmp;
				}
			}
		}
	}
	//6.快速排序
	public static void quickSort(int[] a) {
		quickSort(a, 0, a.length - 1);
	}
	public static void quickSort(int[] a, int l, int r) {
		if(l < r) {
			int m = partion(a, l, r);
			quickSort(a, 0, m - 1);
			quickSort(a, m + 1, r);
		}
	}
	public static int partion(int[] a, int l, int r) {
		int privotKey = a[l];
		while(l < r) {
			while(l < r && a[r] >= privotKey)
				--r;
			swap(a, l, r);
			while(l < r && a[l] <= privotKey)
				++l;
			swap(a, l, r);
		}
		return l;
	}
	
	//7.归并排序
	public static void mergeSort(int[] a) {
		int[] tmpArray = new int[a.length];
		mergeSort(a, tmpArray, 0, a.length - 1);
	}
	public static void mergeSort(int[] a, int[] tmpArray, int left, int right) {
		if(left < right) {
			int center = (left + right) / 2;
			mergeSort(a, tmpArray, left, center);
			mergeSort(a, tmpArray, center + 1, right);
			merge(a, tmpArray, left, center + 1, right);
		}
	}
	public static void merge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;
		
		while(leftPos <= leftEnd && rightPos <= rightEnd) {
			if(a[leftPos] <= a[rightPos])
				tmpArray[tmpPos++] = a[leftPos++];
			else
				tmpArray[tmpPos++] = a[rightPos++];
		}
		while(leftPos <= leftEnd)
			tmpArray[tmpPos++] = a[leftPos++];
		while(rightPos <= rightEnd)
			tmpArray[tmpPos++] = a[rightPos++];
		for(int i = 0; i < numElements; i++, rightEnd--) {
			a[rightEnd] = tmpArray[rightEnd];
		}
	}