題記：
常見的內(nèi)部排序算法有：
插入排序更耻、希爾排序测垛、選擇排序、冒泡排序秧均、歸并排序食侮、快速排序、堆排序目胡、基數(shù)排序等锯七。
首先理解兩個排序涉及的概念：
原地排序（Sorted in place）。原地排序算法誉己，就是特指空間復(fù)雜度是 O(1) 的排序算法眉尸。
穩(wěn)定性。這個概念是說巫延，如果待排序的序列中存在值相等的元素效五，經(jīng)過排序之后，相等元素之間原有的先后順序不變炉峰。
接下來討論畏妖、理解和比較這些常用的排序算法都離不開這兩點。
一疼阔、冒泡排序（Bubble Sort）
冒泡排序（BubbleSort）是一種最簡單的排序算法戒劫。它的基本思想是迭代地對輸入序列的第一個元素到最后一個元素進行倆倆比較，當(dāng)滿足條件時交換這倆個元素的位置婆廊，該過程持續(xù)到不需要執(zhí)行上述過程的條件時迅细。
<!--每次冒出一個最大的-->
public void bubbleSort(int[] a) {
if (a.length <= 1) return;
for (int i = 0; i < a.length-1 ; ++i) {
// 提前退出冒泡循環(huán)的標(biāo)志位
boolean flag = false;
for (int j = 0; j < a.length - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交換
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有數(shù)據(jù)交換
}
}
if (!flag) break; // 沒有數(shù)據(jù)交換，提前退出
}
}
分析：
第一淘邻， 冒泡排序是原地排序算法嗎茵典？
冒泡的過程只涉及相鄰數(shù)據(jù)的交換操作，只需要常量級的臨時空間宾舅，所以它的空間復(fù)雜度為 O(1)统阿，是一個原地排序算法彩倚。
第二， 冒泡排序是穩(wěn)定的排序算法嗎扶平？
在冒泡排序中帆离，只有交換才可以改變兩個元素的前后順序。為了保證冒泡排序算法的穩(wěn)定性结澄，當(dāng)有相鄰的兩個元素大小相等的時候哥谷，我們不做交換，相同大小的數(shù)據(jù)在排序前后不會改變順序麻献，所以冒泡排序是穩(wěn)定的排序算法们妥。
第三， 冒泡排序的時間復(fù)雜度是多少赎瑰？
最好情況下王悍，要排序的數(shù)據(jù)已經(jīng)是有序的了，我們只需要進行一次冒泡操作餐曼，就可以結(jié)束了，所以最好情況時間復(fù)雜度是 O(n)源譬。而最壞的情況是集惋，要排序的數(shù)據(jù)剛好是倒序排列的踩娘，我們需要進行 n 次冒泡操作刮刑，所以最壞情況時間復(fù)雜度為 O(n2 )。
二雷绢、插入排序（InsertionSort）
插入排序（InsertionSort）是一種簡單且有效的比較排序算法理卑，我們將數(shù)組中的數(shù)據(jù)分為兩個區(qū)間翘紊，已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素藐唠，就是數(shù)組的第一個元素帆疟。重復(fù)該過程宇立，知道所有元素都被選擇一次。
public void insertionSort(int[] a) {
if (a.length <= 1) return;
for (int i = 1; i < a.length; ++i) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; // 數(shù)據(jù)移動
} else {
break;
}
}
a[j+1] = value; // 插入數(shù)據(jù)
}
}
分析：
第一柳琢， 插入排序是原地排序算法嗎？
從實現(xiàn)過程可以很明顯地看出痘绎，插入排序算法的運行并不需要額外的存儲空間，所以空間復(fù)雜度是 O(1)，也就是說尔苦，這是一個原地排序算法允坚。
第二， 插入排序是穩(wěn)定的排序算法嗎稠项？
在插入排序中，對于值相同的元素活逆，我們可以選擇將后面出現(xiàn)的元素拗胜，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變锈遥，所以插入排序是穩(wěn)定的排序算法勘畔。
第三， 插入排序的時間復(fù)雜度是多少炫七？
如果要排序的數(shù)據(jù)已經(jīng)是有序的，我們并不需要搬移任何數(shù)據(jù)懦尝。如果我們從尾到頭在有序數(shù)據(jù)組里面查找插入位置壤圃，每次只需要比較一個數(shù)據(jù)就能確定插入的位置。所以這種情況下踊挠，最好是時間復(fù)雜度為 O(n)。注意效床，這里是從尾到頭遍歷已經(jīng)有序的數(shù)據(jù)剩檀。
三、選擇排序（Selection Sort）
選擇排序算法的實現(xiàn)思路有點類似插入排序沪猴，也分已排序區(qū)間和未排序區(qū)間。首先在未排序序列中找到最泻肌（大）元素担租，存放到排序序列的起始位置。再從剩余未排序元素中繼續(xù)尋找最辛氩巍（大）元素菠镇，然后放到已排序序列的末尾。重復(fù)第二步蚌本，直到所有元素均排序完畢隘梨。
private void sorter(int[] arr) {
// 總共要經(jīng)過 N-1 輪比較
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每輪需要比較的次數(shù) N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 記錄目前能找到的最小值元素的下標(biāo)
min = j;
}
}
// 將找到的最小值和i位置所在的值進行交換
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}
選擇排序空間復(fù)雜度為 O(1)，是一種原地排序算法嵌莉，適用于小文件捻脖。選擇排序的最好情況時間復(fù)雜度、最壞情況和平均情況時間復(fù)雜度都為 O(n2)沿癞。選擇排序是一種不穩(wěn)定的排序算法矛渴。
四、歸并排序（Merge sort）
歸并排序（Merge sort）使用的就是分治思想蚕涤。用遞歸實現(xiàn)。
歸并排序的實現(xiàn)由兩種方法：
- 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫茴丰，所以就有了第 2 種方法）蛮位；
- 自下而上的迭代；
如果要排序一個數(shù)組失仁，我們先把數(shù)組從中間分成前后兩部分们何，然后對前后兩部分分別排序冤竹，再將排好序的兩部分合并在一起，這樣整個數(shù)組就都有序了鹦蠕。
// 歸并排序算法, A是數(shù)組钟病，n表示數(shù)組大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 遞歸調(diào)用函數(shù)
merge_sort_c(A, p, r) {
// 遞歸終止條件
if p >= r then return
// 取p到r之間的中間位置q
q = (p+r) / 2
// 分治遞歸
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 將A[p...q]和A[q+1...r]合并為A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}
如果我們定義求解問題 a 的時間是 T(a)，求解問題 b票唆、c 的時間分別是 T(b) 和 T( c)屹徘，那我們就可以得到這樣的遞推關(guān)系式：T(a) = T(b) + T(c) + K其中 K 等于將兩個子問題 b、c 的結(jié)果合并成問題 a 的結(jié)果所消耗的時間簿煌。
五鉴吹、快速排序
快速排序并不是一個穩(wěn)定的排序算法。
六授滓、堆排序
堆排序包括建堆和排序兩個操作。
建堆過程的時間復(fù)雜度是 O(n)在孝，排序過程的時間復(fù)雜度是 O(nlogn)淮摔，所以，堆排序整體的時間復(fù)雜度是 O(nlogn)仔燕。
1魔招、建堆
借助在堆中插入一個元素的思路。盡管數(shù)組中包含 n 個數(shù)據(jù)办斑，假設(shè)起初堆中只包含一個數(shù)據(jù)乡翅，然后依次將n-1個數(shù)據(jù)依次插入到堆中，這樣蠕蚜，建堆結(jié)束之后，數(shù)組中的數(shù)據(jù)已經(jīng)是按照大頂堆的特性來組織的腺毫。時間復(fù)雜度是 O(n)尺铣。
2、排序
對于完全二叉樹來說澈灼，下標(biāo)從 n/2 到 n-1 的節(jié)點都是葉子節(jié)點店溢，如圖，3214為葉子節(jié)點荣回，存儲下標(biāo)從8/2到7戈咳。因為葉子節(jié)點不需要堆化壕吹，每個節(jié)點堆化的時間復(fù)雜度是 O(logn)删铃，那 n/2個節(jié)點堆化的總時間復(fù)雜度就是 O(nlogn) 。
public int[] sort(int[] arr ) throws Exception {
int len = arr.length;
buildMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len);
}
}
private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
七、線性排序
三種時間復(fù)雜度是 O(n) 的排序算法：桶排序诫隅、計數(shù)排序、基數(shù)排序蛔屹。
因為這些排序算法的時間復(fù)雜度是線性的豁生，所以我們把這類排序算法叫作線性排序（Linear sort）。之所以能做到線性的時間復(fù)雜度，主要原因是摇肌，這三個算法是非基于比較的排序算法仪际，都不涉及元素之間的比較操作。
