SortUtils.java

package junlin.util;

import java.util.Comparator;
import static junlin.util.Print.*;

public class SortUtil {

	/**
	 * 交换两个变量的值
	 *
	 * @param array
	 * @param i
	 * @param j
	 */
	private static <T> void swap(T[] array, int i, int j) {
		T temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	/**
	 * 冒泡排序，使用swapped标识优化。泛型类需要实现Comparable接口
	 *
	 * @param array
	 */
	public static <T extends Comparable<T>> void sort(T[] array) {
		boolean swapped = true;
		for (int i = 0; i < array.length - 1 && swapped; ++i) {
			swapped = false; // 如果这趟没有发生交换则不用再继续排序了
			for (int j = 0; j < array.length - i - 1; ++j) {
				if (array[j].compareTo(array[j + 1]) < 0) {
					swap(array, j, j + 1);
					swapped = true;
				}
			}
		}
	}

	/**
	 * 冒泡排序，使用swapped标识优化。需要传进一个比较器Comparator对象
	 *
	 * @param array
	 * @param comp
	 *            比较器，可以用匿名类实现
	 */
	public <T> void sort(T[] array, Comparator<T> comp) {
		boolean continued = true; // 是否继续下一趟排序标识
		int len = array.length;

		for (int i = 0; i < len - 1 && continued; ++i) {
			continued = false; // 排序前假设下一趟不用继续

			for (int j = 0; j < len - i - 1; ++j) {
				if (comp.compare(array[j], array[j + 1]) > 0) {
					continued = true; // 发生了交换，说明下一趟还可能需要排序，继续
					swap(array, j, j + 1);
				}
			}
		}
	}

	/**
	 * 快速排序。泛型T类需要实现Comparable接口
	 *
	 * @param array
	 * @param l
	 *            外部调用时此参数为0
	 * @param r
	 *            外部调用时此参数为array.length-1
	 */
	public static <T extends Comparable<T>> void quickSort(T[] array, int l, int r) {
		if (l < r) {
			T pivot = array[l]; // 定义基轴pivot为第一个数，挖的第一个坑

			int i = l, j = r;

			// 从左右两边向中间靠拢，把比pivot小的数放在左边，比pivot大的数放在右边
			while (i < j) {
				while (i < j && array[j].compareTo(pivot) >= 0) // 先从右向左找出比pivot小的数，j位置挖坑
					j--;
				if (i < j) // 把挖出的数array[j]填入左边的坑内，即i位置，然后i++
					array[i++] = array[j];

				while (i < j && array[i].compareTo(pivot) < 0) // 从左向右找出比pivot大的数，i位置挖坑
					i++;
				if (i < j) // 把挖出的数array[i]填入右边的坑内，即j位置，然后j--
					array[j--] = array[i];
			}

			// 最后i==j，是最后一个坑，把pivot填入坑内，这样pivot左边的数都小于它，pivot右边的数都大于它
			array[i] = pivot;

			quickSort(array, l, i - 1); // 分治法，pivot右边的区域再进行排序
			quickSort(array, i + 1, r); // 分治法，pivot左边的区域再进行排序
			// 最后当l==r时排序完成
		}
	}

	/**
	 * 选择排序
	 *
	 * @param array
	 */
	public static <T extends Comparable<T>> void selectSort(T[] array) {
		// 每趟选择出对应区间的最小值，放到有序序列末尾
		for (int i = 0; i < array.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < array.length; j++) {
				if (array[j].compareTo(array[minIndex]) < 0)
					minIndex = j;
			}
			if (minIndex != i) {
				swap(array, minIndex, i);
			}
		}
	}

	/**
	 * 直接插入排序。工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
	 *
	 * @param array
	 */
	public static <T extends Comparable<T>> void insertSort(T[] array) {
		int i, j, len = array.length;
		// 从a[1]、a[2]...a[len]插入到前面已经排序好的序列中
		for (i = 1; i < len; i++) {
			T temp = array[i]; // 保存待插入数据，因为这个位置会被前面的数据后移覆盖掉
			// 从前面有序序列末尾开始扫描，如果有序序列中的某个数据大于待插入数据，则后移一位
			for (j = i - 1; j >= 0 && array[j].compareTo(temp) > 0; j--) {
				array[j + 1] = array[j];
			}
			// 把待插入数据插入到正确的位置。j+1是因为for循环中最后多减了1
			array[j + 1] = temp;
		}
	}

	/**
	 * （最大）堆排序 因为堆是一个完全二叉树结构，所以可以采用一维数组顺序存储，数组头为堆顶
	 * 堆具有如下性质：父结点一定比子结点大（最大堆）或小（最小堆）； 已知父结点下标i，则左孩子left = 2i+1，右孩子right = 2i+2
	 * 最后一个非终端结点为lastparent = floor((last - 1)/2)
	 *
	 * @param array
	 */
	public static <T extends Comparable<T>> void heapSort(T[] array) {
		// 通过最后一个叶结点找到最后一个非终端结点： parent = floor(last-1)/2, last =
		// array.length-1(最后一个下标)
		int lastParentIndex = (array.length - 2) / 2;

		// 从最后一个父结点开始调整最大堆，使父结点的值大于子结点的值，直到堆顶，最大堆构造完成
		for (int i = lastParentIndex; i >= 0; i--) {
			maxHeapify(array, array.length, i);
		}
		// 构造完后array[0]为数组中的最大值

		// 把最大值跟数组末尾的值交换，同时堆大小减一，一直循环到只剩堆顶
		for (int i = array.length - 1; i > 0; i--) {
			swap(array, 0, i);
			maxHeapify(array, i, 0); // 最大堆顶被其它值替换后要重新调整整个堆，从堆顶开始调
		}
	}

	/**
	 * 最大堆调整
	 *
	 * @param array
	 * @param heapSize
	 *            当前堆有效大小
	 * @param index
	 *            将要调整的父结点下标
	 */
	private static <T extends Comparable<T>> void maxHeapify(T[] array, int heapSize, int index) {
		int left = 2 * index + 1;
		int right = 2 * index + 2;

		int largest = index; // 最大值下标

		if (left < heapSize && array[left].compareTo(array[largest]) > 0)
			largest = left;
		if (right < heapSize && array[right].compareTo(array[largest]) > 0)
			largest = right;

		// 如果最大值不是父结点则把最大值跟父结点交换
		if (largest != index) {
			swap(array, largest, index);
			// 子结点的值改变后可能会对孙子结点造成影响（孙子结点的值>子结点的值），所以继续调整
			maxHeapify(array, heapSize, largest);
		}
	}

	/**
	 * 数组存储的完全二叉树层次结构输出（可用于输出堆结构） 关键是判断什么时候该输出换行
	 *
	 * @param array
	 */
	public static <T> void printHeapStructer(T[] array) {
		for (int i = 0, count = 1; i < array.length; i++) {
			print(array[i] + " ");
			// 2的n次幂转换成二进制，其中只有一个1后面跟了n个0；如果将这个数减一转换成二进制，仅有的那个1会变为0，
			// 而原来的那n个0会变为1；因此将原来的数与去减去1后的数字进行与运算后会发现结果为零
			// 所以判断是否2的n次幂的最快速方法是(number & number - 1) == 0

			// 堆因为是完全二叉树，每层的末尾序号+1都是2的n次幂，所以如果到达了一层的末尾就输出换行
			if (((i + 1) & i) == 0)
				println();
		}
	}
}