八大排序算法實(shí)戰(zhàn)：思想與實(shí)現(xiàn)
2018-07-20 來源：編程學(xué)習(xí)網(wǎng)
摘要：
所謂排序，就是根據(jù)排序碼的遞增或者遞減順序把數(shù)據(jù)元素依次排列起來，使一組任意排列的元素變?yōu)橐唤M按其排序碼線性有序的元素。本文將介紹八種最為經(jīng)典常用的內(nèi)部排序算法的基本思想與實(shí)現(xiàn)，包括插入排序(直接插入排序，希爾排序)、選擇排序(直接選擇排序，堆排序)、交換排序(冒泡排序，快速排序)、歸并排序、分配排序(基數(shù)排序)，并給出各種算法的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。
友情提示：
若讀者需要本博文相關(guān)完整代碼，請(qǐng)移步我的Github自行獲取，項(xiàng)目名為 DataStructure(具體算法實(shí)現(xiàn)在cn.tju.edu.rico.sort包)，項(xiàng)目鏈接地址為：https://github.com/githubofrico/DataStructure。
一. 排序算法概述
所謂排序，就是根據(jù)排序碼的遞增或者遞減順序把數(shù)據(jù)元素依次排列起來，使一組任意排列的元素變?yōu)橐唤M按其排序碼線性有序的元素。本文將介紹八種最為經(jīng)典常用的內(nèi)部排序算法，包括插入排序(直接插入排序，希爾排序)、選擇排序(直接選擇排序，堆排序)、交換排序(冒泡排序，快速排序)、歸并排序、分配排序(基數(shù)排序)。實(shí)際上，無論是基本排序方法(直接插入排序，直接選擇排序，冒泡排序)，還是高效排序方法(快速排序，堆排序，歸并排序)等，它們各有所長(zhǎng)，都擁有特定的使用場(chǎng)景。因此，在實(shí)際應(yīng)用中，我們必須根據(jù)實(shí)際任務(wù)的特點(diǎn)和各種排序算法的特性來做出最合適的選擇。一般地，我們衡量一個(gè)算法的指標(biāo)包括：
-
時(shí)間復(fù)雜度 (在排序過程中需要比較和交換的次數(shù))
-
空間復(fù)雜度 (在排序過程中需要的輔助存儲(chǔ)空間)
-
穩(wěn)定性 (該算法的實(shí)現(xiàn)是否可以保證排序后相等元素的初始順序，只要該算法存在一種實(shí)現(xiàn)可以保證這種特征，那么該算法就是穩(wěn)定的)
-
內(nèi)部排序/外部排序 (在排序過程中數(shù)據(jù)元素是否完全在內(nèi)存)
筆者將在本文著重探討上述八種排序算法的思想和實(shí)現(xiàn)，并就各算法根據(jù)以上指標(biāo)進(jìn)行分析和歸類，以便進(jìn)一步熟悉它們各自的應(yīng)用場(chǎng)景。
二. 插入排序
插入排序的基本思想：每步將一個(gè)待排序元素，按其排序碼大小插入到前面已經(jīng)排好序的一組元素中，直到元素全部插入為止。在這里，我們介紹三種具體的插入排序算法：直接插入排序，希爾排序與折半插入排序。
1、直接插入排序
直接插入排序的思想：當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的V[0],…,V[i-1]等i-1個(gè) 元素已經(jīng)有序。這時(shí)，將第i個(gè)元素與前i-1個(gè)元素V[i-1]，…，V[0]依次比較，找到插入位置即將V[i]插入，同時(shí)原來位置上的元素向后順移。在這里，插入位置的查找是順序查找。直接插入排序是一種穩(wěn)定的排序算法，其實(shí)現(xiàn)如下：
/**
* Title: 插入排序中的直接插入排序，依賴于初始序列
* Description: 在有序序列中不斷插入新的記錄以達(dá)到擴(kuò)大有序區(qū)到整個(gè)數(shù)組的目的
* 時(shí)間復(fù)雜度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空間復(fù)雜度：O(1)
* 穩(wěn) 定 性：穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightInsertionSort {
public static int[] insertSort(int[] target){
if(target != null && target.length != 1){ // 待排序數(shù)組不為空且長(zhǎng)度大于1
for (int i = 1; i < target.length; i++) { // 不斷擴(kuò)大有序序列，直到擴(kuò)展到整個(gè)數(shù)組
for (int j = i; j > 0; j--) { // 向有序序列中插入新的元素
if(target[j] < target[j-1]){ // 交換
int temp = target[j];
target[j] = target[j-1];
target[j-1] = temp;
}
}
}
}
return target;
}
}
2、希爾排序
希爾排序的思想：設(shè)待排序序列共n個(gè)元素，首先取一個(gè)整數(shù)gap<n作為間隔，將全部元素分為間隔為gap的gap個(gè)子序列并對(duì)每一個(gè)子序列進(jìn)行直接插入排序。然后，縮小間隔gap，重復(fù)上述操作，直至gap縮小為1，此時(shí)所有元素位于同一個(gè)序列且有序。由于剛開始時(shí)，gap較大，每個(gè)子序列元素較少，排序速度較快；待到排序后期，gap變小，每個(gè)子序列元素較多，但大部分元素基本有序，所以排序速度仍較快。一般地，gap取 （gap/3 + 1）。希爾排序是一種不穩(wěn)定的排序方法，其實(shí)現(xiàn)如下：
/**
* Title: 插入排序中的希爾排序，依賴于初始序列
* Description: 分別對(duì)間隔為gap的gap個(gè)子序列進(jìn)行直接插入排序，不斷縮小gap,直至為 1
*
* 剛開始時(shí)，gap較大，每個(gè)子序列元素較少，排序速度較快；
* 待到排序后期，gap變小，每個(gè)子序列元素較多，但大部分元素基本有序，所以排序速度仍較快。
*
* 時(shí)間復(fù)雜度：O(n) ~ O(n^2)
* 空間復(fù)雜度：O(1)
* 穩(wěn) 定 性：不穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class ShellSort {
public static int[] shellSort(int[] target){
if(target != null && target.length != 1){
int gap = target.length; // gap個(gè)大小為gap的子序列
do{
gap = gap/3 + 1; // 不斷縮小gap直至為1
for (int i = 0 + gap; i < target.length; i++) { // 對(duì)每個(gè)子序列進(jìn)行直接插入排序
if(target[i] < target[i-gap]){
int j = i - gap;
int temp = target[i]; // 待插入值
do{
target[j + gap] = target[j]; // 后移元素
j = j - gap; // 再比較前一個(gè)元素
}while(j >= 0 && target[j] > temp); // 向前比較的終止條件
target[j + gap] = temp; // 將待插入值插入合適的位置
}
}
}while(gap > 1);
}
return target;
}
}
3、折半插入排序
折半插入排序的思想：當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的V[0],…,V[i-1]等i-1個(gè) 元素已經(jīng)有序。這時(shí)，折半搜索第i個(gè)元素在前i-1個(gè)元素V[i-1]，…，V[0]中的插入位置，然后直接將V[i]插入，同時(shí)原來位置上的元素向后順移。與直接插入排序不同的是，折半插入排序比直接插入排序明顯減少了關(guān)鍵字之間的比較次數(shù)，但是移動(dòng)次數(shù)是沒有改變。所以，折半插入排序和插入排序的時(shí)間復(fù)雜度相同都是O（N^2），但其減少了比較次數(shù)，所以該算法仍然比直接插入排序好。折半插入排序是一種穩(wěn)定的排序算法，其實(shí)現(xiàn)如下：
/**
* Title: 插入排序中的折半插入排序，依賴于初始序列
* Description: 折半搜索出插入位置，并直接插入;與直接插入搜索的區(qū)別是，后者的搜索要快于順序搜索
* 時(shí)間復(fù)雜度：折半插入排序比直接插入排序明顯減少了關(guān)鍵字之間的比較次數(shù)，但是移動(dòng)次數(shù)是沒有改變。所以，
* 折半插入排序和插入排序的時(shí)間復(fù)雜度相同都是O（N^2），在減少了比較次數(shù)方面它確實(shí)相當(dāng)優(yōu)秀，所以該算法仍然比直接插入排序好。
* 空間復(fù)雜度：O(1)
* 穩(wěn) 定 性：穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
* @author rico
* @created 2017年5月25日 下午12:03:23
*/
public class BinaryInsertSort {
public static int[] binaryInsertSort(int[] target) {
if (target != null && target.length > 1) {
for (int i = 1; i < target.length; i++) {
int left = 0;
int right = i - 1;
int mid;
int temp = target[i];
if(temp < target[right]){ // 當(dāng)前值小于有序序列的最大值時(shí)，開始查找插入位置
while(left <= right){
mid = (left + right)/2;
if(target[mid] < temp){
left = mid + 1; // 縮小插入?yún)^(qū)間
}else if(target[mid] > temp){
right = mid - 1; // 縮小插入?yún)^(qū)間
}else{ // 待插入值與有序序列中的target[mid]相等，保證穩(wěn)定性的處理
left = left + 1;
}
}
// left及其后面的數(shù)據(jù)順序向后移動(dòng)，并在left位置插入
for (int j = i; j > left; j--) {
target[j] = target[j-1];
}
target[left] = temp;
}
}
}
return target;
}
}
三. 選擇排序
選擇排序的基本思想：每一趟 (例如第i趟，i = 0,1,…)在后面第n-i個(gè)待排序元素中選出最小元素作為有序序列的第i個(gè)元素，直到第n-1趟結(jié)束后，所有元素有序。在這里，我們介紹兩種具體的選擇排序算法：直接選擇排序與堆排序。
1、直接選擇排序
直接選擇排序的思想：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R1~R[n-1]中選取最小值，與R1交換，….，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，…..，第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個(gè)按排序碼從小到大排列的有序序列。直接選擇排序是一種不穩(wěn)定的排序算法，其實(shí)現(xiàn)如下：
/**
* Title: 選擇排序中的直接選擇排序，依賴于初始序列
* Description: 每一趟 (例如第i趟，i = 0,1,...)在后面第n-i個(gè)待排序元素中選出最小元素作為有序序列的第i個(gè)元素
* 時(shí)間復(fù)雜度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)
* 空間復(fù)雜度：O(1)
* 穩(wěn) 定 性：不穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightSelectSort {
public static int[] selectSort(int[] target){
if(target != null && target.length != 1){
for (int i = 0; i < target.length; i++) {
int min_index = i;
for (int j = i + 1; j < target.length; j++) {
if(target[min_index] > target[j]){
min_index = j;
}
}
if(target[min_index] != target[i]){ // 導(dǎo)致不穩(wěn)定的因素：交換
int min = target[min_index];
target[min_index] = target[i];
target[i] = min;
}
}
}
return target;
}
}
2、堆排序
堆排序的核心是堆調(diào)整算法。首先根據(jù)初始輸入數(shù)據(jù)，利用堆調(diào)整算法shiftDown()形成初始堆；然后，將堆頂元素與堆尾元素交換，縮小堆的范圍并重新調(diào)整為堆，如此往復(fù)。堆排序是一種不穩(wěn)定的排序算法，其實(shí)現(xiàn)如下：
/**
* Title: 堆排序(選擇排序)，升序排序(最大堆)，依賴于初始序列
* Description: 現(xiàn)將給定序列調(diào)整為最大堆，然后每次將堆頂元素與堆尾元素交換并縮小堆的范圍，直到將堆縮小至1
* 時(shí)間復(fù)雜度：O(nlgn)
* 空間復(fù)雜度：O(1)
* 穩(wěn) 定 性：不穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
* @author rico
* @created 2017年5月25日 上午9:48:06
*/
public class HeapSort {
public static int[] heapSort(int[] target) {
if (target != null && target.length > 1) {
// 調(diào)整為最大堆
int pos = (target.length - 2) / 2;
while (pos >= 0) {
shiftDown(target, pos, target.length - 1);
pos--;
}
// 堆排序
for (int i = target.length-1; i > 0; i--) {
int temp = target[i];
target[i] = target[0];
target[0] = temp;
shiftDown(target, 0, i-1);
}
return target;
}
return target;
}
/**
* @description 自上而下調(diào)整為最大堆
* @author rico
* @created 2017年5月25日 上午9:45:40
* @param target
* @param start
* @param end
*/
private static void shiftDown(int[] target, int start, int end) {
int i = start;
int j = 2 * start + 1;
int temp = target[i];
while (j <= end) { // 迭代條件
if (j < end && target[j + 1] > target[j]) { //找出較大子女
j = j + 1;
}
if (target[j] <= temp) { // 父親大于子女
break;
} else {
target[i] = target[j];
i = j;
j = 2 * j + 1;
}
}
target[i] = temp;
}
}
四. 交換排序
交換排序的基本思想：根據(jù)序列中兩個(gè)元素的比較結(jié)果來對(duì)換這兩個(gè)記錄在序列中的位置，也就是說，將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)。
1、冒泡排序
冒泡排序的思想：根據(jù)序列中兩個(gè)元素的比較結(jié)果來對(duì)換這兩個(gè)記錄在序列中的位置，將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)。因此，每一趟都將較小的元素移到前面，較大的元素自然就逐漸沉到最后面了，也就是說，最大的元素最后才能確定，這就是冒泡。冒泡排序是一種穩(wěn)定的排序算法，其實(shí)現(xiàn)如下：
/**
* Title: 交換排序中的冒泡排序 ，一般情形下指的是優(yōu)化后的冒泡排序，最多進(jìn)行n-1次比較，依賴于初始序列
* Description:因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端(最后位置)，最大的數(shù)最后才確定下來，所以稱為冒泡排序
* 時(shí)間復(fù)雜度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空間復(fù)雜度：O(1)
* 穩(wěn) 定 性：穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class BubbleSort {
/**
* @description 樸素冒泡排序(共進(jìn)行n-1次比較)
* @author rico
*/
public static int[] bubbleSort(int[] target) {
int n = target.length;
if (target != null && n != 1) {
// 最多需要進(jìn)行n-1躺，每一趟將比較小的元素移到前面，比較大的元素自然就逐漸沉到最后面了，這就是冒泡
for (int i = 0; i < n-1; i++) {
for (int j = n-1; j > i; j--) {
if(target[j] < target[j-1]){
int temp = target[j];
target[j] = target[j-1];
target[j-1] = temp;
}
}
System.out.println(Arrays.toString(target));
}
}
return target;
}
/**
* @description 優(yōu)化冒泡排序
* @author rico
*/
public static int[] optimizeBubbleSort(int[] target) {
int n = target.length;
if (target != null && n != 1) {
// 最多需要進(jìn)行n-1躺，每一趟將比較小的元素移到前面，比較大的元素自然就逐漸沉到最后面了，這就是冒泡
for (int i = 0; i < n-1; i++) {
boolean exchange = false;
for (int j = n-1; j > i; j--) {
if(target[j] < target[j-1]){
int temp = target[j];
target[j] = target[j-1];
target[j-1] = temp;
exchange = true;
}
}
System.out.println(Arrays.toString(target));
if (!exchange){ // 若 i 到 n-1 這部分元素已經(jīng)有序，則直接返回
return target;
}
}
}
return target;
}
}
2、快速排序
快速排序的思想：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小(劃分過程)，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序(快速排序過程)，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列�？焖倥判蚴且环N不穩(wěn)定的排序算法。
/**
* Title: 交換排序中的快速排序，目前應(yīng)用最為廣泛的排序算法，是一個(gè)遞歸算法，依賴于初始序列
* Description:快速排序包括兩個(gè)過程：劃分 和 快排
* "劃分"是指將原序列按基準(zhǔn)元素劃分兩個(gè)子序列
* "快排"是指分別對(duì)子序列進(jìn)行快排
*
* 就平均計(jì)算時(shí)間而言，快速排序是所有內(nèi)部排序方法中最好的一個(gè)
*
* 對(duì)大規(guī)模數(shù)據(jù)排序時(shí)，快排是快的；對(duì)小規(guī)模數(shù)據(jù)排序時(shí)，快排是慢的，甚至慢于簡(jiǎn)單選擇排序等簡(jiǎn)單排序方法
*
* 快速排序依賴于原始序列，因此其時(shí)間復(fù)雜度從O(nlgn)到O(n^2)不等
* 時(shí)間復(fù)雜度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)
*
* 遞歸所消耗的�？臻g
* 空間復(fù)雜度：O(lgn)
*
* 可選任一元素作為基準(zhǔn)元素
* 穩(wěn) 定 性：不穩(wěn)定
*
*
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class QuickSort {
/**
* @description 快排算法(遞歸算法)：在遞去過程中就把問題解決了
* @author rico
* @created 2017年5月20日 下午5:12:06
* @param target
* @param left
* @param right
* @return
*/
public static int[] quickSort(int[] target, int left, int right) {
if(right > left){ // 遞歸終止條件
int base_index = partition(target,left, right); // 原序列劃分后基準(zhǔn)元素的位置
quickSort(target, left, base_index-1); // 對(duì)第一個(gè)子序列快速排序，不包含基準(zhǔn)元素！
quickSort(target, base_index+1, right); // 對(duì)第二個(gè)子序列快速排序，不包含基準(zhǔn)元素！
return target;
}
return target;
}
/**
* @description 序列劃分，以第一個(gè)元素為基準(zhǔn)元素
* @author rico
* @created 2017年5月20日 下午5:10:54
* @param target 序列
* @param left 序列左端
* @param right 序列右端
* @return
*/
public static int partition(int[] target, int left, int right){
int base = target[left]; // 基準(zhǔn)元素的值
int base_index = left; // 基準(zhǔn)元素最終應(yīng)該在的位置
for (int i = left+1; i <= right; i++) { // 從基準(zhǔn)元素的下一個(gè)元素開始
if(target[i] < base){ // 若其小于基準(zhǔn)元素
base_index++; // 若其小于基準(zhǔn)元素,則基準(zhǔn)元素最終位置后移；否則不用移動(dòng)
if(base_index != i){ // 相等情況意味著i之前的元素都小于base,只需要換一次即可，不需要次次都換
int temp = target[base_index];
target[base_index] = target[i];
target[i] = temp;
}
}
}
// 將基準(zhǔn)元素就位
target[left] = target[base_index];
target[base_index] = base;
System.out.println(Arrays.toString(target));
return base_index; //返回劃分后基準(zhǔn)元素的位置
}
}
五. 歸并排序
歸并排序包含兩個(gè)過程：”歸”和”并”。其中，”歸”是指將原序列分成半子序列，分別對(duì)子序列進(jìn)行遞歸排序；”并”是指將排好序的各子序列合并成原序列。歸并排序算法是一個(gè)典型的遞歸算法，因此也是概念上最為簡(jiǎn)單的排序算法。與快速排序算法相比，歸并排序算法不依賴于初始序列，并且是一種穩(wěn)定的排序算法，但需要與原序列一樣大小的輔助存儲(chǔ)空間。
/**
* Title: 歸并排序 ，概念上最為簡(jiǎn)單的排序算法，是一個(gè)遞歸算法，不依賴于初始序列
* Description:歸并排序包括兩個(gè)過程：歸 和 并
* "歸"是指將原序列分成半子序列，分別對(duì)子序列進(jìn)行遞歸排序
* "并"是指將排好序的各子序列合并成原序列
*
* 歸并排序的主要問題是：需要一個(gè)與原待排序數(shù)組一樣大的輔助數(shù)組空間
*
* 歸并排序不依賴于原始序列，因此其最好情形、平均情形和最差情形時(shí)間復(fù)雜度都一樣
* 時(shí)間復(fù)雜度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空間復(fù)雜度：O(n)
* 穩(wěn) 定 性：穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class MergeSort {
/**
* @description 歸并排序算法(遞歸算法)：遞去分解，歸來合并
* @author rico
* @created 2017年5月20日 下午4:04:52
* @param target 待排序序列
* @param left 待排序序列起始位置
* @param right 待排序序列終止位置
* @return
*/
public static int[] mergeSort(int[] target, int left, int right) {
if(right > left){ // 遞歸終止條件
int mid = (left + right)/2;
mergeSort(target, left, mid); // 歸并排序第一個(gè)子序列
mergeSort(target, mid+1, right); // 歸并排序第二個(gè)子序列
return merge(target,left,mid,right); // 合并子序列成原序列
}
return target;
}
/**
* @description 兩路歸并算法
* @author rico
* @created 2017年5月20日 下午3:59:16
* @param target 用于存儲(chǔ)歸并結(jié)果
* @param left 第一個(gè)有序表的第一個(gè)元素所在位置
* @param mid 第一個(gè)有序表的最后一個(gè)元素所在位置
* @param right 第二個(gè)有序表的最后一個(gè)元素所在位置
* @return
*/
public static int[] merge(int[] target, int left, int mid, int right){
// 需要一個(gè)與原待排序數(shù)組一樣大的輔助數(shù)組空間
int[] temp = Arrays.copyOf(target, target.length);
// s1,s2是檢查指針，index 是存放指針
int s1 = left;
int s2 = mid + 1;
int index = left;
// 兩個(gè)表都未檢查完，兩兩比較
while(s1 <= mid && s2 <= right){
if(temp[s1] <= temp[s2]){ // 穩(wěn)定性
target[index++] = temp[s1++];
}else{
target[index++] = temp[s2++];
}
}
//若第一個(gè)表未檢查完，復(fù)制
while(s1 <= mid){
target[index++] = temp[s1++];
}
//若第二個(gè)表未檢查完，復(fù)制
while(s2 <= right){
target[index++] = temp[s2++];
}
return target;
}
}
Ps : 歸并排序和快速排序都是典型的遞歸算法，因此它們比較容易理解和實(shí)現(xiàn)。關(guān)于遞歸思想和內(nèi)涵深度剖析，請(qǐng)見博文《算法設(shè)計(jì)方法：遞歸的內(nèi)涵與經(jīng)典應(yīng)用》。
六. 分配排序(基數(shù)排序)
分配排序的基本思想：用空間換時(shí)間。在整個(gè)排序過程中，無須比較關(guān)鍵字，而是通過用額外的空間來”分配”和”收集”來實(shí)現(xiàn)排序，它們的時(shí)間復(fù)雜度可達(dá)到線性階：O(n)。其中，基數(shù)排序包括兩個(gè)過程：首先，將目標(biāo)序列各元素分配到各個(gè)桶中(分配過程)；然后，將各個(gè)桶中的元素按先進(jìn)先出的順序再放回去(收集過程)，如此往復(fù)，一共需要進(jìn)行d趟，d為元素的位數(shù)。
/**
* Title: 分配排序中的基數(shù)排序，不依賴于初始序列
* Description: 不是在對(duì)元素進(jìn)行比較的基礎(chǔ)上進(jìn)行排序，而是采用 "分配 + 收集" 的辦法
*
* 首先，將目標(biāo)序列各元素分配到各個(gè)桶中；
* 其次，將各個(gè)桶中的元素按先進(jìn)先出的順序再放回去
* 如此往復(fù)...
*
* 時(shí)間復(fù)雜度：O(d*(r+n))或者 O(dn),d 的大小一般會(huì)受到 n的影響
* 空間復(fù)雜度：O(rd + n)或者 O(n)
* 穩(wěn) 定 性：穩(wěn)定
* 內(nèi)部排序(在排序過程中數(shù)據(jù)元素完全在內(nèi)存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class RadixSort {
/**
* @description 分配 + 收集
* @author rico
* @created 2017年5月21日 下午9:25:52
* @param target 待排序數(shù)組
* @param r 基數(shù)
* @param d 元素的位數(shù)
* @param n 待排序元素個(gè)數(shù)
* @return
*/
public static int[] radixSort(int[] target, int r, int d, int n){
if (target != null && target.length != 1 ) {
int[][] bucket = new int[r][n]; // 一共有基數(shù)r個(gè)桶，每個(gè)桶最多放n個(gè)元素
int digit; // 獲取元素對(duì)應(yīng)位上的數(shù)字，即裝入那個(gè)桶
int divisor = 1; // 定義每一輪的除數(shù)，1, 10, 100, ...
int[] count = new int[r]; // 統(tǒng)計(jì)每個(gè)桶中實(shí)際存放元素的個(gè)數(shù)
for (int i = 0; i < d; i++) { // d 位的元素，需要經(jīng)過分配、收集d次即可完成排序
// 分配
for (int ele : target) {
digit = (ele/divisor) % 10; // 獲取元素對(duì)應(yīng)位上的數(shù)字(巧妙�。�！)
bucket[digit][count[digit]++] = ele; // 將元素放入對(duì)應(yīng)桶，桶中元素?cái)?shù)目加1
}
// 收集
int index = 0; // 目標(biāo)數(shù)組的下標(biāo)
for (int j = 0; j < r; j++) {
int k = 0; // 用于按照先進(jìn)先出順序獲取桶中元素
while(k < count[j]){
target[index++] = bucket[j][k++]; // 按照先進(jìn)先出依次取出桶中的元素
}
count[j] = 0; // 計(jì)數(shù)器歸零
}
divisor *= 10; //用于獲取元素對(duì)應(yīng)位數(shù)字
}
}
return target;
}
}
七. 總結(jié)
1、直接插入排序 Vs. 折半插入排序 Vs. 希爾排序
這三種排序方法都屬于插入排序的范疇。與直接插入排序的順序搜索插入位置相比，折半插入排序通過折半搜索的方法搜索插入位置，因此，在搜索插入位置方面，折半插入排序要快于直接插入排序。實(shí)際上，折半插入排序比直接插入排序只是減少了關(guān)鍵字之間的比較次數(shù)，但是移動(dòng)次數(shù)是沒有改變。所以，折半插入排序和插入排序的時(shí)間復(fù)雜度相同都是O（n^2），但減少了比較次數(shù)，所以該算法要比直接插入排序好一點(diǎn)。希爾排序可以看作是對(duì)直接插入排序的一種優(yōu)化，它將全部元素分為間隔為gap的gap個(gè)子序列并對(duì)每一個(gè)子序列進(jìn)行直接插入排序，同時(shí)不斷縮小間隔gap，直至所有元素位于同一個(gè)序列。使用這種方式可以保證排序效率，因?yàn)閯傞_始時(shí)，gap較大，每個(gè)子序列元素較少，排序速度較快；待到排序后期，gap變小，每個(gè)子序列元素較多，但大部分元素基本有序，所以排序速度仍較快。因此，希爾排序比直接插入排序 、折半插入排序都要高效，但它不是穩(wěn)定的。
2、直接選擇排序 Vs. 堆排序
這兩種排序方法都屬于插入選擇排序的范疇，它們的核心思想都是每一趟都選擇一個(gè)極值元素放在靠前/靠后位置，直到序列有序。與直接選擇排序不同的是，堆排序不是“蠻力選擇”，而是不斷進(jìn)行堆調(diào)整以取得每趟中的極值。因此，堆排序比直接選擇排序要高效，不過它們都是不穩(wěn)定的。
3、冒泡排序 Vs. 快速排序
這兩種排序方法都屬于選擇排序的范疇，它們的核心思想都是元素的交換，冒泡排序中每一趟相鄰元素互相比較，并將較小的交換到前面(較大的自然沉到后面)位置，快速排序則是以基準(zhǔn)點(diǎn)為基礎(chǔ)，將比它小的元素和比它大的元素分別交換到它的兩邊。因此，快速排序比冒泡排序要高效，但它不是穩(wěn)定的。
4、歸并排序 Vs. 快速排序
這兩種排序方法都屬于遞歸算法的范疇，因此，它們都比較容易讓人理解和實(shí)現(xiàn)。與快速排序相比，歸并排序不但是穩(wěn)定的，還是與原始序列無關(guān)的(不依賴于原始序列的順序，時(shí)間復(fù)雜度總是O(nlgn))，但是需要與原始序列一樣大小的空間；而快速排序則一般情況下都要比其他高效排序算法（包括歸并排序）快，而且空間復(fù)雜度只為O(1)。另外，我們從算法實(shí)現(xiàn)中可以看出這兩種遞歸算法有以下區(qū)別和聯(lián)系：
- 二者的遞歸終止條件相同；
- 二者的實(shí)現(xiàn)結(jié)構(gòu)較為類似，歸并排序是先歸后并，快速排序是先分后排；
- 歸并排序的核心實(shí)現(xiàn)在于有序子序列的合并，而快速排序的核心實(shí)現(xiàn)在于對(duì)原始序列的劃分；
5、小結(jié)
直接插入排序、直接選擇排序和冒泡排序是基本的排序方法，它們平均情況下的時(shí)間復(fù)雜度都是O(n^2)，實(shí)現(xiàn)也比較簡(jiǎn)單，它們對(duì)規(guī)模較小的元素序列很有效。
快速排序、堆排序和歸并排序是高效的排序方法，它們平均情況下的時(shí)間復(fù)雜度都是O(nlgn)，其中快速排序是最通用的高效排序算法，但其是不穩(wěn)定的；歸并排序是上述幾種排序算法中唯一與初始序列無關(guān)的，而且時(shí)間復(fù)雜度總是O(nlgn)，但其空間復(fù)雜度是O(n)，是一種穩(wěn)定的排序算法；堆排序的時(shí)間復(fù)雜度總是O(nlgn)，空間復(fù)雜度是O(1)，也是不穩(wěn)定的。它們對(duì)規(guī)模較大的元素序列很有效。
希爾排序的效率介于基本排序方法與高效排序方法之間，是一種不穩(wěn)定的排序算法。它們各有所長(zhǎng)，都擁有特定的使用場(chǎng)景�；鶖�(shù)排序雖然具有線性增長(zhǎng)的時(shí)間復(fù)雜度，但實(shí)際上開銷并不比快速排序小很多，應(yīng)用相對(duì)不太廣泛。
因此，在實(shí)際應(yīng)用中，我們必須根據(jù)實(shí)際任務(wù)的特點(diǎn)和各種排序算法的特性來做出最合適的選擇。
八. 更多
歸并排序和快速排序都是典型的遞歸算法，因此它們比較容易理解和實(shí)現(xiàn)。關(guān)于遞歸思想和內(nèi)涵深度剖析，請(qǐng)見博文《算法設(shè)計(jì)方法：遞歸的內(nèi)涵與經(jīng)典應(yīng)用》。
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。
