轉(zhuǎn)載請注明出處：
http://egoistk21.xyz/2016/09/10/Java排序算法專題/
今天晚上做了一下LeetCode上的Median of Two Sorted Arrays這道題，沒想到一次性通過了。隨即想要歸納整理一下排序算法捕发，廢話少說扇苞，我們開始吧。
選擇排序
這是一種最簡單直觀的排序算法，它的工作原理如下：每一趟從待排序的數(shù)列中選出最小的（最大的）一個元素锚赤，順序放到已經(jīng)排好序的數(shù)列的最后题翻，直到所有待排元素全部排好。選擇排序是穩(wěn)定的排序算法平夜，最壞時間復(fù)雜度是O(n^2) 蝶棋，最優(yōu)時間復(fù)雜度是O(n^2) ，平均時間復(fù)雜度是O(n^2)忽妒。
下面是對{1, 3, 5, 7, 9, 2, 4, 6, 8, 0}進行選擇排序的具體過程
|1 3 5 7 9 2 4 6 8 0 選擇第一小的數(shù)與0位交換
i j
1 3 5 7 9 2 4 6 8 0
i j
min
0| 3 5 7 9 2 4 6 8 1 選擇第二小的數(shù)與1位交換
i j
0 3 5 7 9 2 4 6 8 1
i j
min
0 1| 5 7 9 2 4 6 8 3 選擇第三小的數(shù)與2位交換
0 1 2| 7 9 5 4 6 8 3 選擇第四小的數(shù)與3位交換
0 1 2 3| 9 5 4 6 8 7 選擇第五小的數(shù)與4位交換
0 1 2 3 4| 5 9 6 8 7 選擇第六小的數(shù)與5位交換
0 1 2 3 4 5| 9 6 8 7 選擇第七小的數(shù)與6位交換
0 1 2 3 4 5 6| 9 8 7 選擇第八小的數(shù)與7位交換
0 1 2 3 4 5 6 7| 8 9 選擇第九小的數(shù)與8位交換
0 1 2 3 4 5 6 7 8| 9 待排只剩一個數(shù)玩裙，排序結(jié)束
選擇排序(從小到大)的Java實現(xiàn)如下：
public static void selectSort(int[] nums) {
int min, temp, length = nums.length;
for (int i = 0; i < length -1; i++) {
min = i;
for (int j = i + 1; j < length; j++) {
if (nums[min] > nums[j]) {
min = j;
}
}
temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
插入排序
這也是一種簡單直觀的排序算法，它的工作原理如下：構(gòu)建有序序列段直，即對于未排序數(shù)據(jù)吃溅，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入鸯檬。插入排序是穩(wěn)定的排序算法决侈，最壞時間復(fù)雜度是O(n^2) ，最優(yōu)時間復(fù)雜度是O(n)喧务，平均時間復(fù)雜度是O(n^2)赖歌。
下面是對{1, 3, 5, 7, 9, 2, 4, 6, 8, 0}進行插入排序的具體過程
1 3 5 7 9 2 4 6 8 0
1 3 5 7 9 9 4 6 8 0 temp=2
1 3 5 7 7 9 4 6 8 0
1 3 5 5 7 9 4 6 8 0
1 3 3 5 7 9 4 6 8 0
1 2 3 5 7 9 4 6 8 0
1 2 3 5 7 9 9 6 8 0 temp=4
1 2 3 5 7 7 9 6 8 0
1 2 3 5 5 7 9 6 8 0
1 2 3 4 5 7 9 6 8 0
1 2 3 4 5 7 9 9 8 0 temp=6
1 2 3 4 5 7 7 9 8 0
1 2 3 4 5 6 7 9 8 0
1 2 3 4 5 6 7 9 9 0 temp=8
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 9 temp=0
1 2 3 4 5 6 7 8 8 9
1 2 3 4 5 6 7 7 8 9
1 2 3 4 5 6 6 7 8 9
1 2 3 4 5 5 6 7 8 9
1 2 3 4 4 5 6 7 8 9
1 2 3 3 4 5 6 7 8 9
1 2 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
插入排序(從小到大)的Java實現(xiàn)如下：
public static void insertSort(int[] nums) {
int temp, length = nums.length;
for (int i = 1; i < length; i++) {
temp = nums[i];
int j = i;
for (; j >= 1&&temp < nums[j - 1]; j--) {
nums [j] = nums[j - 1];
}
nums[j] = temp;
}
}
希爾排序
希爾排序，也稱遞減增量排序算法功茴，是插入排序的一種高速而穩(wěn)定的改進版本庐冯。我把希爾排序叫做分組插入排序，它的工作原理如下：先把要排序的序列元素以序列長度的1/2為間隔(向下取整)兩兩分為一組坎穿，對每組分別進行插入排序肄扎，排完后再以序列長度的1/4為間隔(向下取整)分組，對每組分別進行插入排序，重復(fù)上述操作犯祠，直至間隔為一旭等，即最后一趟為普通的插入排序(此時序列已基本有序)。希爾排序是不穩(wěn)定的排序算法衡载，時間復(fù)雜度取決于分組間隔gap的取值搔耕，目前最佳版本的最壞時間復(fù)雜度是O(n(lgn)^2) 。一般情況下痰娱，最壞時間復(fù)雜度是O(n^2)弃榨，最優(yōu)時間復(fù)雜度是O(n)。
下面是對{1, 3, 5, 7, 9, 2, 4, 6, 8, 0}進行插入排序的具體過程
1 3 5 7 9 2 4 6 8 0 gap=5
1 3 5 7 9 2 4 6 8 9 temp=0
1 3 5 7 0 2 4 6 8 9 gap=2
1 3 5 7 5 2 4 6 8 9 temp=0
1 3 1 7 5 2 4 6 8 9
0 3 1 7 5 2 4 6 8 9
0 3 1 7 5 2 5 6 8 9 temp=4
0 3 1 7 4 2 5 6 8 9
0 3 1 7 4 7 5 6 8 9 temp=2
0 3 1 3 4 7 5 6 8 9
0 2 1 3 4 7 5 6 8 9
0 2 1 3 4 7 5 7 8 9 temp=6
0 2 1 3 4 6 5 7 8 9 gap=1
0 2 2 3 4 6 5 7 8 9 temp=1
0 1 2 3 4 6 5 7 8 9
0 1 2 3 4 6 6 7 8 9 temp=5
0 1 2 3 4 5 6 7 8 9
希爾排序(從小到大)的Java實現(xiàn)如下：
public static void shellSort(int[] nums) {
int temp, length = nums.length;
for (int gap = length/2; gap > 0; gap /= 2) {
for (int i = 0; i < gap ; i++) {
for (int j = i + gap; j < length; j += gap) {
temp = nums[j];
int k = j;
for (; k >= gap&&temp < nums[k - gap]; k -= gap) {
nums[k] = nums[k - gap];
}
nums[k] = temp;
}
}
}
}
冒泡排序
冒泡排序梨睁，是一種簡單的排序算法鲸睛。因其排序過程中較大(或小)元素會慢慢“浮到”頂部，就像魚吐泡泡而得名坡贺。它的工作原理如下：重復(fù)地遍歷要排序的序列官辈，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來遍坟，直到序列有序拳亿。冒泡排序是穩(wěn)定的排序算法，最壞時間復(fù)雜度是O(n^2) 愿伴，最優(yōu)時間復(fù)雜度是O(n)肺魁，平均時間復(fù)雜度是O(n^2)。
下面是對{1, 3, 5, 7, 9, 2, 4, 6, 8, 0}進行冒泡排序的具體過程
|1 3 5 7 9 2 4 6 8 0
|1 3 5 7 9 2 4 6 0 8
|1 3 5 7 9 2 4 0 6 8
|1 3 5 7 9 2 0 4 6 8
|1 3 5 7 9 0 2 4 6 8
|1 3 5 7 0 9 2 4 6 8
|1 3 5 0 7 9 2 4 6 8
|1 3 0 5 7 9 2 4 6 8
|1 0 3 5 7 9 2 4 6 8
0 1| 3 5 7 9 2 4 6 8
0 1| 3 5 7 2 9 4 6 8
0 1| 3 5 2 7 9 4 6 8
0 1| 3 2 5 7 9 4 6 8
0 1 2 3| 5 7 9 4 6 8
0 1 2 3| 5 7 4 9 6 8
0 1 2 3| 5 4 7 9 6 8
0 1 2 3 4 5| 7 9 6 8
0 1 2 3 4 5| 7 6 9 8
0 1 2 3 4 5 6 7| 9 8
0 1 2 3 4 5 6 7 8 9|
冒泡排序(從小到大)的Java實現(xiàn)如下：
public static void bubbleSort(int[] nums) {
int length = nums.length;
for (int i = 0; i < length; i++) {
for (int j = length - 1; j > i; j--) {
if (nums[j - 1] > nums[j]) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
}
快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法隔节。在平均狀況下鹅经，排序 n 個項目要Ο(nlogn)次比較。在最壞狀況下則需要Ο(n^2)次比較怎诫，但這種狀況并不常見瞬雹。事實上，快速排序通常明顯比其他Ο(nlogn) 算法更快刽虹，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來，且在大部分真實世界的數(shù)據(jù)呢诬，可以決定設(shè)計的選擇涌哲，減少所需時間的二次方項之可能性∩辛快速排序是不穩(wěn)定的排序算法阀圾，最壞時間復(fù)雜度是O(n^2)，最優(yōu)時間復(fù)雜度是O(nlogn)狗唉，平均時間復(fù)雜度是O(nlogn)初烘。
下面是對{1, 3, 5, 7, 9, 2, 4, 6, 8, 0}進行快速排序(遞歸版)的具體過程
第一遍循環(huán)
取pivot=1
1 3 5 7 9 2 4 6 8 0
i j
先從尾部j開始，找到比1小的數(shù)字往i的位置復(fù)制
0 3 5 7 9 2 4 6 8 0
i j
0比1小，被復(fù)制到i的位置肾筐，復(fù)制之后i++
0 3 5 7 9 2 4 6 8 3
i j
這時候要從頭部i開始哆料，找到比1大的數(shù)字往j的位置復(fù)制
3比1大，被復(fù)制到j(luò)的位置吗铐，復(fù)制之后j--
0 3 5 7 9 2 4 6 8 3
i
j
再次從j開始尋找比1小的數(shù)字东亦，但是沒找到，直到i和j相遇（i=j）
第一遍循環(huán)結(jié)束
0 1 5 7 9 2 4 6 8 3
把pivot復(fù)制到循環(huán)結(jié)束時i的位置
此時pivot把數(shù)組分成兩部分{0}和{5, 7, 9, 2, 4, 6, 8, 3}
第二次循環(huán)分兩部分進行
第一部分 第二部分
0 取pivot=5
只有一個數(shù)唬渗，不用排序 5 7 9 2 4 6 8 3
第一部分結(jié)束 i j
和第一遍循環(huán)一樣先從j開始...
3 7 9 2 4 6 8 3
i j
3 7 9 2 4 6 8 7
i j
3 4 9 2 4 6 8 7
i j
3 4 9 2 9 6 8 7
i
j
3 4 2 2 9 6 8 7
i
j
3 4 2 5 9 6 8 7
第二遍循環(huán)結(jié)束
只有第二部分進行第三次循環(huán)
此時pivot把數(shù)組分成兩部分{3, 4, 2}和{9, 6, 8, 7}
不斷循環(huán)典阵，排序，分組镊逝，直到最后每一組都只剩1個數(shù)
最后“將所有組合并”（實際上數(shù)組沒有分組壮啊，只是每次對部分?jǐn)?shù)據(jù)進行操作）
得到{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
快速排序(遞歸版、從小到大)的Java實現(xiàn)如下：
public static void recursiveQuickSort(int[] nums, int head, int tail) {
int i = head, j = tail;
int pivot = nums[head];
while (i < j) {
while (i < j) {
if (pivot >= nums[j]) {
nums[i++] = nums[j];
break;
}
j--;
}
while (i < j) {
if (pivot <= nums[i]) {
nums[j--] = nums[i];
break;
}
i++;
}
}
nums[i] = pivot;
if (i - 1 - head > 0) {
recursiveQuickSort(nums, head, i - 1);
}
if (tail - i - 1 > 0) {
recursiveQuickSort(nums, i + 1, tail);
}
}
歸并排序
Median of Two Sorted Arrays這道題我用的排序法就是歸并排序撑蒜，歸并排序是建立在歸并操作上的一種有效的排序算法歹啼。該算法是采用分治法的一個非常典型的應(yīng)用。它的原理如下：先申請一個空間用于存儲排序后的序列减江，大小為兩個已經(jīng)排序的序列大小之和染突。在兩個已經(jīng)排序的序列頭部分別放置指針，比較指針?biāo)冈氐拇笮”沧疲^小的(或較大的)復(fù)制到剛剛申請的新序列空間份企，該指針后移，重復(fù)比較巡莹、復(fù)制到新序列尾部司志、后移指針，直到遍歷完其中一個序列降宅，則另一個序列的剩余元素全部原序復(fù)制到新序列尾部骂远。歸并排序是穩(wěn)定的排序算法，最壞時間復(fù)雜度是O(nlogn)腰根，最優(yōu)時間復(fù)雜度是O(n)激才，平均時間復(fù)雜度是O(nlogn)，需要O(n)額外空間额嘿。
下面是對{1, 3, 5, 7, 9, 2, 4, 6, 8, 0}進行歸并排序(遞歸版)的具體過程
{1 3 5 7 9 2 4 6 8 0}
第一層遞歸 {1 3 5 7 9} | {2 4 6 8 0}
第二層遞歸 {1 3 5} | {7 9} | {2 4 6} | {8 0}
第三層遞歸 {1 3} |{5}|{7}|{9} | {2 4}|{6}|{8}|{0}
第四層遞歸 {1}|{3}|{5}|{7}|{9} |{2}|{4}|{6}|{8}|{0}
第一層歸并 {1 3} |{5}| {7 9} | {2 4}|{6}| {0 8}
第二層歸并 {1 3 5} | {7 9} | {2 4 6} | {0 8}
第三層歸并 {1 3 5 7 9} | {0 2 4 6 8}
第四層歸并 {0 1 2 3 4 5 6 7 8 9}
歸并排序(遞歸版瘸恼、從小到大)的Java實現(xiàn)如下：
public static void merge(int[] nums, int head, int median, int tail) {
int[] nums1 = new int[median - head + 1];
int[] nums2 = new int[tail - median];
int length1 = nums1.length, length2 = nums2.length;
System.arraycopy(nums, head, nums1, 0, length1);
System.arraycopy(nums, median + 1, nums2, 0, length2);
int i = 0, j = 0, k = head;
while (i < length1&&j < length2) {
nums[k++] = (nums1[i] < nums2[j])?nums1[i++]:nums2[j++];
}
while (i < length1) {
nums[k++] = nums1[i++];
}
while (j < length2) {
nums[k++] = nums2[j++];
}
}
public static void recursiveMergeSort(int[] nums, int head, int tail) {
int median = (head + tail)/2;
if (median != tail) {
recursiveMergeSort(nums, head, median);
recursiveMergeSort(nums, median + 1, tail);
}
merge(nums, head, median, tail);
}
堆排序
堆排序，是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法册养。堆排序的時間復(fù)雜度為O(nlogn)东帅，是不穩(wěn)定的排序算法，且具有空間原址性：任何時候都只需要常數(shù)個額外的元素空間存儲臨時數(shù)據(jù)球拦。
二叉堆圖文介紹 參考
堆排序(大根堆靠闭、從小到大)的Java實現(xiàn)如下：
public static void maxHeapDown(int[] nums, int head, int tail) {
int p = head, l = 2*p + 1, r = l + 1;
int tmp = nums[p];
for (; l <= tail; p = l,l = 2*l + 1,r = l + 1) {
if (l < tail && nums[l] < nums[r]) {
l = r;
}
if (tmp >= nums[l]) {
break;
} else {
nums[p] = nums[l];
nums[l]= tmp;
}
}
}
public static void heapSort(int[] nums) {
int i, tmp, length = nums.length;
for (i = length/2 - 1; i >= 0; i--) {
maxHeapDown(nums, i, length - 1);
}
for (i = length - 1; i > 0; i--) {
tmp = nums[0];
nums[0] = nums[i];
nums[i] = tmp;
maxHeapDown(nums, 0, i - 1);
}
}
以上7種常見排序都是基于比較的排序帐我，基于比較的排序的時間復(fù)雜度的極限是O(nlogn)，下面我給大家介紹三種基于計算的排序算法愧膀，它們都是線性的拦键，時間復(fù)雜度為O(n)。
桶排序
桶排序的思想特別簡單扇调，就是找出所給序列中最大的元素矿咕，新建一個大小為最大元素加一的序列并初始化為全0，所給序列中元素的大小與新建的序列的下標(biāo)相對應(yīng)狼钮，遍歷所給序列碳柱，每遇到一個元素，以這個元素為下標(biāo)的新序列的元素就自加1熬芜。桶排序是穩(wěn)定的排序算法莲镣，時間復(fù)雜度為O(n)，需要O(k)額外空間涎拉。
下面我們分析一下對數(shù)組{1, 3, 5, 7, 9, 2, 4, 6, 8, 0瑞侮， 0}進行桶排序的過程
1、遍歷所給數(shù)組得到最大元素9
2鼓拧、新建一個長度為9+1的數(shù)組半火，并初始化為全0 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
3、遍歷所給數(shù)組季俩，遇到第一個元素1钮糖，將新建數(shù)組中下標(biāo)為1的元素自加1 {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}
4、同理酌住，遇到第二個元素3店归，將新建數(shù)組中下標(biāo)為3的元素自加1 {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0}
5、遍歷完成后酪我，新數(shù)組為 {2, 1, 1, 1, 1, 1, 1, 1, 1, 1}
6消痛、遍歷新數(shù)組，當(dāng)遇到非零元素時都哭，為所給數(shù)組賦予非零元素個的下標(biāo)的值秩伞，如非零元素2，下標(biāo)為0欺矫，則對所給序列的前兩個元素賦值0
桶排序(從小到大)的Java實現(xiàn)如下：
public static int maxElemOfNums(int[] nums) {
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i] + 1;
}
}
return max;
}
public static void bucketSort(int[] nums) {
int length = nums.length, max = maxElemOfNums(nums), i, j;
int[] bucket = new int[max];
for (i = 0; i < length; i++) {
bucket[nums[i]]++;
}
for (i = 0,j = 0; i < max; i++) {
while ((bucket[i]--) > 0) {
nums[j++] = i;
}
}
}
計數(shù)排序
計數(shù)排序是對桶排序的一種改進纱新，其基本思想是：對于給定序列中的元素x，確定小于(大于)x的元素個數(shù)汇陆。利用這一信息，可以直接把x放到它在輸出序列中的位置上带饱。計數(shù)排序是穩(wěn)定的排序算法毡代，時間復(fù)雜度為O(n+k)阅羹，需要O(n+k)額外空間。
計數(shù)排序(從小到大)的Java實現(xiàn)如下：
public static void countSort(int[] nums) {
int length = nums.length, max = maxElemOfNums(nums), i, j;
int[] temp = new int[length];
System.arraycopy(nums, 0, temp, 0, length);
int[] bucket = new int[max];
for (i = 0; i < length; i++) {
bucket[temp[i]]++;
}
for (i = 1; i < max; i++) {
bucket[i] += bucket[i - 1];
}
for (i = 0; i < length; i++) {
nums[bucket[temp[i]] - 1] = temp[i];
bucket[temp[i]]--;
}
}
基數(shù)排序
基數(shù)排序是對計數(shù)排序的一種改進教寂，它是這樣實現(xiàn)的：將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長度捏鱼，數(shù)位較短的數(shù)前面補零。然后酪耕，從最低位開始导梆，依次進行一次排序(計數(shù)排序)。這樣從最低位排序一直到最高位排序完成以后迂烁，數(shù)列就變成一個有序序列看尼。基數(shù)排序是穩(wěn)定的排序算法盟步，時間復(fù)雜度為O(kn)藏斩，需要O(n)額外空間。
基數(shù)排序(從小到大)的Java實現(xiàn)如下：
public static void radixSort(int[] nums) {
int exp, length = nums.length, max = maxElemOfNums(nums), i;
for (exp = 1; (max - 1)/exp > 0; exp *= 10) {
int[] temp = new int[length];
int[] buckets = new int[max];
for (i = 0; i < length; i++) {
buckets[(nums[i]/exp)%10]++;
}
for (i = 1; i < max; i++) {
buckets[i] += buckets[i - 1];
}
for (i = length - 1; i >= 0; i--) {
temp[buckets[(nums[i]/exp)%10] - 1] = nums[i];
buckets[(nums[i]/exp)%10]--;
}
System.arraycopy(temp, 0, nums, 0, length);
}
}
