6種排序算法的簡潔實現Java代碼：冒泡、選擇、插入、歸并、快速、堆
注釋寫得已經非常詳細了，有興趣的可以瞧瞧。
源碼&注釋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
本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！