十大經典排序算法

1、冒泡排序（Bubble Sort）

冒泡排序是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

1.1 算法描述

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
• 針對所有的元素重複以上的步驟，除了最後一個；
• 重複步驟1~3，直到排序完成。

1.2 動圖演示

1.3 代碼實現

/**
	 * 冒泡排序 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
	 * 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。 針對所有的元素重複以上的步驟，除了最後一個。
	 * 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
	 * 
	 * @param numbers
	 * 需要排序的整型數組
	 */
	public static void bubbleSort(int[] numbers) {
		int temp = 0;
		int size = numbers.length;
		for (int i = 0; i < size - 1; i++) {
			for (int j = 0; j < size - 1 - i; j++) {
				if (numbers[j] > numbers[j + 1]) // 交換兩數位置
				{
					temp = numbers[j];
					numbers[j] = numbers[j + 1];
					numbers[j + 1] = temp;
				}
			}
		}
	}

2、選擇排序（Selection Sort）

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

2.1 算法描述

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下：

· 初始狀態：無序區為R[1..n]，有序區為空；

· 第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；

· n-1趟結束，數組有序化了。

2.2 動圖演示

2.3 代碼實現

/**
	 * 選擇排序算法 在未排序序列中找到最小元素，存放到排序序列的起始位置 再從剩餘未排序元素中繼續尋找最小元素，然後放到排序序列末尾。
	 * 以此類推，直到所有元素均排序完畢。
	 * 
	 * @param numbers
	 */
	public static void selectSort(int[] numbers) {
		int size = numbers.length; // 數組長度
		int temp = 0; // 中間變量
		for (int i = 0; i < size; i++) {
			int k = i; // 待確定的位置
			// 選擇出應該在第i個位置的數
			for (int j = size - 1; j > i; j--) {
				if (numbers[j] < numbers[k]) {
					k = j;
				}
			}
			// 交換兩個數
			temp = numbers[i];
			numbers[i] = numbers[k];
			numbers[k] = temp;
		}
	}

2.4 算法分析

表現最穩定的排序算法之一，因為無論什麼數據進去都是O(n2)的時間複雜度，所以用到它的時候，數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

3.1 算法描述

一般來說，插入排序都採用in-place在數組上實現。具體算法描述如下：

· 從第一個元素開始，該元素可以認為已經被排序；

· 取出下一個元素，在已經排序的元素序列中從後向前掃描；

· 如果該元素（已排序）大於新元素，將該元素移到下一位置；

· 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置；

· 將新元素插入到該位置後；

· 重複步驟2~5。

3.2 動圖演示

3.3 代碼實現

/**
	 * 插入排序
	 * 
	 * 從第一個元素開始，該元素可以認為已經被排序 取出下一個元素，在已經排序的元素序列中從後向前掃描
	 * 如果該元素（已排序）大於新元素，將該元素移到下一位置 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置 將新元素插入到該位置中 重複步驟2
	 * 
	 * @param numbers
	 * 待排序數組
	 */
	public static void insertSort(int[] numbers) {
		int size = numbers.length;
		int temp = 0;
		int j = 0;
		for (int i = 0; i < size; i++) {
			temp = numbers[i];
			// 假如temp比前面的值小，則將前面的值後移
			for (j = i; j > 0 && temp < numbers[j - 1]; j--) {
				numbers[j] = numbers[j - 1];
			}
			numbers[j] = temp;
		}
	}

3.4 算法分析

插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

4、希爾排序（Shell Sort）

1959年Shell發明，第一個突破O(n²)的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在於，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。

4.1 算法描述

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述：

• 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列個數k，對序列進行k 趟排序；
• 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表
• 進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序
• 列的長度。

4.2 動圖演示

4.3 代碼實現

/**

* 希爾排序的原理:根據需求，如果你想要結果從大到小排列，它會首先將數組進行分組，然後將較大值移到前面，較小值

* 移到後面，最後將整個數組進行插入排序，這樣比起一開始就用插入排序減少了數據交換和移動的次數，可以說希爾排序是加強 版的插入排序 拿數組5, 2,

* 8, 9, 1, 3，4來說，數組長度為7，當increment為3時，數組分為兩個序列

* 5，2，8和9，1，3，4，第一次排序，9和5比較，1和2比較，3和8比較，4和比其下標值小increment的數組值相比較

* 此例子是按照從大到小排列，所以大的會排在前面，第一次排序後數組為9, 2, 8, 5, 1, 3，4

* 第一次後increment的值變為3/2=1,此時對數組進行插入排序， 實現數組從大到小排

*/

public static void shellSort(int[] data) {

int j = 0;

int temp = 0;

// 每次將步長縮短為原來的一半

for (int increment = data.length / 2; increment > 0; increment /= 2) {

for (int i = increment; i < data.length; i++) {

temp = data[i];

for (j = i; j >= increment; j -= increment) {

if (temp > data[j - increment])// 如想從小到大排只需修改這裡

{

data[j] = data[j - increment];

} else {

break;

}

}

data[j] = temp;

}

}

}

4.4 算法分析

希爾排序的核心在於間隔序列的設定。既可以提前設定好間隔序列，也可以動態的定義間隔序列。動態定義間隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

5、歸併排序（Merge Sort）

歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。

5.1 算法描述

• 把長度為n的輸入序列分成兩個長度為n/2的子序列；
• 對這兩個子序列分別採用歸併排序；
• 將兩個排序好的子序列合併成一個最終的排序序列。

5.2 動圖演示

5.3 代碼實現

/**

* 歸併排序 簡介:將兩個（或兩個以上）有序表合併成一個新的有序表

* 即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列 時間複雜度為O(nlogn) 穩定排序方式

*

* @param nums

* 待排序數組

* @return 輸出有序數組

*/

public static int[] sort(int[] nums, int low, int high) {

int mid = (low + high) / 2;

if (low < high) {

// 左邊

sort(nums, low, mid);

// 右邊

sort(nums, mid + 1, high);

// 左右歸併

merge(nums, low, mid, high);

}

return nums;

}

/**

* 將數組中low到high位置的數進行排序

*

* @param nums

* 待排序數組

* @param low

* 待排的開始位置

* @param mid

* 待排中間位置

* @param high

* 待排結束位置

*/

public static void merge(int[] nums, int low, int mid, int high) {

int[] temp = new int[high - low + 1];

int i = low;// 左指針

int j = mid + 1;// 右指針

int k = 0;

// 把較小的數先移到新數組中

while (i <= mid && j <= high) {

if (nums[i] < nums[j]) {

temp[k++] = nums[i++];

} else {

temp[k++] = nums[j++];

}

}

// 把左邊剩餘的數移入數組

while (i <= mid) {

temp[k++] = nums[i++];

}

// 把右邊邊剩餘的數移入數組

while (j <= high) {

temp[k++] = nums[j++];

}

// 把新數組中的數覆蓋nums數組

for (int k2 = 0; k2 < temp.length; k2++) {

nums[k2 + low] = temp[k2];

}

}

5.4 算法分析

歸併排序是一種穩定的排序方法。和選擇排序一樣，歸併排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是O(nlogn）的時間複雜度。代價是需要額外的內存空間。

6、快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

6.1 算法描述

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

• 從數列中挑出一個元素，稱為 “基準”（pivot）；
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準
• 的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位
• 置。這個稱為分區（partition）操作；
• 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

6.2 動圖演示

6.3 代碼實現

/**
	 * 查找出中軸（默認是最低位low）的在numbers數組排序後所在位置
	 * 
	 * @param numbers
	 * 帶查找數組
	 * @param low
	 * 開始位置
	 * @param high
	 * 結束位置
	 * @return 中軸所在位置
	 */
	public static int getMiddle(int[] numbers, int low, int high) {
		int temp = numbers[low]; // 數組的第一個作為中軸
		while (low < high) {
			while (low < high && numbers[high] > temp) {
				high--;
			}
			numbers[low] = numbers[high];// 比中軸小的記錄移到低端
			while (low < high && numbers[low] < temp) {
				low++;
			}
			numbers[high] = numbers[low]; // 比中軸大的記錄移到高端
		}
		numbers[low] = temp; // 中軸記錄到尾
		return low; // 返回中軸的位置
	}
	/**
	 * 
	 * @param numbers
	 * 帶排序數組
	 * @param low
	 * 開始位置
	 * @param high
	 * 結束位置
	 */
	public static void quickSort(int[] numbers, int low, int high) {
		if (low < high) {
			int middle = getMiddle(numbers, low, high); // 將numbers數組進行一分為二
			quickSort(numbers, low, middle - 1); // 對低字段表進行遞歸排序
			quickSort(numbers, middle + 1, high); // 對高字段表進行遞歸排序
		}
	}
	/**
	 * 快速排序
	 * 
	 * @param numbers
	 * 帶排序數組
	 */
	public static void quick(int[] numbers) {
		if (numbers.length > 0) {// 查看數組是否為空
			quickSort(numbers, 0, numbers.length - 1);
		}
	}
	/**
	 * 打印函數
	 * 
	 * @param numbers
	 */
	public static void printArr(int[] numbers) {
		for (int i = 0; i < numbers.length; i++) {
			System.out.print(numbers[i] + ",");
		}
		System.out.println("");
	}

6.4算法分析

快速排序是通常被認為在同數量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取基準記錄，即將排序區間的兩個端點與中點三個記錄關鍵碼居中的調整為支點記錄。快速排序是一個不穩定的排序方法。

7、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

7.1 算法描述

• 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；
• 將堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的
• 有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
• 由於交換後新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調
• 整為新堆，然後再次將R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2….Rn-2)
• 和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程
• 完成。

7.2 動圖演示

7.3 代碼實現

public static void main(String[] args) {

int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64 };

int arrayLength = a.length;

// 循環建堆

for (int i = 0; i < arrayLength - 1; i++) {

// 建堆

buildMaxHeap(a, arrayLength - 1 - i);

// 交換堆頂和最後一個元素

swap(a, 0, arrayLength - 1 - i);

System.out.println(Arrays.toString(a));

}

}

// 對data數組從0到lastIndex建大頂堆

public static void buildMaxHeap(int[] data, int lastIndex) {

// 從lastIndex處節點（最後一個節點）的父節點開始

for (int i = (lastIndex - 1) / 2; i >= 0; i--) {

// k保存正在判斷的節點

int k = i;

// 如果當前k節點的子節點存在

while (k * 2 + 1 <= lastIndex) {

// k節點的左子節點的索引

int biggerIndex = 2 * k + 1;

// 如果biggerIndex小於lastIndex，即biggerIndex+1代表的k節點的右子節點存在

if (biggerIndex < lastIndex) {

// 若果右子節點的值較大

if (data[biggerIndex] < data[biggerIndex + 1]) {

// biggerIndex總是記錄較大子節點的索引

biggerIndex++;

}

}

// 如果k節點的值小於其較大的子節點的值

if (data[k] < data[biggerIndex]) {

// 交換他們

swap(data, k, biggerIndex);

// 將biggerIndex賦予k，開始while循環的下一次循環，重新保證k節點的值大於其左右子節點的值

k = biggerIndex;

} else {

break;

}

}

}

}

// 交換

private static void swap(int[] data, int i, int j) {

int tmp = data[i];

data[i] = data[j];

data[j] = tmp;

}

8、計數排序（Counting Sort）

計數排序不是基於比較的排序算法，其核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。 作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。

8.1 算法描述

• 找出待排序的數組中最大和最小的元素；
• 統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
• 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
• 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1。

8.2 動圖演示

8.3 代碼實現

private static int[] countingSort(int[] arr, int maxValue) {
		int[] bucket = new int[maxValue + 1];
		int sortedIndex = 0;
		int arrLen = arr.length;
		int bucketLen = maxValue + 1;
		for (int i = 0; i < arrLen; i++) {
			if (bucket[arr[i]] != 0) {
				bucket[arr[i]] = 0;
			}
			bucket[arr[i]]++;
		}
		for (int j = 0; j < bucketLen; j++) {
			while (bucket[j] > 0) {
				arr[sortedIndex++] = j;
				bucket[j]--;
			}
		}
		return arr;
	}

9、桶排序（Bucket Sort）

桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分佈，將數據分到有限數量的桶裡，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排）。

9.1 算法描述

• 設置一個定量的數組當作空桶；
• 遍歷輸入數據，並且把數據一個一個放到對應的桶裡去；
• 對每個不是空的桶進行排序；
• 從不是空的桶裡把排好序的數據拼接起來。

9.2 圖片演示

9.3 代碼實現

public static void bucketSort(int[] arr) {
		System.out.println("排序前數組：" + Arrays.toString(arr));
		System.out.println();
		// 尋找數組中min，max，用於建桶
		int min = 0, max = 0;
		for (int i = 0; i <= arr.length - 1; i++) {
			if (arr[i] < min) {
				min = arr[i];
			}
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		System.out.println("預處理信息：" + "min：" + min + " " + "max：" + max);
		System.out.println();
		// 開始建桶，注意桶的數量等於max - min + 1
		System.out.println("排序過程中桶狀態：");
		int bucketCount = max - min + 1;
		System.out.println("桶個數：" + bucketCount + ",桶下標範圍0~" + (bucketCount - 1));
		int[] bucket = new int[bucketCount];
		for (int i = 0; i <= arr.length - 1; i++) {
			bucket[arr[i] - min]++;
		}
		System.out.println(Arrays.toString(bucket));
		for (int i = 1; i < bucketCount; i++) {
			bucket[i] = bucket[i] + bucket[i - 1];
		}
		System.out.println(Arrays.toString(bucket));
		System.out.println();
		// 開始排序
		int[] copy = new int[arr.length];
		System.arraycopy(arr, 0, copy, 0, arr.length);
		// 從後往前排序，保持元素相對位置，保證算法穩定性。
		for (int i = arr.length - 1; i >= 0; i--) {
			arr[--bucket[copy[i] - min]] = copy[i];
		}
		// 若從前往後排序，雖然排序結果相同，但會破壞元素相對位置和算法穩定性
		// for(int i = 0; i <= arr.length - 1; i++){
		// arr[--bucket[copy[i] - min]] = copy[i];
		// }
		System.out.println("排序後數組：" + Arrays.toString(arr));
	}

9.4 算法分析

桶排序最好情況下使用線性時間O(n)，桶排序的時間複雜度，取決與對各個桶之間數據進行排序的時間複雜度，因為其它部分的時間複雜度都為O(n)。很顯然，桶劃分的越小，各個桶之間的數據越少，排序所用的時間也會越少。但相應的空間消耗就會增大。

10、基數排序（Radix Sort）

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。

10.1 算法描述

• 取得數組中的最大數，並取得位數；
• arr為原始數組，從最低位開始取每個位組成radix數組；
• 對radix進行計數排序（利用計數排序適用於小範圍數的特點）；

10.2 動圖演示

10.3 代碼實現

private static void radixSort(int[] array, int d) {

int n = 1;// 代表位數對應的數：1,10,100...

int k = 0;// 保存每一位排序後的結果用於下一位的排序輸入

int length = array.length;

int[][] bucket = new int[10][length];// 排序桶用於保存每次排序後的結果，這一位上排序結果相同的數字放在同一個桶裡

int[] order = new int[length];// 用於保存每個桶裡有多少個數字

while (n < d) {

for (int num : array) // 將數組array裡的每個數字放在相應的桶裡

{

int digit = (num / n) % 10;

bucket[digit][order[digit]] = num;

order[digit]++;

}

for (int i = 0; i < length; i++)// 將前一個循環生成的桶裡的數據覆蓋到原數組中用於保存這一位的排序結果

{

if (order[i] != 0)// 這個桶裡有數據，從上到下遍歷這個桶並將數據保存到原數組中

{

for (int j = 0; j < order[i]; j++) {

array[k] = bucket[i][j];

k++;

}

}

order[i] = 0;// 將桶裡計數器置0，用於下一次位排序

}

n *= 10;

k = 0;// 將k置0，用於下一輪保存位排序結果

}

}

public static void main(String[] args) {

int[] A = new int[] { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };

radixSort(A, 100);

for (int num : A) {

System.out.println(num);

}

}

10.4 算法分析

基數排序基於分別排序，分別收集，所以是穩定的。但基數排序的性能比桶排序要略差，每一次關鍵字的桶分配都需要O(n)的時間複雜度，而且分配之後得到新的關鍵字序列又需要O(n)的時間複雜度。假如待排數據可以分為d個關鍵字，則基數排序的時間複雜度將是O(d*2n) ，當然d要遠遠小於n，因此基本上還是線性級別的。

基數排序的空間複雜度為O(n+k)，其中k為桶的數量。一般來說n>>k，因此額外空間需要大概n個左右。