注释写得已经非常详细了，有兴趣的可以瞧瞧。
源码&注释
package cn.fansunion.common.suanfa;
/**
* 排序工具类
*
* @author LeiWen@FansUnion.cn
*
*/
public final class SortingUtils {
public static boolean debug = false;
// 不允许实例化
private SortingUtils() {
}
/**
* 冒泡排序:最容易理解的排序方法
*/
public static void bubbleSort(int[] array) {
boolean needNextPass = true;
int length = array.length;
// 遍历N-1次，从第“2”个元素开始
for (int index = 1; index < length; index++) {
// 需要下一次排序
if (needNextPass) {
needNextPass = false;
// 遍历N-index次
for (int i = 0; i < length - index; i++) {
if (array[i] > array[i + 1]) {
swap(array, i, i + 1);
// 需要下一次排序
needNextPass = true;
}
}
} else {
// 已经有序了
return;
}
debug(array);
}
}
/**
* 选择排序
*/
public static void selectionSort(int[] array) {
for (int index = array.length - 1; index >= 1; index--) {
// 假设第0个是当前最大的
int curMaxValue = array[0];
int curMaxIndex = 0;
// 查找最大的元素 array[1..index]
for (int j = 1; j <= index; j++) {
// 找到比当前值更大的元素
if (curMaxValue < array[j]) {
curMaxValue = array[j];
curMaxIndex = j;
}
}
// 交换元素
if (curMaxIndex != index) {
array[curMaxIndex] = array[index];
array[index] = curMaxValue;
}
debug(array);
}
}
/**
* 插入排序（容易理解，代码有一点难懂）
*/
public static void insertionSort(int[] array) {
int length = array.length;
for (int index = 1; index < length; index++) {
// 插入 array[index]到一个已经有序的子列表 array[0..i-1],使得 array[0..i] 是有序的。
int curElement = array[index];
int k = -1;
// 从index的前面元素中，找到一个比array[index]大的元素
for (k = index - 1; k >= 0 && array[k] > curElement; k--) {
array[k + 1] = array[k];
}
// 插入当前元素到 array[k+1]
array[k + 1] = curElement;
debug(array);
}
}
/**
* 快速排序：对所有元素排序。(递归实现，不容易理解)
*/
public static void quickSort(int[] array) {
quickSort(array, 0, array.length - 1);
}
/**
* 快速排序：对某个区间的元素进行排序。
*/
public static void quickSort(int[] array, int left, int right) {
int leftIndex = left;
int rightIndex = right;
// 选取中间的数作为主元
int middle = array[(leftIndex + rightIndex) / 2];
do {
// 在middle元素的左边，找到第1个比middle大的数
while (array[leftIndex] < middle && leftIndex < right) {
// 如果左边的数小于中间的数，则一直向右移动
// System.out.println(array[leftIndex] + "大于" + middle);
leftIndex++;
}
// 在middle元素的右边，找到第1个比middle小的数
while (array[rightIndex] > middle && rightIndex > left) {
// System.out.println(array[rightIndex] + "小于" + middle);
rightIndex--;
}
// 将左边大的数和右边的小数交换
if (leftIndex <= rightIndex) {
swap(array, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
debug(array);
} while (leftIndex <= rightIndex);// 当两者交错时停止,每遍历一次，[...]
// 递归：对子区间的元素快速排序
if (leftIndex < right) {
quickSort(array, leftIndex, right);
}
// 递归：对子区间的元素快速排序
if (rightIndex > left) {
quickSort(array, left, rightIndex);
}
}
/**
* 交换数组中的2个元素
*
* @param array
* 数组
* @param i
* 第1个索引
* @param j
* 第2个索引
*/
private static void swap(int[] array, int i, int j) {
if (array == null || array.length == 1) {
return;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* 归并排序(递归实现，不容易理解)
*/
public static void mergeSort(int[] array) {
int length = array.length;
// 长度大于1的数组，默认为“无序”；否则，默认为“有序”
if (length > 1) {
// 归并排序第一部分
int[] firstHalf = new int[length / 2];
System.arraycopy(array, 0, firstHalf, 0, length / 2);
mergeSort(firstHalf);
// 归并排序第二部分
int secondHalfLength = length - length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(array, length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// 合并第一部分和第二部分
int[] temp = merge(firstHalf, secondHalf);
System.arraycopy(temp, 0, array, 0, temp.length);
}
}
/**
* 把2个有序的数组合并成1个有序的数组
*/
private static int[] merge(int[] array1, int[] array2) {
int length1 = array1.length;
int length2 = array2.length;
int[] resultArray = new int[length1 + length2];
int curIndex1 = 0; // array1的当前索引
int curIndex2 = 0; // array2的当前索引
int curIndexTemp = 0; // temp的当前索引
while (curIndex1 < length1 && curIndex2 < length2) {
if (array1[curIndex1] < array2[curIndex2]) {
resultArray[curIndexTemp++] = array1[curIndex1++];
} else {
resultArray[curIndexTemp++] = array2[curIndex2++];
}
}
while (curIndex1 < length1) {
resultArray[curIndexTemp++] = array1[curIndex1++];
}
while (curIndex2 < length2) {
resultArray[curIndexTemp++] = array2[curIndex2++];
}
return resultArray;
}
/**
* 打印数组
*/
private static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
// 如果是debug模式，打印数组
private static void debug(int[] array) {
if (!debug) {
return;
}
System.out.print("[debug]");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
private static void println(Object object) {
System.out.println(object);
}
/**
* 堆排序（太复杂，很难懂）
*
* 堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。 *
* 这种数据结构具有以下性质。 任意节点小于它的所有后裔，最小元在堆的根上（堆序性）。 堆总是一棵完全树。 * *
* 1.每次从数组添加一个元素来创建堆 *
* 2.通过重复从堆中删除根 *
* 3.重建堆来对数组排序。 */ public static void heapSort(int array[]) { // 创建堆 for (int i = 1; i < array.length; i++) { makeHeap(array, i); } // 删除根，重建堆，使得数组有序 for (int last = array.length - 1; last > 0;) { swap(array, 0, last); rebuildHeap(array, last--); debug(array); } } /** * 假设[0..k-1]是一个堆，把array[k]加入到堆中 */ private static void makeHeap(int[] array, int k) { int curIndex = k; int middleIndex = (curIndex - 1) / 2; while (curIndex > 0 && array[curIndex] > array[middleIndex]) { swap(array, curIndex, middleIndex); curIndex = middleIndex; } }