@[toc]
0. 前言
排序算法中涉及到了兩個(gè)概念：
原地排序：根據(jù)算法對(duì)內(nèi)存的消耗情況髓涯，可以將算法分為原地排序和非原地排序漫玄，原地排序特指空間復(fù)雜度為 O(1) 的排序。
排序算法的穩(wěn)定性：例如排序一個(gè)數(shù)組 [1, 5, 3, 7, 4, 9, 5]，數(shù)組中有兩個(gè) 5彻磁，排序之后是 [1, 3, 4, 5, 5, 7, 9]，如果排序之后的兩個(gè) 5 的前后順序沒有發(fā)生變化狸捅，那么稱這個(gè)排序是穩(wěn)定的衷蜓，反之則是不穩(wěn)定的。
1. 冒泡排序
冒泡排序是很經(jīng)典的排序算法了尘喝，相鄰的兩個(gè)數(shù)據(jù)依次進(jìn)行比較并交換位置磁浇。遍歷一遍數(shù)組后，則有一個(gè)數(shù)據(jù)排序完成朽褪，然后再遍歷 n 次置吓，排序完成无虚。示意圖如下：
代碼實(shí)現(xiàn)：
public class BubbleSort {
private static void bubbleSort(int[] data){
int length = data.length;
for (int i = length - 1; i > 0; i --) {
//判斷是否有數(shù)據(jù)交換，如果沒有則提前退出
boolean flag = false;
for (int j = 0; j < i; j ++) {
if (data[j] > data[j + 1]){
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
flag = true;
}
}
if (!flag){
break;
}
}
}
}
2. 選擇排序
將要排序的數(shù)據(jù)分為了已排序區(qū)間和未排序區(qū)間衍锚，每次從未排序區(qū)間找到最小值友题，然后將其放到已排序區(qū)間的末尾，循環(huán)遍歷未排序區(qū)間則排序完成戴质。
示意圖如下：
代碼實(shí)現(xiàn)：
public class SelectionSort {
public static void selectionSort(int[] data){
int length = data.length;
for (int i = 0; i < length - 1; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (data[min] > data[j]){
min = j;
}
}
int temp = data[min];
data[min] = data[i];
data[i] = temp;
}
}
}
3. 插入排序
和選擇排序類似度宦，插入排序也將數(shù)據(jù)分為了已排序區(qū)間和未排序區(qū)間，遍歷未排序區(qū)間告匠，每次取一個(gè)數(shù)據(jù)斗埂，將其插入到已排序區(qū)間的合適位置，讓已排序區(qū)間一直保持有序凫海，直到未排序區(qū)間遍歷完排序則完成呛凶。
示意圖如下：
代碼實(shí)現(xiàn)：
public class InsertionSort {
public static void insertionSort(int[] data){
int length = data.length;
for (int i = 0; i < length - 1; i++) {
int val = data[i + 1];
int j = i + 1;
while (j > 0 && data[j - 1] > val){
data[j] = data[j - 1];
j --;
}
data[j] = val;
}
}
}
插入排序?yàn)槭裁幢让芭菖判蚋Ｓ茫?/p>
這兩種排序的時(shí)間復(fù)雜度都是一樣的，最好情況是 O(n)行贪，最壞情況是 O(n2)漾稀，但是在實(shí)際的生產(chǎn)中，插入排序使用更多建瘫，原因在于兩者數(shù)據(jù)交換的次數(shù)不同崭捍。冒泡排序需要進(jìn)行三次交換，插入排序只要一次：
//冒泡排序數(shù)據(jù)交換
if (data[j] > data[j + 1]){
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
flag = true;
}
//插入排序數(shù)據(jù)交換
while (j > 0 && data[j - 1] > val){
data[j] = data[j - 1];
j --;
}
在數(shù)據(jù)量較大的時(shí)候啰脚，兩者性能差距就體現(xiàn)出來了殷蛇。
4. 希爾排序
希爾排序其實(shí)是插入排序的一種優(yōu)化，其思路是將排序的數(shù)組按照一定的增量將數(shù)據(jù)分組橄浓，每個(gè)分組用插入排序進(jìn)行排序粒梦，然后增量逐步減小，當(dāng)增量減小為1的時(shí)候荸实，算法便終止匀们，所以希爾排序又叫做“縮小增量排序”。
示意圖如下：
圖中的示例准给，每次依次將數(shù)組分為若干組泄朴，每組分別進(jìn)行插入排序。代碼實(shí)現(xiàn)如下：
public class ShellSort {
public static void shellSort(int[] data) {
int length = data.length;
int step = length / 2;
while (step >= 1){
for (int i = step; i < length; i++) {
int val = data[i];
int j = i - step;
for (; j >= 0; j -= step){
if (data[j] > val){
data[j + step] = data[j];
}
else {
break;
}
}
data[j + step] = val;
}
step = step / 2;
}
}
}
5. 歸并排序
歸并排序使用到了分治思想露氮，分治思想即將大的問題分解成小的問題祖灰，小的問題解決了，大的問題也就解決了畔规。蘊(yùn)含分治思想的問題局扶，一般可以使用遞歸技巧來實(shí)現(xiàn)。
歸并排序的思路是：首先將數(shù)組分解，局部進(jìn)行排序详民，然后將排序的結(jié)果進(jìn)行合并，這樣整個(gè)數(shù)組就有序了陌兑，你可以結(jié)合下圖理解：
代碼實(shí)現(xiàn)：
public class MergeSort {
public static void mergeSort(int[] data){
mergeInternally(data, 0, data.length - 1);
}
private static void mergeInternally(int[] data, int p, int r){
if (p >= r){
return;
}
int q = (p + r) / 2;
//分治遞歸
mergeInternally(data, p, q);
mergeInternally(data, q + 1, r);
//結(jié)果合并
merge(data, p, q, r);
}
private static void merge(int[] data, int p, int q, int r){
int[] temp = new int[r - p + 1];
int k = 0;
int i = p;
int j = q + 1;
//比較并合并
while (i <= q && j <= r){
if (data[i] < data[j]){
temp[k ++] = data[i ++];
}
else {
temp[k ++] = data[j ++];
}
}
//合并可能出現(xiàn)的剩余元素
int start = i;
int end = q;
if (j <= r){
start = j;
end = r;
}
while (start <= end){
temp[k ++] = data[start ++];
}
//拷貝回原數(shù)組
if (r - p + 1 >= 0) {
System.arraycopy(temp, 0, data, p, r - p + 1);
}
}
}
6. 快速排序
快速排序也用到了分治的思想沈跨，只不過它和歸并排序的思路剛好是相反的，快速排序使用數(shù)組中一個(gè)數(shù)據(jù)作為分區(qū)點(diǎn)（一般可以選取數(shù)組第一個(gè)或最后一個(gè)元素）兔综，比分區(qū)點(diǎn)小的饿凛，放在左側(cè)，比分區(qū)點(diǎn)大的软驰，放在右側(cè)涧窒。然后左右兩側(cè)的數(shù)據(jù)再次選擇分區(qū)點(diǎn)，循環(huán)進(jìn)行這個(gè)操作锭亏，直到排序完成纠吴。
示意圖如下（圖中是以第一個(gè)元素作為分區(qū)點(diǎn)）：
代碼實(shí)現(xiàn)：
public class QuickSort {
public static void quickSort(int[] data){
quickSortInternally(data, 0, data.length - 1);
}
private static void quickSortInternally(int[] data, int p, int r){
if (p >= r){
return;
}
int q = partition(data, p, r);
quickSortInternally(data, p, q - 1);
quickSortInternally(data, q + 1, r);
}
/**
* 獲取分區(qū)點(diǎn)函數(shù)
*/
private static int partition(int [] data, int p, int q){
int pivot = data[q];
int i = 0;
int j = 0;
while (j < q){
if (data[j] <= pivot){
swap(data, i, j);
i ++;
}
j ++;
}
swap(data, i, q);
return i;
}
/**
* 交換數(shù)組兩個(gè)元素
*/
private static void swap(int[] data, int i, int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
7. 堆排序
基于堆的排序比較常用，時(shí)間復(fù)雜度為 O(nlogn)慧瘤，并且是原地排序戴已，主要的步驟分為建堆和排序。
建堆
思路是從堆中第一個(gè)非葉子節(jié)點(diǎn)锅减，依次從上往下進(jìn)行堆化糖儡，如下圖：
排序
建堆完成之后，假設(shè)堆中元素個(gè)數(shù)為 n怔匣，堆頂元素即是最大的元素握联，這時(shí)候直接將堆頂元素和堆中最后一個(gè)元素進(jìn)行交換，然后將剩余的 n - 1 個(gè)元素構(gòu)建成新的堆每瞒，依次類推金闽，直到堆中元素減少至 1，則排序完成剿骨。示意圖如下：
代碼實(shí)現(xiàn)：
public class HeapSort {
/**
* 排序
*/
public void heapSort(int[] data){
int length = data.length;
if (length <= 1){
return;
}
buildHeap(data);
while (length > 0){
swap(data, 0, -- length);
heapify(data, length, 0);
}
}
/**
* 建堆
*/
private void buildHeap(int[] data){
int length = data.length;
for (int i = (length - 2) / 2; i >= 0; i --) {
heapify(data, length, i);
}
}
/**
* 堆化函數(shù)
*/
private void heapify(int[] data, int size, int i){
while (true){
int max = i;
if ((2 * i + 1) < size && data[i] < data[2 * i + 1]) {
max = 2 * i + 1;
}
if ((2 * i + 2) < size && data[max] < data[2 * i + 2]) {
max = 2 * i + 2;
}
if (max == i){
break;
}
swap(data, i, max);
i = max;
}
}
/**
* 交換數(shù)組中兩個(gè)元素
*/
private void swap(int[] data, int i, int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
8. 桶排序
桶排序并不是基于數(shù)據(jù)比較的呐矾，因此比較的高效，時(shí)間復(fù)雜度接近 O(n)懦砂，但是相應(yīng)地蜒犯，應(yīng)用的條件十分苛刻。其思路非常的簡(jiǎn)單：將要排序的數(shù)據(jù)分到各個(gè)有序的桶內(nèi)荞膘，數(shù)據(jù)在桶內(nèi)進(jìn)行排序罚随，然后按序取出，整個(gè)數(shù)據(jù)就是有序的了羽资。
最好情況下淘菩，數(shù)據(jù)被均勻的分到各個(gè)桶中，最壞情況是數(shù)據(jù)全都被分到一個(gè)桶中。
下面是一個(gè)桶排序的示例：
public class BucketSort {
/**
* 測(cè)試場(chǎng)景：數(shù)組中有10000個(gè)數(shù)據(jù)潮改，范圍在(0-100000)
* 使用100個(gè)桶狭郑，每個(gè)桶存放的數(shù)據(jù)范圍為：0-999, 1000-1999, 2000-2999，依次類推
*/
public static void bucketSort(int[] data){
//新建100個(gè)桶
int bucketSize = 100;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketSize);
for (int i = 0; i < bucketSize; i++) {
buckets.add(new ArrayList<>());
}
//遍歷數(shù)據(jù)汇在，將數(shù)據(jù)放到桶中
for (int i : data) {
buckets.get(i / 1000).add(i);
}
//在桶內(nèi)部進(jìn)行排序
int k = 0;
for (int i = 0; i < bucketSize; i++) {
ArrayList<Integer> list = buckets.get(i);
Integer[] num = list.toArray(new Integer[1]);
Arrays.sort(num);
//拷貝到data中
for (int n : num) {
data[k++] = n;
}
}
}
//測(cè)試
public static void main(String[] args) {
Random random = new Random();
int[] data = new int[10000];
for (int i = 0; i < data.length; i++) {
data[i] = random.nextInt(100000);
}
BucketSort.bucketSort(data);
System.out.println(Arrays.toString(data));
}
}
9. 計(jì)數(shù)排序
計(jì)數(shù)排序其實(shí)是一種特殊的桶排序翰萨，適用于數(shù)據(jù)的區(qū)間不是很大的情況。
例如給 10 萬人按照年齡進(jìn)行排序糕殉，我們知道年齡的區(qū)間并不是很大亩鬼，最小的 0 歲，最大的可以假設(shè)為 120 歲阿蝶，那么我們可以新建 121 個(gè)桶雳锋，掃描一遍數(shù)據(jù)，將年齡相同的放到一個(gè)桶中羡洁，然后按序從桶中將數(shù)據(jù)取出玷过，這樣數(shù)據(jù)就有序了。
計(jì)數(shù)排序的基本思路如下：
代碼實(shí)現(xiàn)：
public class CountingSort {
private static void countingSort(int[] data){
int length = data.length;
//找到數(shù)組的最大值
int max = data[0];
for (int i : data){
if (max < i){
max = i;
}
}
//新建一個(gè)計(jì)數(shù)數(shù)組筑煮，大小為max+1
//count數(shù)組的下標(biāo)對(duì)應(yīng)data的值冶匹，存儲(chǔ)的值為對(duì)應(yīng)data值的個(gè)數(shù)
int[] count = new int[max + 1];
for (int i : data){
count[i] ++;
}
//根據(jù)count數(shù)組取出數(shù)據(jù)
int k = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] != 0){
data[k ++] = i;
count[i] --;
}
}
}
}
10. 基數(shù)排序
基數(shù)排序適用于位數(shù)較多的數(shù)字或者字符串，思路是將排序的數(shù)據(jù)按位拆分咆瘟，每一位單獨(dú)按照穩(wěn)定的排序算法進(jìn)行比較嚼隘，如下圖：
圖中的示例，以每個(gè)數(shù)字為下標(biāo)袒餐，建了 10 個(gè) “桶”飞蛹，每個(gè)桶是一個(gè)隊(duì)列（也可以是數(shù)組），然后將要排序的數(shù)據(jù)按位加入到隊(duì)列中灸眼，然后出隊(duì)卧檐，比較完每一位，則排序完成焰宣。
代碼實(shí)現(xiàn)：
public class RadixSort {
private static void radixSort(int[] data) {
int maxDigit = maxDigit(data);
//新建并初始化10個(gè)桶
Queue<Integer>[] queues = new LinkedList[10];
for (int i = 0; i < queues.length; i++) {
queues[i] = new LinkedList<>();
}
for (int i = 0, mod = 1; i < maxDigit; i ++, mod *= 10) {
for (int n : data){
int m = (n / mod) % 10;
queues[m].add(n);
}
int count = 0;
for (Queue<Integer> queue : queues) {
while (queue.size() > 0) {
data[count++] = queue.poll();
}
}
}
}
/**
* 獲取數(shù)組最大位數(shù)
*/
private static int maxDigit(int[] data){
int maxDigit = data[0];
for (int i : data){
if (maxDigit < i){
maxDigit = i;
}
}
return String.valueOf(maxDigit).length();
}
}
在我的 Github 上面有更加詳細(xì)的數(shù)據(jù)結(jié)構(gòu)與算法代碼
