注释写得已经非常详细了，有兴趣的可以瞧瞧。
源码&注释
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);
}
/**
* 堆排序（太复杂，很难懂）
* <p>
* 堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。
* <p>
* 这种数据结构具有以下性质。 任意节点小于它的所有后裔，最小元在堆的根上（堆序性）。 堆总是一棵完全树。
*
* <p>
* 1.每次从数组添加一个元素来创建堆
* <p>
* 2.通过重复从堆中删除根
* <p>
* 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;
}
}
// 重建堆
private static void rebuildHeap(int[] array, int last) {
int curIndex = 0;
boolean isHeap = false;
while (!isHeap) {
int leftChildIndex = 2 * curIndex + 1;
int rightChildIndex = 2 * curIndex + 2;
int maxIndex = curIndex;
if (leftChildIndex <= last
&& array[maxIndex] < array[leftChildIndex]) {
maxIndex = leftChildIndex;
}
if (rightChildIndex <= last
&& array[maxIndex] < array[rightChildIndex]) {
maxIndex = rightChildIndex;
}
if (maxIndex != curIndex) {
swap(array, curIndex, maxIndex);
curIndex = maxIndex;
} else {
isHeap = true;
}
}
}
/**
* 测试排序算法,比较直观；写单元测试也可，更严谨。
*/
public static void main(String[] args) {
SortingUtils.debug = true;
testBubbleSort();
testSelectionSort();
testInsertionSort();
testQuickSort();
testMergeSort();
testHeapSort();
}
// 测试堆排序
private static void testHeapSort() {
println("堆排序：");
int[] heapSortArray = { 1, 13, 2, 4, 5, 7 };
quickSort(heapSortArray);
print(heapSortArray);
}
// 测试归并排序
private static void testMergeSort() {
println("归并排序：");
int[] mergeSortArray = { 1, 13, 2, 4, 5, 7 };
mergeSort(mergeSortArray);
print(mergeSortArray);
}
// 测试快速排序
private static void testQuickSort() {
println("快速排序：");
int[] quickSortArray = { 1, 13, 2, 4, 5, 7 };
quickSort(quickSortArray);
print(quickSortArray);
}
// 测试插入排序
private static void testInsertionSort() {
println("插入排序：");
int[] insertionSortArray = { 1, 13, 2, 4, 5, 7 };
insertionSort(insertionSortArray);
print(insertionSortArray);
}
// 测试选择排序
private static void testSelectionSort() {
println("选择排序：");
int[] selectionSortArray = { 1, 13, 2, 4, 5, 7 };
selectionSort(selectionSortArray);
print(selectionSortArray);
}
// 测试冒泡排序
private static void testBubbleSort() {
println("冒泡排序：");
int[] bubbleSortArray = { 1, 13, 2, 4, 5, 7 };
bubbleSort(bubbleSortArray);
print(bubbleSortArray);
}
}运行结果
冒泡排序：
[debug]1 2 4 5 7 13
[debug]1 2 4 5 7 13
1 2 4 5 7 13
选择排序：
[debug]1 7 2 4 5 13
[debug]1 5 2 4 7 13
[debug]1 4 2 5 7 13
[debug]1 2 4 5 7 13
[debug]1 2 4 5 7 13
1 2 4 5 7 13
插入排序：
[debug]1 13 2 4 5 7
[debug]1 2 13 4 5 7
[debug]1 2 4 13 5 7
[debug]1 2 4 5 13 7
[debug]1 2 4 5 7 13
1 2 4 5 7 13
快速排序：
[debug]1 2 13 4 5 7
[debug]1 2 4 13 5 7
[debug]1 2 4 5 13 7
[debug]1 2 4 5 7 13
[debug]1 2 4 5 7 13
1 2 4 5 7 13
归并排序：
1 2 4 5 7 13
堆排序：
[debug]1 2 13 4 5 7
[debug]1 2 4 13 5 7
[debug]1 2 4 5 13 7
[debug]1 2 4 5 7 13
[debug]1 2 4 5 7 13
1 2 4 5 7 13
原文链接：http://FansUnion.cn/articles/3349(小雷网-FansUnion.cn)