排序是一個(gè)非常常見的應(yīng)用場(chǎng)景推捐，很多時(shí)候，我們需要根據(jù)自己需要排序的數(shù)據(jù)類型侧啼，來自定義排序算法牛柒，但是，在這里痊乾，我們只介紹這些基礎(chǔ)排序算法皮壁，包括：插入排序、選擇排序哪审、冒泡排序蛾魄、快速排序（重點(diǎn)）、堆排序湿滓、歸并排序等等滴须。看下圖：
給定數(shù)組：int data[] = {9,2,7,19,100,97,63,208,55,78}
一叽奥、直接插入排序(內(nèi)部排序扔水、O(n2)、穩(wěn)定)
原理：從待排序的數(shù)中選出一個(gè)來朝氓，插入到前面的合適位置魔市。
package com.xtfggef.algo.sort;
public class InsertSort {
static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };
public static void insertSort() {
int tmp, j = 0;
for (int k = 0; k < data.length; k++) {//-----1-----
tmp = data[k];
j = k - 1;
while (j >= 0 && tmp < data[j]) {//-----2-----
data[j + 1] = data[j];
j--;
}
data[j + 1] = tmp;//------3-------
}
}
public static void main(String[] args) {
print();
System.out.println();
insertSort();
System.out.println();
print();
}
static void print() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}
我簡(jiǎn)單的講解一下過程：思路上從待排序的數(shù)據(jù)中選出一個(gè)主届，插入到前面合適的位置，耗時(shí)點(diǎn)在插入方面待德，合適的位置意味著我們需要進(jìn)行比較找出哪是合適的位置君丁，舉個(gè)例子：對(duì)于9,2,7,19,100,97,63,208,55,78這組數(shù)，第一個(gè)數(shù)9前面沒有将宪，不做操作绘闷，當(dāng)?shù)谝粋€(gè)數(shù)完后，剩下的數(shù)就是待排序的數(shù)涧偷，我們將要從除去9開始的書中選出一個(gè)插入到前面合適的位置簸喂，拿到2后毙死，放在tmp上燎潮，進(jìn)行注釋中的2處的代碼，2處的代碼就是通過循環(huán)找出這個(gè)合適的位置扼倘，發(fā)現(xiàn)比tmp大的數(shù)确封，立即將該數(shù)向后移動(dòng)一位（這樣做的目的是：前面需要空出一位來進(jìn)行插入），最后通過注釋3處的代碼將數(shù)插入再菊。
本排序適合：基本有序的數(shù)據(jù)
二爪喘、選擇排序（O(n2)、不穩(wěn)定）
與直接插入排序正好相反纠拔，選擇排序是從待排序的數(shù)中選出最小的放在已經(jīng)排好的后面秉剑，這個(gè)算法選數(shù)耗時(shí)。
package com.xtfggef.algo.sort;
public class SelectSort {
static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };
public static void selectSort() {
int i, j, k, tmp = 0;
for (i = 0; i < data.length - 1; i++) {
k = i;
for (j = i + 1; j < data.length; j++)
if (data[j] < data[k])
k = j;
if (k != i) {
tmp = data[i];
data[i] = data[k];
data[k] = tmp;
}
}
}
public static void main(String[] args) {
print();
System.out.println();
selectSort();
System.out.println();
print();
}
static void print() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}
通過循環(huán)稠诲，找出最小的數(shù)的下標(biāo)侦鹏，賦值于k，即k永遠(yuǎn)保持待排序數(shù)據(jù)中最小的數(shù)的下標(biāo)臀叙，最后和當(dāng)前位置i互換數(shù)據(jù)即可略水。
三、快速排序（O(nlogn)劝萤、不穩(wěn)定）
快速排序簡(jiǎn)稱快排渊涝，是一種比較快的排序，適合基本無序的數(shù)據(jù)床嫌，為什么這么說呢跨释？下面我說下快排的思路：
設(shè)置兩個(gè)指針：i和j，分別指向第一個(gè)和最后一個(gè)厌处，i像后移動(dòng)鳖谈，j向前移動(dòng)，選第一個(gè)數(shù)為標(biāo)準(zhǔn)（一般這樣做嘱蛋，當(dāng)然快排的關(guān)鍵就是這個(gè)“標(biāo)準(zhǔn)”的選闰悄贰）五续，從后面開始，找到第一個(gè)比標(biāo)準(zhǔn)小的數(shù)龄恋，互換位置疙驾，然后再?gòu)那懊妫业降谝粋€(gè)比標(biāo)準(zhǔn)大的數(shù)郭毕，互換位置它碎，第一趟的結(jié)果就是標(biāo)準(zhǔn)左邊的都小于標(biāo)準(zhǔn)，右邊的都大于標(biāo)準(zhǔn)（但不一定有序）显押，分成兩撥后扳肛，繼續(xù)遞歸的使用上述方法，最終有序乘碑！代碼如下：
package com.xtfggef.algo.sort;
public class QuickSortTest {
static class QuickSort {
public int data[];
private int partition(int array[], int low, int high) {
int key = array[low];
while (low < high) {
while (low < high && array[high] >= key)
high--;
array[low] = array[high];
while (low < high && array[low] <= key)
low++;
array[high] = array[low];
}
array[low] = key;
return low;
}
public int[] sort(int low, int high) {
if (low < high) {
int result = partition(data, low, high);
sort(low, result - 1);
sort(result + 1, high);
}
return data;
}
}
static void print(int data[]) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
public static void main(String[] args) {
int data[] = { 20, 3, 10, 9, 186, 99, 200, 96, 3000 };
print(data);
System.out.println();
QuickSort qs = new QuickSort();
qs.data = data;
qs.sort(0, data.length - 1);
print(data);
}
}
看看上面的圖挖息，基本就明白了。
四兽肤、冒泡排序（穩(wěn)定套腹、基本有序可達(dá)O(n)，最壞情況為O(n2)）
冒泡排序是一種很簡(jiǎn)單资铡，不論是理解還是時(shí)間起來都比較容易的一種排序算法电禀，思路簡(jiǎn)單：小的數(shù)一點(diǎn)一點(diǎn)向前起泡，最終有序笤休。
package com.xtfggef.algo.sort;
public class BubbleSort {
static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };
public static void bubbleSort() {
int i, j, tmp = 0;
for (i = 0; i < data.length - 1; i++) {
for (j = data.length - 1; j > i; j--) {
if (data[j] < data[j - 1]) {
tmp = data[j];
data[j] = data[j - 1];
data[j - 1] = tmp;
}
}
}
}
public static void main(String[] args) {
print();
System.out.println();
bubbleSort();
System.out.println();
print();
}
static void print() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}
五尖飞、堆排序
我們這里不詳細(xì)介紹概念，堆的話店雅，大家只要記得堆是一個(gè)完全二叉樹（什么是完全二叉樹政基，請(qǐng)不懂的讀者去查資料），堆排序分為兩種堆底洗，大頂堆和小頂堆腋么，大頂堆的意思就是堆頂元素是整個(gè)堆中最大的，小頂堆的意思就是堆頂元素是整個(gè)堆中最小的亥揖，滿足：任何一非葉節(jié)點(diǎn)的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點(diǎn)的關(guān)鍵字珊擂。堆排序是一個(gè)相對(duì)難理解的過程，下面我會(huì)較為清楚费变、詳細(xì)的講解一下堆排序摧扇。堆排序分為三個(gè)過程：
建堆：從一個(gè)數(shù)組順序讀取元素，建立一個(gè)堆（完全二叉樹）
初始化：將堆進(jìn)行調(diào)整挚歧，使得堆頂為最大（最大堆）或者最锌富（最小堆）的元素
維護(hù)：將堆頂元素出堆后，需要將堆的最后一個(gè)節(jié)點(diǎn)補(bǔ)充到堆頂滑负，因?yàn)檫@樣破壞了堆的秩序在张，所以需要進(jìn)行維護(hù)用含。下面我們圖示一下：
一般情況，建堆和初始化同步進(jìn)行帮匾，
最后為如下所示啄骇，即為建堆、初始化成功瘟斜。
我們可以觀察下這個(gè)最大堆缸夹，看出堆頂是整個(gè)堆中最大的元素，而且除葉子節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都大于其子節(jié)點(diǎn)螺句。下面的過程就是當(dāng)我們輸出堆頂元素后虽惭，對(duì)堆進(jìn)行維護(hù)。
過程是這樣：將堆頂元素出堆后蛇尚，用最后一個(gè)元素補(bǔ)充堆頂元素芽唇，這樣破壞了之前的秩序，需要重新維護(hù)堆佣蓉，在堆頂元素的左右節(jié)點(diǎn)中選出較小的和堆頂互換披摄，然后一直遞歸下去，所以每次出一個(gè)元素勇凭，需要一次維護(hù)，堆排序適合解決topK問題义辕，能將復(fù)雜度降到nlogK虾标。下面是代碼：
package com.xtfggef.algo.sort;
public class HeapSort {
private static int[] sort = new int[] { 1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12,
17, 34, 11 };
public static void main(String[] args) {
buildMaxHeapify(sort);
heapSort(sort);
print(sort);
}
private static void buildMaxHeapify(int[] data) {
// 沒有子節(jié)點(diǎn)的才需要?jiǎng)?chuàng)建最大堆，從最后一個(gè)的父節(jié)點(diǎn)開始
int startIndex = getParentIndex(data.length - 1);
// 從尾端開始創(chuàng)建最大堆灌砖，每次都是正確的堆
for (int i = startIndex; i >= 0; i--) {
maxHeapify(data, data.length, i);
}
}
/**
* 創(chuàng)建最大堆
*
* @param data
* @param heapSize
* 需要?jiǎng)?chuàng)建最大堆的大小璧函，一般在sort的時(shí)候用到，因?yàn)樽疃嘀捣旁谀┪不裕┪簿筒辉贇w入最大堆了
* @param index
* 當(dāng)前需要?jiǎng)?chuàng)建最大堆的位置
*/
private static void maxHeapify(int[] data, int heapSize, int index) {
// 當(dāng)前點(diǎn)與左右子節(jié)點(diǎn)比較
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
int largest = index;
if (left < heapSize && data[index] < data[left]) {
largest = left;
}
if (right < heapSize && data[largest] < data[right]) {
largest = right;
}
// 得到最大值后可能需要交換蘸吓，如果交換了，其子節(jié)點(diǎn)可能就不是最大堆了撩幽，需要重新調(diào)整
if (largest != index) {
int temp = data[index];
data[index] = data[largest];
data[largest] = temp;
maxHeapify(data, heapSize, largest);
}
}
/**
* 排序库继，最大值放在末尾，data雖然是最大堆窜醉，在排序后就成了遞增的
*
* @param data
*/
private static void heapSort(int[] data) {
// 末尾與頭交換宪萄，交換后調(diào)整最大堆
for (int i = data.length - 1; i > 0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxHeapify(data, i, 0);
}
}
/**
* 父節(jié)點(diǎn)位置
*
* @param current
* @return
*/
private static int getParentIndex(int current) {
return (current - 1) >> 1;
}
/**
* 左子節(jié)點(diǎn)position 注意括號(hào)，加法優(yōu)先級(jí)更高
*
* @param current
* @return
*/
private static int getChildLeftIndex(int current) {
return (current << 1) + 1;
}
/**
* 右子節(jié)點(diǎn)position
*
* @param current
* @return
*/
private static int getChildRightIndex(int current) {
return (current << 1) + 2;
}
private static void print(int[] data) {
int pre = -2;
for (int i = 0; i < data.length; i++) {
if (pre < (int) getLog(i + 1)) {
pre = (int) getLog(i + 1);
System.out.println();
}
System.out.print(data[i] + " |");
}
}
/**
* 以2為底的對(duì)數(shù)
*
* @param param
* @return
*/
private static double getLog(double param) {
return Math.log(param) / Math.log(2);
}
}
慢慢理解一下榨惰，還是容易明白的拜英！
六、歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法琅催。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用居凶。
首先考慮下如何將將二個(gè)有序數(shù)列合并虫给。這個(gè)非常簡(jiǎn)單，只要從比較二個(gè)數(shù)列的第一個(gè)數(shù)侠碧，誰小就先取誰狰右，取了后就在對(duì)應(yīng)數(shù)列中刪除這個(gè)數(shù)。然后再進(jìn)行比較舆床，如果有數(shù)列為空棋蚌，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可。
package com.xtfggef.algo.sort;
public class SortTest {
// 將有序數(shù)組a[]和b[]合并到c[]中
static void MemeryArray(int a[], int n, int b[], int m, int c[]) {
int i, j, k;
i = j = k = 0;
while (i < n && j < m) {
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
public static void main(String[] args) {
int a[] = { 2, 7, 8, 10, 299 };
int b[] = { 5, 9, 14, 20, 66, 88, 92 };
int c[] = new int[a.length + b.length];
MemeryArray(a, 5, b, 7, c);
print(c);
}
private static void print(int[] c) {
for (int i = 0; i < c.length; i++) {
System.out.print(c[i] + " ");
}
}
}
可以看出合并有序數(shù)列的效率是比較高的挨队，可以達(dá)到O(n)谷暮。解決了上面的合并有序數(shù)列問題，再來看歸并排序盛垦，其的基本思路就是將數(shù)組分成二組A湿弦，B，如果這二組組內(nèi)的數(shù)據(jù)都是有序的腾夯，那么就可以很方便的將這二組數(shù)據(jù)進(jìn)行排序颊埃。如何讓這二組組內(nèi)數(shù)據(jù)有序了？可以將A蝶俱，B組各自再分成二組班利。依次類推，當(dāng)分出來的小組只有一個(gè)數(shù)據(jù)時(shí)榨呆，可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序罗标，然后再合并相鄰的二個(gè)小組就可以了。這樣通過先遞歸的分解數(shù)列积蜻，再合并數(shù)列就完成了歸并排序闯割。下面是歸并排序代碼：
package com.xtfggef.algo.sort;
public class MergeSort {
private static void mergeSort(int[] data, int start, int end) {
if (end > start) {
int pos = (start + end) / 2;
mergeSort(data, start, pos);
mergeSort(data, pos + 1, end);
merge(data, start, pos, end);
}
}
private static void merge(int[] data, int start, int pos, int end) {
int len1 = pos - start + 1;
int len2 = end - pos;
int A[] = new int[len1 + 1];
int B[] = new int[len2 + 1];
for (int i = 0; i < len1; i++) {
A[i] = data[i + start - 1];
}
A[len1] = Integer.MAX_VALUE;
for (int i = 0; i < len2; i++) {
B[i] = data[i + pos];
}
B[len2] = Integer.MAX_VALUE;
int m = 0, n = 0;
for (int i = start - 1; i < end; i++) {
if (A[m] > B[n]) {
data[i] = B[n];
n++;
} else {
data[i] = A[m];
m++;
}
}
}
private static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
public static void main(String args[]) {
int data[] = { 8, 16, 99, 732, 10, 1, 29, 66 };
print(data);
System.out.println();
mergeSort(data, 1, data.length);
print(data);
}
}
七、希爾排序（不穩(wěn)定竿拆、O（nlogn））
d1 = n/2宙拉，d2 = d1/2 ...
舉例一下：{9,8,7,6,5,4,3,2,1,0} 10個(gè)數(shù)，現(xiàn)分為5組(9,4),(8,3),(7,2),(6,1),(5,0)丙笋，然后分別對(duì)每組進(jìn)行直接插入排序得到：
(4,9),(3,8),(2,7),(1,6),(0,5)谢澈，再將這5組分為2組（4,3,2,1,0）,（9,8,7,6,5）分別對(duì)這兩組進(jìn)行直插排序，得：(0,1,2,3,4),(5,6,7,8,9)最終有序不见。
package com.xtfggef.algo.sort;
public class ShellSort {
static void shellsort(int[] a, int n) {
int i, j, temp;
int gap = 0;
while (gap <= n) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (i = gap; i < n; i++) {
j = i - gap;
temp = a[i];
while ((j >= 0) && (a[j] > temp)) {
a[j + gap] = a[j];
j = j - gap;
}
a[j + gap] = temp;
}
gap = (gap - 1) / 3;
}
}
static void print(int data[]) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
public static void main(String[] args) {
int data[] = { 2, 68, 7, 19, 1, 28, 66, 200 };
print(data);
System.out.println();
shellsort(data, data.length);
print(data);
}
}
八澳化、多路快排
JDK1.8中Arrays.sort()采用的排序算法，具有較快的時(shí)間復(fù)雜度和穩(wěn)定性稳吮，基本思路為：
1. 選取兩個(gè)中軸P1, P2缎谷。
2. 假設(shè)P1<P2，否則交換。
3. 過程中原數(shù)組會(huì)分為四個(gè)部分：小于中軸1列林，大于中軸2瑞你，介于兩個(gè)中軸之間，未排序部分（剛開始除了兩個(gè)中軸希痴，其它元素都屬于這部分）者甲。
4. 開始后，從未排序部分選取一個(gè)數(shù)砌创，和兩個(gè)中軸作比較虏缸，然后放到合適的位置，一直到未排序部分無數(shù)據(jù)嫩实，結(jié)束一趟排序刽辙。
5. 遞歸地處理子數(shù)組，穩(wěn)定排序甲献，時(shí)間復(fù)雜度穩(wěn)定為O(nlogn)宰缤。
詳情可以參見我的另一篇博文《Java之美[從菜鳥到高手演練]之Arrays類及其方法分析》
九、其他排序
計(jì)數(shù)排序
當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)晃洒，它的運(yùn)行時(shí)間是 O(n + k)慨灭。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法球及。
由于用來計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1）氧骤，這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存桶略。例如：計(jì)數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法语淘，但是它不適合按字母順序排序人名。但是际歼，計(jì)數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。
算法的步驟如下：
找出待排序的數(shù)組中最大和最小的元素
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)姑蓝，存入數(shù)組C的第i項(xiàng)
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始鹅心，每一項(xiàng)和前一項(xiàng)相加）
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
貼上代碼：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//對(duì)于排序的關(guān)鍵字范圍纺荧，一定是0-99
#define NUM_RANGE (100)
void print_arr(int *arr, int n)
{
int i;
for(i=0; i<n; i++){
if(!i){
printf("%d", arr[i]);
}else{
printf(" %d", arr[i]);
}
}
printf("\n");
}
/*
算法的步驟如下：
1.找出待排序的數(shù)組中最大和最小的元素
2.統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)旭愧，存入數(shù)組C的第i項(xiàng)
3.對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
4.反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)宙暇，每放一個(gè)元素就將C(i)減去1
*/
void counting_sort(int *ini_arr, int *sorted_arr, int n)
{
int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE);
int i, j, k;
//統(tǒng)計(jì)數(shù)組中输枯，每個(gè)元素出現(xiàn)的次數(shù)
for(k=0; k<NUM_RANGE; k++){
count_arr[k] = 0;
}
for(i=0; i<n; i++){
count_arr[ini_arr[i]]++;
}
for(k=1; k<NUM_RANGE; k++){
count_arr[k] += count_arr[k-1];
}
for(j=n-1 ; j>=0; j--){
int elem = ini_arr[j];
int index = count_arr[elem]-1;
sorted_arr[index] = elem;
count_arr[elem]--;
}
free(count_arr);
}
int main(int argc, char* argv[])
{
int n;
if(argc < 2){
n = 10;
}else{
n = atoi(argv[1]);
}
int i;
int *arr = (int *)malloc(sizeof(int) * n);
int *sorted_arr = (int *)malloc(sizeof(int) *n);
srand(time(0));
for(i=0; i<n; i++){
arr[i] = rand() % NUM_RANGE;
}
printf("ini_array: ");
print_arr(arr, n);
counting_sort(arr, sorted_arr, n);
printf("sorted_array: ");
print_arr(sorted_arr, n);
free(arr);
free(sorted_arr);
return 0;
}
桶排序
桶排序的基本思想
假設(shè)有一組長(zhǎng)度為N的待排關(guān)鍵字序列K[1....n]。首先將這個(gè)序列劃分成M個(gè)的子區(qū)間(桶) 占贫。然后基于某種映射函數(shù) 桃熄，將待排序列的關(guān)鍵字k映射到第i個(gè)桶中(即桶數(shù)組B的下標(biāo) i) ，那么該關(guān)鍵字k就作為B[i]中的元素(每個(gè)桶B[i]都是一組大小為N/M的序列)型奥。接著對(duì)每個(gè)桶B[i]中的所有元素進(jìn)行比較排序(可以使用快排)瞳收。然后依次枚舉輸出B[0]....B[M]中的全部?jī)?nèi)容即是一個(gè)有序序列碉京。假如待排序列K= {49、 38 螟深、 35谐宙、 97 、 76界弧、 73 凡蜻、 27、 49 }垢箕。這些數(shù)據(jù)全部在1—100之間划栓。因此我們定制10個(gè)桶，然后確定映射函數(shù)f(k)=k/10舰讹。則第一個(gè)關(guān)鍵字49將定位到第4個(gè)桶中(49/10=4)茅姜。依次將所有關(guān)鍵字全部堆入桶中，并在每個(gè)非空的桶中進(jìn)行快速排序月匣。
桶排序代價(jià)分析
桶排序利用函數(shù)的映射關(guān)系钻洒，減少了幾乎所有的比較工作。實(shí)際上锄开，桶排序的f(k)值的計(jì)算素标，其作用就相當(dāng)于快排中劃分，已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)萍悴。然后只需要對(duì)桶中的少量數(shù)據(jù)做先進(jìn)的比較排序即可头遭。
對(duì)N個(gè)關(guān)鍵字進(jìn)行桶排序的時(shí)間復(fù)雜度分為兩個(gè)部分：
(1) 循環(huán)計(jì)算每個(gè)關(guān)鍵字的桶映射函數(shù)，這個(gè)時(shí)間復(fù)雜度是O(N)癣诱。
(2) 利用先進(jìn)的比較排序算法對(duì)每個(gè)桶內(nèi)的所有數(shù)據(jù)進(jìn)行排序计维，其時(shí)間復(fù)雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個(gè)桶的數(shù)據(jù)量撕予。
很顯然鲫惶，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因?yàn)榛诒容^排序的最好平均時(shí)間復(fù)雜度只能達(dá)到O(N*logN)了)实抡。因此欠母，我們需要盡量做到下面兩點(diǎn)：
(1) 映射函數(shù)f(k)能夠?qū)個(gè)數(shù)據(jù)平均的分配到M個(gè)桶中，這樣每個(gè)桶就有[N/M]個(gè)數(shù)據(jù)量吆寨。
(2) 盡量的增大桶的數(shù)量赏淌。極限情況下每個(gè)桶只能得到一個(gè)數(shù)據(jù)，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作啄清。 當(dāng)然六水，做到這一點(diǎn)很不容易，數(shù)據(jù)量巨大的情況下，f(k)函數(shù)會(huì)使得桶集合的數(shù)量巨大缩擂，空間浪費(fèi)嚴(yán)重鼠冕。這就是一個(gè)時(shí)間代價(jià)和空間代價(jià)的權(quán)衡問題了。
對(duì)于N個(gè)待排數(shù)據(jù)胯盯，M個(gè)桶懈费，平均每個(gè)桶[N/M]個(gè)數(shù)據(jù)的桶排序平均時(shí)間復(fù)雜度為：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
當(dāng)N=M時(shí)，即極限情況下每個(gè)桶只有一個(gè)數(shù)據(jù)時(shí)博脑。桶排序的最好效率能夠達(dá)到O(N)憎乙。
總結(jié)： 桶排序的平均時(shí)間復(fù)雜度為線性的O(N+C)，其中C=N*(logN-logM)叉趣。如果相對(duì)于同樣的N泞边，桶數(shù)量M越大，其效率越高疗杉，最好的時(shí)間復(fù)雜度達(dá)到O(N)阵谚。 當(dāng)然桶排序的空間復(fù)雜度 為O(N+M)，如果輸入數(shù)據(jù)非常龐大烟具，而桶的數(shù)量也非常多梢什，則空間代價(jià)無疑是昂貴的。此外朝聋，桶排序是穩(wěn)定的嗡午。
我個(gè)人還有一個(gè)感受：在查找算法中，基于比較的查找算法最好的時(shí)間復(fù)雜度也是O(logN)冀痕。比如折半查找荔睹、平衡二叉樹、紅黑樹等言蛇。但是Hash表卻有O(C)線性級(jí)別的查找效率(不沖突情況下查找效率達(dá)到O(1))僻他。大家好好體會(huì)一下：Hash表的思想和桶排序是不是有一曲同工之妙呢?
基數(shù)排序
上面的問題是多關(guān)鍵字的排序，但單關(guān)鍵字也仍然可以使用這種方式腊尚。
比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每個(gè)字符看成一個(gè)關(guān)鍵字中姜。另外還有整數(shù) 425、321跟伏、235、432也可以每個(gè)位上的數(shù)字為一個(gè)關(guān)鍵字翩瓜。
基數(shù)排序的思想就是將待排數(shù)據(jù)中的每組關(guān)鍵字依次進(jìn)行桶分配受扳。比如下面的待排序列：
278、109兔跌、063勘高、930、589、184华望、505蕊蝗、269、008赖舟、083
我們將每個(gè)數(shù)值的個(gè)位蓬戚，十位，百位分成三個(gè)關(guān)鍵字： 278 -> k1(個(gè)位)=8 宾抓，k2(十位)=7 子漩，k3=(百位)=2。
然后從最低位個(gè)位開始(從最次關(guān)鍵字開始)石洗，對(duì)所有數(shù)據(jù)的k1關(guān)鍵字進(jìn)行桶分配(因?yàn)榇逼茫總€(gè)數(shù)字都是 0-9的，因此桶大小為10)讲衫，再依次輸出桶中的數(shù)據(jù)得到下面的序列缕棵。
930、063涉兽、083招驴、184、505花椭、278忽匈、008、109矿辽、589丹允、269
再對(duì)上面的序列接著進(jìn)行針對(duì)k2的桶分配，輸出序列為：
505袋倔、008雕蔽、109、930宾娜、063批狐、269、278前塔、083嚣艇、184、589
最后針對(duì)k3的桶分配华弓，輸出序列為：
008食零、063、083寂屏、109贰谣、184娜搂、269、278吱抚、505百宇、589、930
性能分析
很明顯秘豹，基數(shù)排序的性能比桶排序要略差携御。每一次關(guān)鍵字的桶分配都需要O(N)的時(shí)間復(fù)雜度，而且分配之后得到新的關(guān)鍵字序列又需要O(N)的時(shí)間復(fù)雜度憋肖。假如待排數(shù)據(jù)可以分為d個(gè)關(guān)鍵字因痛，則基數(shù)排序的時(shí)間復(fù)雜度將是O(d*2N) ，當(dāng)然d要遠(yuǎn)遠(yuǎn)小于N岸更，因此基本上還是線性級(jí)別的鸵膏。基數(shù)排序的空間復(fù)雜度為O(N+M)怎炊，其中M為桶的數(shù)量谭企。一般來說N>>M，因此額外空間需要大概N個(gè)左右评肆。
但是债查，對(duì)比桶排序，基數(shù)排序每次需要的桶的數(shù)量并不多瓜挽。而且基數(shù)排序幾乎不需要任何“比較”操作盹廷，而桶排序在桶相對(duì)較少的情況下，桶內(nèi)多個(gè)數(shù)據(jù)必須進(jìn)行基于比較操作的排序久橙。因此俄占，在實(shí)際應(yīng)用中，基數(shù)排序的應(yīng)用范圍更加廣泛淆衷。
