簡介：本文主要總結(jié)了以下幾個排序算法：冒泡排序、選擇排序猜绣、插入排序灰殴、希爾排序、歸并排序掰邢、快速排序牺陶、堆排序伟阔、計數(shù)排序、桶排序掰伸、基數(shù)排序
冒泡排序（Bubble Sort）
基本版原理：從左至右依次進行兩兩比較皱炉，將最大的元素冒泡至最右邊，此為1輪冒泡狮鸭，然后重復n次合搅，n為數(shù)組長度。
優(yōu)化版原理：在基本版里歧蕉，如果數(shù)組已經(jīng)排好序灾部，時間復雜度并不是最優(yōu)的O(n)，為了使得復雜度降低惯退，優(yōu)化版記錄數(shù)組中最后一次交換的位置赌髓，則此位置后的數(shù)組已經(jīng)有序，則每次只需遍歷到該位置即可蒸痹。
冒泡排序是穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class BubbleSort {
/**
* 基本版的冒泡排序
* @param nums
*/
public void buubleSort(int[] nums) {
int len = nums.length;
if (len <= 1) return ;
for (int i=0; i<len; i++) {
for (int j=0; j<len-i-1; j++) {
if (nums[j] > nums[j+1]) {
swap(nums, j, j+1);
}
}
}
}
/**
* 優(yōu)化版的冒泡排序
* @param nums
*/
public void bubbleSortOptimize(int[] nums) {
int len = nums.length;
if (len <= 1) return ;
int lastSwapPos = len - 1;//最后一次交換的位置
while (lastSwapPos != 0) {//為0時循環(huán)終止春弥，排序完成
int pos = 0;
for (int i=0; i<lastSwapPos; i++) {
if (nums[i] > nums[i+1]) {
swap(nums, i, i+1);
pos = i;//每發(fā)生一次交換，則記錄交換的位置
}
}
lastSwapPos = pos;//更新最后一次交換的位置
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 冒泡排序動態(tài)排序圖：
bubble sort
選擇排序 （Selection Sort）
原理：從左至右選出最大的元素叠荠，并與最右邊未排好序的第一個元素進行交換，此為1次選擇排序扫责，然后重復n次榛鼎，n為數(shù)組長度。
選擇排序是不穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class SelectionSort {
/**
* 選擇排序
* @param nums
*/
public void selectionSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
for (int i=0; i<len; i++) {
int index = 0;//最大元素索引
for (int j=1; j<len-i; j++) {
if (nums[j] > nums[index]) index = j;
}
swap(nums, index, len-i-1);//元素交換
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 選擇排序動態(tài)排序圖：
selection sort
插入排序 （Insertion Sort）
原理：遍歷數(shù)組中的每個元素鳖孤，對于每個元素者娱，其左邊的元素已經(jīng)排好序，只需將其插入到對應的位置即可苏揣，即從右至左遍歷左邊的元素黄鳍，并與比該元素大的進行位置交換。
插入排序是穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class InsertionSort {
/**
* 插入排序
* @param nums
*/
public void insertionSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
for (int i=0; i<len; i++) {
for (int j=i; j>0; j--) {
if (nums[j] < nums[j-1]) swap(nums, j, j-1);
}
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 插入排序動態(tài)排序圖：
insertion sort
希爾排序（Shell Sort）
原理：希爾排序是插入排序的一種更高效的改進版本平匈。首先根據(jù)設(shè)定的步長gap框沟，它將待排序的數(shù)組分為若干個子序列，然后分別對每個子序列進行插入排序增炭，修改步長忍燥，重復上面的操作直至步長為1，排序完成隙姿。
希爾排序是不穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class ShellSort {
/**
* 希爾排序O(n^3/2)
* @param nums
*/
public void shellSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int gap = 1;
//設(shè)置步長
while (gap < len / 3) {
gap = gap * 3 + 1;
}
//根據(jù)步長循環(huán)
for (; gap > 0; gap /= 3) {
//對gap位置后的元素進行簡單插入排序
for (int i = gap; i < len; i++) {
int j = i - gap, tmp = nums[i];
for (; j >= 0 && nums[j] > tmp; j -= gap) {
//將大于tmp的元素后移gap個單位
nums[j + gap] = nums[j];
}
//放置tmp元素
nums[j + gap] = tmp;
}
}
}
}
2. 希爾排序演示圖：
shell sort
歸并排序 （Merge Sort）
遞歸版原理：將待排序長度為n的數(shù)組分為兩個長度為n/2的子序列梅垄，然后對這兩個子序列分別進行歸并排序，最后將排好序的兩個子序列進行合并成排好序的數(shù)組输玷。由于子序列的合并不能在原數(shù)組直接進行队丝，所以需要長度為n的輔助存儲空間在子序列合并時使用靡馁。
迭代版原理：根據(jù)歸并排序的思想，先將原數(shù)組分為不可再分的子序列机久，然后再逐層合并奈嘿。所以迭代版歸并排序中首先設(shè)定一個步長block為1，并在循環(huán)的過程中每次增加1倍吞加，目的是將原數(shù)組分為n/block個子序列裙犹，每個序列的長度為block，然后針對每個block衔憨，對每兩個相鄰的長度為block的序列進行排序叶圃。當block大于等于n/2，排序完成践图。
歸并排序是穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class MergeSort {
/**
* 遞歸版歸并排序
* @param nums
* @param start 起始位置
* @param end 結(jié)束位置
* @param extra 輔助的存儲空間
*/
public void mergeSort(int[] nums, int start, int end, int[] extra) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int middle = (start + end)/2;
//子序列1從start-middle
mergeSort(nums, start, middle, extra);
//子序列2從middle+1-end
mergeSort(nums, middle+1, end, extra);
//子序列1和2進行合并
merge(nums, start, middle, end, extra);
}
/**
* 子序列合并操作
* @param nums
* @param start-middle 子序列1
* @param middle+1-end 子序列2
* @param extra
*/
public void merge(int[] nums, int start, int middle, int end, int[] extra) {
int left = start, right = middle+1;
int index = start;
//將兩個子序列的元素值進行比較掺冠，從小到大拷貝進輔助數(shù)組
while (left <= middle && right <= end) {
if (nums[left] < nums[right]) {
extra[index++] = nums[left++];
} else {
extra[index++] = nums[right++];
}
}
//如果兩個子序列的任一個還有元素未拷貝，則繼續(xù)拷貝
while (left <= middle) extra[index++] = nums[left++];
while (right <= end) extra[index++] = nums[right++];
//將合并后的元素重新拷貝回原數(shù)組
for (int i=start; i<=end; i++) {
nums[i] = extra[i];
}
}
/**
* 迭代版歸并排序
* @param nums
* @param extra 輔助的存儲空間
*/
public void mergeSortIterator(int[] nums, int[] extra) {
int len = nums.length;
if (len <= 1) return;
//步長block
for (int block=1; block<len; block=block*2) {
//每兩個相鄰的長度為block的序列進行排序
for (int start=0; start<len; start=start+block*2) {
int left = start,
middle = (start + block) < len ? (start + block) : len,
end = (start + block*2) < len? (start + block*2) : len;
int right = middle, index = start;
while (left < middle && right < end) {
if (nums[left] < nums[right]) {
extra[index++] = nums[left++];
} else {
extra[index++] = nums[right++];
}
}
while (left < middle) extra[index++] = nums[left++];
while (right < end) extra[index++] = nums[right++];
for (int i=start; i<end; i++) nums[i] = extra[i];
}
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 歸并排序動態(tài)排序圖：
merge sort
快速排序 （Quick Sort）
遞歸版原理：首先码党，選取一個元素作為基準pivot德崭，將小于該基準的元素放在左邊，大于該基準的元素放在右邊揖盘，該基準位于中間位置眉厨，稱為分區(qū)（partition）操作，然后遞歸地分別對左右兩邊的元素進行快速排序兽狭。根據(jù)所選基準元素位置的不同憾股，源碼中分別實現(xiàn)了選取第一個元素、最后一個元素及中間元素作為基準的遞歸快速排序箕慧，原理相同服球，但實現(xiàn)上略有不同，需要注意颠焦。
迭代版原理：借助棧來對待排序序列的起始位置和結(jié)束位置進行保存斩熊，首先入棧全局數(shù)組的位置即0-n-1，然后循環(huán)訪問該棧伐庭，只要棧非空粉渠，則繼續(xù)排序，并將新的位置信息入棧似忧，直至椩眩空，排序完成盯捌。
快速排序是不穩(wěn)定的排序
1. Java源碼實現(xiàn)：
import java.util.LinkedList;
public class QuickSort {
/**
* 選擇第一個元素作為基準的遞歸快排
* @param nums
* @param start 起始位置
* @param end 結(jié)束位置
*/
public void quickSortStart(int[] nums, int start, int end) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int left = start, right = end;
int pivot = nums[left];
/*每次循環(huán)先從右至左遍歷淳衙，找到比基準元素小的第一個元素，
* 然后從左至右遍歷，找到比基準元素大的第一個元素箫攀，
* 最后交換兩個元素的位置肠牲，循環(huán)終止時left==right，
* 且right指向最后一個小于該基準元素的位置
*/
while (left < right) {
while (left < right && nums[right] >= pivot) right --;
while (left < right && nums[left] <= pivot) left ++;
swap(nums, left, right); //when left == right;
}
//交換基準元素與最后一個小于基準的元素的位置
swap(nums, start, right);
quickSortStart(nums, start, right-1);
quickSortStart(nums, right+1, end);
}
/**
* 選擇最后一個元素作為基準的遞歸快排
* @param nums
* @param start 起始位置
* @param end 結(jié)束位置
*/
public void quickSortEnd(int[] nums, int start, int end) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int left = start, right = end;
int pivot = nums[end];
/*每次循環(huán)先從左至右遍歷靴跛，找到比基準元素大的第一個元素缀雳，
* 然后從右至左遍歷，找到比基準元素小的第一個元素梢睛，
* 最后交換兩個元素的位置肥印，循環(huán)終止時left==right，
* 且left指向第一個大于該基準元素的位置
*/
while (left < right) {
while (left < right && nums[left] <= pivot) left ++;
while (left < right && nums[right] >= pivot) right --;
swap(nums, left, right);
}
//交換基準元素與第一個大于基準的元素的位置
swap(nums, left, end);
quickSortEnd(nums, start, left-1);
quickSortEnd(nums, left+1, end);
}
/**
* 選擇中間位置元素作為基準的遞歸快排
* @param nums
* @param start 起始位置
* @param end 結(jié)束位置
*/
public void quickSortMiddle(int[] nums, int start, int end) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int left = start, right = end;
int middle = (left + right)/2;
int pivot = nums[middle];
//注意與以上兩種方法的不同 left <= right 而非<
while (left <= right) {
//nums[left] < pivot 而非 <= , nums[right] > pivot 而非>=
while (left <= right && nums[left] < pivot) left ++;
while (left <= right && nums[right] > pivot) right --;
//需要判斷因為left可能大于right
if (left <= right){
swap(nums, left, right);
//需要有绝葡，因為遇到等于pivot的元素時會陷入死循環(huán)
left++;
right--;
}
}
quickSortMiddle(nums, start, right);
quickSortMiddle(nums, left, end);
}
class Element {
int start, end;
public Element(int start, int end) {
this.start = start;
this.end = end;
}
}
/**
* 迭代版快排
* @param nums
*/
public void quickSortIterator(int[] nums) {
int len = nums.length;
if (len <= 1) return;
LinkedList<Element> s = new LinkedList<Element>();
s.push(new Element(0, len-1));
while (!s.isEmpty()) {
Element e = s.pop();
int start = e.start, end = e.end;
int left = start, right = end;
if (left >= right) continue;
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] >= pivot) right--;
while (left < right && nums[left] <= pivot) left++;
swap(nums, left, right);
}
swap(nums, start, right);
s.push(new Element(start, right - 1));
s.push(new Element(right + 1, end));
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 快速排序動態(tài)排序圖：
quick sort
堆排序 （Heap Sort）
原理：首先將待排序數(shù)組構(gòu)建為大小為n的最大（猩罴睢）堆，然后將最大的堆頂元素與數(shù)組最后一個元素交換藏畅，將最大的元素放在最后一個位置敷硅，接下來不斷調(diào)整最大堆并進行與上面相同的操作，此時堆的大小為n-1并依次遞減愉阎，直至為0時绞蹦，排序完成。
堆排序是不穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class HeapSort {
/**
* 最大堆排序
* @param nums
*/
public void heapSortMax(int[] nums) {
int len = nums.length;
//建堆操作
for (int i=(len-1)/2; i>=0; i--) {
maxHeap(nums, i, len);
}
//排序操作
for (int i=0; i<len; i++) {
swap(nums, 0, len-i-1);
maxHeap(nums, 0, len-i-1);
}
}
/**
* 最大堆調(diào)整操作
* @param nums
* @param parent 父節(jié)點
* @param len 堆的大小
*/
public void maxHeap(int[] nums, int parent, int len) {
int left = parent * 2 + 1;
if (left > len-1) return;
int right = left + 1;
int max = left;
if (right <= len-1 && nums[left] < nums[right]) max = right;
if (nums[parent] < nums[max]) {
swap(nums, parent, max);
maxHeap(nums, max, len);
}
}
/**
* 最小堆排序
* @param nums
*/
public void heapSortMin(int[] nums) {
int len = nums.length;
if (len <= 1) return;
//建堆操作
for (int i=(len-1)/2; i>=0; i--){
minHeap(nums, i, len);
}
//排序操作
for (int i=0; i<len; i++) {
swap(nums, 0, len-1-i);
minHeap(nums, 0, len-1-i);
}
}
/**
* 最小堆調(diào)整操作
* @param nums
* @param parent 父節(jié)點
* @param len 堆的大小
*/
public void minHeap(int[] nums, int parent, int len) {
int left = parent * 2 + 1;
if (left > len-1) return;
int right = left + 1;
int min = left;
if (right <= len-1 && nums[right] < nums[left]) min = right;
if (nums[parent] > nums[min]) {
swap(nums, parent, min);
minHeap(nums, min, len);
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 堆排序動態(tài)排序圖：
heap sort
計數(shù)排序 （Counting Sort）
原理：找出待排序數(shù)組中最小和最大的元素榜旦，統(tǒng)計每個元素i出現(xiàn)的次數(shù)并存入數(shù)組count的第i-min項幽七，然后累加所有的計數(shù)（count數(shù)組中的第一個元素開始，每一項和前一項相加并存入該項）章办，能夠得出每個元素的最終位置锉走，最后考慮算法的穩(wěn)定性，反向填充目標數(shù)組（倒序遍歷原數(shù)組）藕届，將每個元素nums[i]放入新數(shù)組extra中第count[i]項，每放入一個元素就將count[i]減1亭饵，詳見穩(wěn)定版計數(shù)排序休偶。當不考慮穩(wěn)定性時，可以省略輔助數(shù)組extra辜羊，遍歷數(shù)組count踏兜，按順序?qū)放回原數(shù)組，詳見優(yōu)化版計數(shù)排序八秃。
計數(shù)排序是穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class CountingSort {
/**
* 穩(wěn)定版計數(shù)排序
* @param nums
* @return int[]
*/
public int[] countingSort(int[] nums) {
int len = nums.length;
if (len <= 1) return nums;
int[] extra = new int[len];
int min = nums[0], max = nums[0];
for (int i = 1; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
int k = max - min + 1;
int[] count = new int[k];
//計數(shù)
for (int i = 0; i < len; i++) {
count[nums[i] - min]++;
}
//計數(shù)累加
for (int i = 1; i < k; i++) {
count[i] = count[i] + count[i-1];
}
//考慮到排序的穩(wěn)定性碱妆，所以需要進行反向填充
for (int i = len - 1; i >= 0; i--) {
extra[--count[nums[i] - min]] = nums[i];
}
return extra;
}
/**
* 優(yōu)化版計數(shù)排序
* @param nums
*/
public void countingSortOptimize(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int min = nums[0], max = nums[0];
for (int i = 1; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
int k = max - min + 1;
int[] count = new int[k];
//計數(shù)
for (int i = 0; i < len; i++) {
count[nums[i] - min]++;
}
int index = 0;
for (int i = 0; i < k; i++) {
while (count[i] != 0) {
nums[index++] = i + min;
count[i]--;
}
}
}
}
2. 計數(shù)排序動態(tài)排序圖：
optimal counting sort
桶排序
原理：先將待排序數(shù)組分到有限數(shù)量的桶里，每個桶再分別進行排序（排序算法可以是其他排序算法也可以是遞歸的桶排序）昔驱。具體過程如下：設(shè)置一定數(shù)量的數(shù)組作為空桶疹尾，然后將待排序的數(shù)組中的元素放到對應的桶中，再對每個非空桶進行排序，最后將非空桶的元素依次放回原數(shù)組纳本。
桶排序是穩(wěn)定的排序
1. Java源碼實現(xiàn)：
import java.util.ArrayList;
import java.util.List;
public class BucketSort {
/**
* 桶排序
* @param nums
*/
public void bucketSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int min = nums[0], max = nums[0];
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
//步長
int step = 2;
//桶的個數(shù)
int bucketNum = max/step - min/step + 1;
List<List<Integer>> buckets = new ArrayList<List<Integer>>();
//桶的初始化
for (int i = 0; i < bucketNum; i++) {
buckets.add(new ArrayList<Integer>());
}
//將待排序數(shù)組元素裝桶
for (int i = 0; i < len; i++) {
int index = (nums[i] - min)/step;
buckets.get(index).add(nums[i]);
}
//將桶內(nèi)元素進行插入排序后重新放回原數(shù)組
int index = 0;
for (int i = 0; i < bucketNum; i++) {
List<Integer> bucket = buckets.get(i);
insertionSort(bucket);
for (int j : bucket) {
nums[index++] = j;
}
}
}
/**
* 桶內(nèi)元素的插入排序
* @param bucket
*/
public void insertionSort(List<Integer> bucket) {
int size = bucket.size();
for (int i = 0; i < size; i++) {
for (int j = i; j > 0; j--) {
if (bucket.get(j) < bucket.get(j - 1)) {
swap(bucket, j, j - 1);
}
}
}
}
public void swap(List<Integer> bucket, int i, int j) {
int tmp = bucket.get(i);
bucket.set(i, bucket.get(j));
bucket.set(j, tmp);
}
}
2. 桶排序演示圖：
bucket sort（step=20）
基數(shù)排序
原理：將整數(shù)按位切割成不同的數(shù)字窍蓝，然后按每個位數(shù)分別比較。具體過程如下：先找出待排序數(shù)組的最大數(shù)繁成，并計算其位數(shù)吓笙，即最終循環(huán)排序的次數(shù)，然后按照位數(shù)從最低位開始進行計數(shù)排序巾腕，直到最高位面睛，最后數(shù)組排序完成。
基數(shù)排序是穩(wěn)定的排序
1. Java源碼實現(xiàn)：
public class RadixSort {
/**
* 基數(shù)排序（LSD：Least Significant Digital）
* @param nums
*/
public void radixSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int digital = maxDigital(nums, len);
//需要循環(huán)排序的次數(shù)尊搬，為最大數(shù)的位數(shù)
for (int i = 0; i < digital; i++) {
int[] count = new int[10];
//每次計算的基數(shù)
int radix = (int)Math.pow(10, i);
//計數(shù)
for (int j = 0; j < len; j++) {
count[(nums[j] / radix) % 10]++;
}
//累加
for (int j = 1; j < 10; j++) {
count[j] = count[j] + count[j-1];
}
//反向填充
int[] tmp = new int[len];
for (int j = len - 1; j >= 0; j--) {
tmp[--count[(nums[j] / radix) % 10]] = nums[j];
}
//重新賦值給原數(shù)組
for (int j = 0; j < len; j++) {
nums[j] = tmp[j];
}
}
}
/**
* 求最大數(shù)的位數(shù)
* @param nums 待排序數(shù)組
* @param len 數(shù)組長度
* @return 位數(shù)
*/
public int maxDigital(int[] nums, int len) {
int max = nums[0];
for (int i = 1; i < len; i++) {
max = Math.max(max, nums[i]);
}
int digital = 1;
while (max >= 10) {
max = max / 10;
digital++;
}
return digital;
}
}
2. 基數(shù)排序動態(tài)排序圖：
radix sort（LSD）
