6种排序算法的简洁实现Java代码：冒泡、选择、插入、归并、快速、堆
jopen
11年前
注释写得已经非常详细了，有兴趣的可以瞧瞧。
源码&注释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