排序
符號：Θ
log是以任何數(shù)為底
lg是以10為底
ln是以e為底
- 插入排序
- 選擇排序
- 堆排序
- 歸并排序
- 冒泡排序
- 快速排序
- 桶排序
- 基數(shù)排序
- 計數(shù)排序
插入排序
插入排序（Insertion Sort）是一種簡單的插入排序法，其基本思想是：把待排序的元素按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中朵纷，直到所有的元素插入完為止炭臭，得到一個新的有序序列。
比喻
莫撲克牌袍辞，開始時鞋仍，左手為空并且桌子上的牌面向下，然后每次從牌堆最上面拿走一張牌搅吁，插入到左手的正確位置上威创。
性質(zhì)
- 最好時間復(fù)雜度 : Θ(n)
- 平均時間復(fù)雜度 : Θ(n2)
- 最差時間復(fù)雜度 : Θ(n2)
- 空間復(fù)雜度 : Θ(1)
- 穩(wěn)定性 : 穩(wěn)定
偽代碼
void insertSort(int array[],int length)
{
for (int i = 1; i < length; i++) {
int temp = array[i];
int j = i;
for (; j > 0; j--) {
if (array[j-1] > temp) {
array[j] = array[j-1];
}else{
break;
}
}
array[j] = temp;
}
}
遞歸式：為了排序A[0..k],我們遞歸地排序A[0...k-1]，然后把A[k]插入到已排序的數(shù)組A[0...k-1]中谎懦。
void recursiveInsertSort(int array[], int length, int cur)
{
if (cur < 1)
{
return;
}
//遞歸前一個數(shù)組
recursiveInsertSort(array, length, cur-1);
int value = array[cur];
int j = cur;
for (; j > 0; j--)
{
if (array[j-1] > value){
array[j] = array[j-1];
}else{
break;
}
}
array[j] = value;
}
選擇排序
選擇排序（Selection Sort）的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最卸遣颉（或最大）的一個元素，與待排序序列起始位置的元素交換界拦，直到全部待排序的數(shù)據(jù)元素排完吸申。
性質(zhì)
- 最好時間復(fù)雜度 : Θ(n2)
- 平均時間復(fù)雜度 : Θ(n2)
- 最差時間復(fù)雜度 : Θ(n2)
- 空間復(fù)雜度 : Θ(1)
- 穩(wěn)定性 : 不穩(wěn)定
偽代碼
void selectionSort(int array[], int length)
{
for (int i = 0; i < length-1; ++i)
{
int min = i;
for (int j = i+1; j < length; ++j)
{
if (array[min] > array[j]){
min = j;
}
}
if (min != i){
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
堆排序
堆排序（Heap Sort）指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。
- 堆分為大根堆（k[i]>=k[2i],k[i]>=k[2i+1]）和小根堆（k[i]<=k[2i],k[i]<=k[2i+1]）呛谜。(i=1,2,3...?n/2?)
- 堆是完全二叉樹在跳。
實現(xiàn)堆排序要解決兩個問題：
- 將n個待排序的數(shù)建成堆。
- 輸出堆頂元素后隐岛，調(diào)整剩余元素猫妙，成為一個新堆。
解決：
問題一：從最后一個非葉子節(jié)點（k[?n/2?]）開始的子樹聚凹，使之成為堆割坠，依次向前，直到根節(jié)點妒牙。
問題二：將堆頂輸出彼哼，最后一個節(jié)點換到堆頂，堆被破壞湘今。從堆頂開始敢朱，與左右結(jié)點中較小（或較大）的元素交換摩瞎。繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行交換拴签，直到使之成為堆。
性質(zhì)
- 最好時間復(fù)雜度 : Θ(nlogn)
- 平均時間復(fù)雜度 : Θ(nlogn)
- 最差時間復(fù)雜度 : Θ(nlogn)
- 空間復(fù)雜度 : Θ(1)
- 穩(wěn)定性 : 不穩(wěn)定
偽代碼
//注意：這里的i=（1,2,3...n）
void heapSort(int array[], int length)
{
buildHeap(array, length);
for (int i = length; i >= 1; i--)
{
//交換第一個元素和最后一個元素旗们，即每次將堆頂元素排到未排好序列的最后
int temp = array[0];
array[0] = array[i-1];
array[i-1] = temp;
//重新調(diào)整為堆
heapAdjust(array, i-1, 1);
}
}
///調(diào)整以i結(jié)點為根的樹為堆
void heapAdjust(int array[], int length, int i)
{
int lChild = i*2;
int rChild = i*2 + 1;
int maxIndex = i;
//處理非葉子節(jié)點
if (i <= length/2)
{
if (lChild <= length && array[lChild-1] > array[maxIndex-1])
{
maxIndex = lChild;
}
if (rChild <= length && array[rChild-1] > array[maxIndex-1])
{
maxIndex = rChild;
}
if (maxIndex != i)
{
int temp = array[maxIndex-1];
array[maxIndex-1] = array[i-1];
array[i-1] = temp;
heapAdjust(array, length, maxIndex);
}
}
}
///創(chuàng)建堆
void buildHeap(int array[], int length)
{
//從最后一個非葉子結(jié)點開始蚓哩，調(diào)整為堆
for (int i = length/2; i >= 1; i--)
{
heapAdjust(array, length, i);
}
}
歸并排序
歸并排序（Merge Sort）是將已有序的子序列合并，得到完全有序的序列上渴；即先使每個子序列有序岸梨，再使子序列段間有序。是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用稠氮。
性質(zhì)
- 最好時間復(fù)雜度 : Θ(nlogn)
- 平均時間復(fù)雜度 : Θ(nlogn)
- 最差時間復(fù)雜度 : Θ(nlogn)
- 空間復(fù)雜度 : Θ(n)
- 穩(wěn)定性 : 穩(wěn)定
偽代碼
void mergeSort(int array[], int tempArray[], int low, int high)
{
if (low >= high){
return;
}
//遞歸前半段曹阔、后半段
int mid = (low + high) / 2;
mergeSort(array, tempArray, low, mid);
mergeSort(array, tempArray, mid + 1, high);
int i = low;
int j = mid + 1;
int cur = 0;
while(i <= mid && j <= high)
{
if (array[i] < array[j]){
tempArray[cur] = array[i++];
}else{
tempArray[cur] = array[j++];
}
cur++;
}
while(i <= mid)
{
tempArray[cur++] = array[i++];
}
while(j <= high)
{
tempArray[cur++] = array[j++];
}
for (int i = 0; i < cur; ++i)
{
array[i+low] = tempArray[i];
}
}
冒泡排序
冒泡排序（Bubble Sort）在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)括袒，自上而下對相鄰的兩個數(shù)依次進(jìn)行比較和調(diào)整次兆，讓較大的數(shù)往下沉稿茉，較小的往上冒锹锰。
性質(zhì)
- 最好時間復(fù)雜度 : Θ(n)
- 平均時間復(fù)雜度 : Θ(n2)
- 最差時間復(fù)雜度 : Θ(n2)
- 空間復(fù)雜度 : Θ(1)
- 穩(wěn)定性 : 穩(wěn)定
偽代碼
void bubbleSort(int array[], int length)
{
for (int i = 0; i < length-1; ++i)
{
for (int j = 0; j < length-1-i; ++j)
{
if (array[j] > array[j+1])
{
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
改進(jìn)
1.設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時只要掃描到pos位置即可漓库。
void bubbleSort1(int array[], int length)
{
for (int i = length - 1; i > 0;)
{
int pos = 0;
for (int j = 0; j < i; ++j)
{
if (array[j] > array[j+1])
{
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
pos = j;
}
}
i = pos;
}
}
2.傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半恃慧。
void bubbleSort2(int array[], int length)
{
int low = 0;
int high = length - 1;
while(low < high){
for (int j = low; j < high; j++)
{
//正向冒泡
if (array[j] > array[j+1])
{
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
high--;
for (int j = high; j > low; j--)
{
//反向冒泡
if (array[j-1] > array[j])
{
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
low++;
}
}
快速排序
快速排序（Quick Sort）是對冒泡排序的一種改進(jìn)。通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分渺蒿，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行缤灵，以此達(dá)到整個數(shù)據(jù)變成有序序列。
性質(zhì)
- 最好時間復(fù)雜度 : Θ(nlogn)
- 平均時間復(fù)雜度 : Θ(nlogn)
- 最差時間復(fù)雜度 : Θ(n2)
- 空間復(fù)雜度 : Θ(1)
- 穩(wěn)定性 : 不穩(wěn)定
偽代碼
void quickSort(int array[], int low, int high)
{
if (low >= high)
{
return;
}
int i = low;
int j = high;
int cur = array[i];
int curIndex = i;
while(i < j){
cur = array[i];
curIndex = i;
while(curIndex < j && array[j] >= cur) j--;
array[curIndex] = array[j];
array[j] = cur;
curIndex = j;
while(i < curIndex && array[i] <= cur) i++;
array[curIndex] = array[i];
array[i] = cur;
curIndex = i;
}
quickSort(array, low, curIndex-1);
quickSort(array, curIndex+1, high);
}
改進(jìn)
快速排序是通常被認(rèn)為在同數(shù)量級（O(nlogn)）的排序方法中平均性能最好的善延。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序城侧。
1.為改進(jìn)之易遣，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄嫌佑。
void quickSort1(int array[], int low, int high)
{
if (low >= high)
{
return;
}
int i = low;
int j = high;
int cur = array[i];
int curIndex = i;
while(i < j){
//前后中三點取中 start
cur = array[i];
curIndex = i;
int max = array[i];
int maxIndex = i;
int min = array[i];
int minIndex = i;
if (array[i] > array[j])
{
min = array[j];
minIndex = j;
}else{
max = array[j];
maxIndex = j;
}
if (min > array[(i+j)/2])
{
cur = min;
curIndex = minIndex;
}else if (max < array[(i+j)/2])
{
cur = max;
curIndex = maxIndex;
}else{
cur = array[(i+j)/2];
curIndex = (i+j)/2;
}
//前后中三點取中 end
while(curIndex < j && array[j] >= cur) j--;
array[curIndex] = array[j];
array[j] = cur;
curIndex = j;
while(i < curIndex && array[i] <= cur) i++;
array[curIndex] = array[i];
array[i] = cur;
curIndex = i;
}
quickSort1(array, low, curIndex-1);
quickSort1(array, curIndex+1, high);
}
2.還有一種改進(jìn)方法豆茫，對長度大于k的序列遞歸調(diào)用排序，使序列基本有序屋摇，然后再用插入排序使序列完全有序揩魂。（因為快速排序?qū)居行虻男蛄信判蚵迦肱判驅(qū)居行虻男蛄信判蚩炫谖拢瑑烧吲浜希┮话鉱取值為8的時候效果最佳火脉。
void quickSort2(int array[], int low, int high)
{
if (low >= high)
{
return;
}
int k = 8;
int i = low;
int j = high;
if (j - i < k)
{
//序列小于k，使用插入排序
for (int x = i+1; x <= j; x++)
{
int value = array[x];
int y = x;
for (; y > i; y--)
{
if (array[y-1] > value)
{
array[y] = array[y-1];
}else{
break;
}
}
array[y] = value;
}
}else{
//序列大于k柒啤，使用快速排序
int cur = array[i];
int curIndex = i;
while(i < j){
cur = array[i];
curIndex = i;
while(curIndex < j && array[j] >= cur) j--;
array[curIndex] = array[j];
array[j] = cur;
curIndex = j;
while(i < curIndex && array[i] <= cur) i++;
array[curIndex] = array[i];
array[i] = cur;
curIndex = i;
}
quickSort2(array, low, curIndex-1);
quickSort2(array, curIndex+1, high);
}
}
桶排序
桶排序(Bucket sort)或所謂的箱排序忘分，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里白修。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）妒峦。
基數(shù)排序
基數(shù)排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由鍵值的最右邊開始兵睛，而MSD則相反肯骇，由鍵值的最左邊開始。LSD的基數(shù)排序適用于位數(shù)小的數(shù)列祖很，如果位數(shù)多的話笛丙，使用MSD的效率會比較好，MSD的方式恰與LSD相反假颇，是由高位數(shù)為基底開始進(jìn)行分配胚鸯，其他的演算方式則都相同。
LSD
待排序序列:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
第一步
首先根據(jù)個位數(shù)的數(shù)值笨鸡，在走訪數(shù)值時將它們分配至編號0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下來將這些桶子中的數(shù)值重新串接起來姜钳，成為以下的數(shù)列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下來將這些桶子中的數(shù)值重新串接起來形耗，成為以下的數(shù)列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
MSD
待排序序列:
170, 45, 75, 90, 2, 24, 802, 66
第一步
我們看到哥桥，這里面的最大的數(shù)是3位數(shù)。所以說我們開始從百位對這些數(shù)進(jìn)行分組
0: 045, 075, 090,002, 024, 066
1: 170
2-7: 空
8: 802
9: 空
第二步
從這里開始就和LSD基數(shù)排序有差別了激涤。在LSD基數(shù)排序中拟糕，每次分好組以后開始對桶中的數(shù)據(jù)進(jìn)行收集。然后根據(jù)下一位，對收集后的序列進(jìn)行分組送滞。而對于MSD侠草，在這里不會對桶中的數(shù)據(jù)進(jìn)行收集。我們要做的是檢測每個桶中的數(shù)據(jù)犁嗅。當(dāng)桶中的元素個數(shù)多于1個的時候梦抢，要對這個桶遞歸進(jìn)行下一位的分組。
在這個例子中愧哟，我們要對0桶中的所有元素根據(jù)十位上的數(shù)字進(jìn)行分組
0: 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 075
8: 空
9: 090
按照上面所說奥吩，我們應(yīng)該再遞歸的對每個桶中的元素根據(jù)個位上的數(shù)進(jìn)行分組。但是我們發(fā)現(xiàn)蕊梧，現(xiàn)在在每個桶中的元素的個數(shù)都是小于等于1的霞赫。因此，到這一步我們就開始回退了肥矢。也就是說我們開始收集桶中的數(shù)據(jù)端衰。收集完成以后，回退到上一層甘改。此時按照百位進(jìn)行分組的桶變成了如下的形式:
0: 002, 024, 045,066, 075, 090
1: 170
2-7: 空
8: 802
9: 空
第三步
然后我們在對這個桶中的數(shù)據(jù)進(jìn)行收集旅东。收集起來以后序列如下：
2, 24, 45, 66, 75, 90, 170, 802
基數(shù)排序的復(fù)雜度分析
設(shè)待排序列為n個記錄，d個關(guān)鍵碼十艾，關(guān)鍵碼的取值范圍為radix抵代，則進(jìn)行鏈?zhǔn)交鶖?shù)排序的時間復(fù)雜度為O(d(n+radix))，其中忘嫉，一趟分配時間復(fù)雜度為O(n)荤牍，一趟收集時間復(fù)雜度為O(radix)，共進(jìn)行d趟分配和收集庆冕。
復(fù)雜度
結(jié)束語
本文代碼以及更多更新在github上康吵。
