預備知識
概念說明
穩定和非穩定
- 穩定：對于陣列中任意兩個元素，某次排序前 a > b a>b a>b，排序后仍有 a > b a>b a>b，也就是說每次排序都朝著更加有序的方向發展，最壞的時候也會不會比上一次排序無序，
- 非穩定：對于陣列中任意兩個元素，某次排序前 a > b a>b a>b，排序后可能會出現有 a < b a<b a<b，則稱為排序演算法不穩定，也就是說排序演算法雖然最侄訓使得陣列變為有序，但是中間程序有時候會使得陣列比上一步排序后更無序，
原地和非原地
- 原地：只需要常數空間的額外輔助空間，如堆排序，
- 非原地：需要非常數的額外輔助空間，
比較和非比較
- 比較：排序中需要對元素的大小做對比（演算法1-7），
- 非比較：排序中不需要對元素的大小做對比（演算法8-10，即桶排序系列），
排序演算法分類
關于
- 本文為了方便各位將程式復制過去就能直接除錯和運行，所以都單獨寫成在了main()函式里，沒有寫成類方法的形式，
- 本文的所有演算法都經過測驗，copy過去就可以直接運行，
- 本文還有很多不足，后續會持續改進，
1、冒泡排序
經典排序演算法，演算法啟蒙，
1.1 核心思想
冒泡排序（Bubble Sort），從陣列的第 0 個元素開始，每次遍歷，依據大小關系選擇是否將第 i 個數和第 i+i 個數交換，每次回圈，最大的數被放到陣列的尾部，小的數漸漸漂浮到陣列的前列，就像泡泡逐漸從池底浮到水面一樣，因此稱之為冒泡排序，
1.2 代碼實作
冒泡排序的代碼如下
//sort1:冒泡排序
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> array={9,5,1,5,6,3,2,7,5,7,10,14};
int n=array.size();
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
{
if(array[j]>array[j+1])
{
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
//列印排序后的陣列
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
return 0;
}
上面的代碼實際每次回圈都會把大的元素后移，小的元素前移，冒泡排序雖然是最基礎的排序演算法，但是它是一種穩定的排序演算法，每次回圈都能保證陣列的有序性提升或者至少不變，
1.3 演算法性能
時間復雜度：
- O ( n 2 ) O(n^2) O(n2)
空間復雜度：
- O ( 1 ) O(1) O(1)
2、選擇排序
2.1 核心思想
選擇排序（Selection Sort），從陣列的第 0 個元素開始，每次回圈，找到當前剩余未排序的數中最小的值，將其與已排序最后一個的數的后一個數交換，
2.2 代碼實作
//sort2:選擇排序
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> array={9,4,6,8,3,5,1,2,7};
int n=array.size();
for(int i=0;i<n;i++)
{
int min_num=array[i];
int pos=i;
for(int j=i;j<n;j++)
{
if(array[j]<=min_num)
{
pos=j;
min_num=array[j];
}
}
int temp=array[i];
array[i]=min_num;
array[pos]=temp;
}
//列印排序后的陣列
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
return 0;
}
2.3 演算法性能
時間復雜度：
- O ( n 2 ) O(n^2) O(n2)
空間復雜度：
- O ( 1 ) O(1) O(1) ，只需要常數額外空間，
冒泡排序和選擇排序的效率很低，究其原因是因為其對于某些常見情況如陣列已經比較有序的情況沒有優化，
3、插入排序
3.1 核心思想
插入排序（Insertion Sort），從陣列的第 0 個元素開始，認為其已經排過序，將其作為參照，每次回圈，找到陣列的第 i （i>=1）個元素在前面已經排過序的數中位置，將其插入到已經排序過的數中，排過序的數依次后移相應的位數，和選擇排序一樣，我們將排過序的數放在陣列的頭部，當然也可以選擇將最大的數放到尾部，從尾部向前遍歷，看君喜好，
3.2 代碼實作
//sort3:基本插入排序
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> array={9,4,6,8,3,5,1,2,7};
int n=array.size();
int current;
for(int i=1;i<n;i++)
{
current=array[i];
int pre_index=i-1;
while(pre_index>=0 && current<array[pre_index])
{
array[pre_index+1]=array[pre_index]; //這兒的處理比較巧妙，即判斷一次，后移一位
pre_index--;
}
array[pre_index+1]=current; //插入的位置下標是pre_index+1
}
//列印排序后的陣列
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
return 0;
}
3.3 演算法性能
時間復雜度：
- O ( n 2 ) O(n^2) O(n2)
空間復雜度：
- O ( 1 ) O(1) O(1) ，只需要常數額外空間，
插入排序的演算法對于比較有序的陣列效率很高，很多時候其效率要高于冒泡排序和選擇排序，但是到目前為止，排序演算法的時間復雜度都沒有突破 O ( n 2 ) O(n^2) O(n2) ，接下來介紹時間復雜度優于（或者大多數情況下優于 O ( n 2 ) O(n^2) O(n2) 的排序演算法，
4、希爾排序（詳解）
4.1 核心思想
希爾排序（Shell Sort），由D.L.Shell于1959年提出，希爾排序是插入演算法的改進演算法，也是第一批時間復雜度突破 O ( n 2 ) O(n^2) O(n2) 的演算法之一，插入排序對于大型亂序的陣列排序很慢，因為它是通過交換相鄰的元素實作已排序部分后移從而實作插入的，希爾排序為了加快速度改進了插入排序，對不相鄰的子陣列進行排序，并最終用插入排序將區域有序的陣列排序，希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
- 插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率，
- 但插入排序一般來說是低效的，因為插入排序每次只能將資料移動一位，
對于新手，希爾排序比較難以理解，而且很多文章的解釋含糊不清，根本沒說到點子上，實際上希爾排序的思想非常簡單，那就是：在對整個陣列進行插入排序前，先大致將其排幾次序，大致排序的方法是先將整個陣列中距離比較遠的個個數進行兩兩交換排序，把小數放到前面，比如對于一個長度為16的陣列，可以先對相距為13的數兩兩排序，然后縮小距離，對相距為4的數兩兩排序，最后對相鄰的兩個數（相距為1）進行排序，大家必須明確，希爾排序無論排了幾次序，最后必須來一次相鄰距離為1的排序（也就是3中使用的基本插入排序），至于在這之前的相距為13和相距為4的排序完全是為最后一次的插入排序服務，也可以說相距為13的排序是使得相距為4的排序更加容易，相距為4的排序使得相距為1的排序更加容易， 在進行基本插入排序之前，先在比較大的距離上對陣列進行幾次排序，這就是希爾排序的核心所在，希爾排序能提高排序效率的根本原因也就無非是在基本插入排序之前進行了幾次長間隔的大致排序，而這么做可以提高插入排序效率的基本依據就是：插入排序對于比較有序的陣列有更高的排序效率，
希爾排序的方法是給定一個有序序列
H
H
H ，
H
H
H的值在1到陣列長度之間，比如對于長度為16的陣列，可以選擇：
H
=
[
1
,
4
,
13
]
H=[1,4,13]
H=[1,4,13]
也可以選擇
H
=
[
1
,
3
,
7
,
15
]
H=[1,3,7,15]
H=[1,3,7,15]
注意其中
H
H
H 必須以 1 結尾，因為1代表最后一次的插入排序，如果
H
=
[
1
]
H=[1]
H=[1]，則希爾排序就退化為基本的插入排序，原則上
H
H
H 的取值是不固定的，但是一般情況下，為了程式的統一起見，
H
H
H 往往是一個按一定規律產生的遞增間隔的有序序列，并且一般情況下
H
H
H 并不會再程式開始之前算好，而是在回圈的程序中計算其元素值
h
h
h 作為排序間隔（有的書也叫做增量或者排序增量），下面給出希爾排序程式，
4.2 代碼實作
在上面解釋希爾排序的時候，我們在長間隔排序的時候采用的方法是兩兩交換，先給出這種希爾排序的程式：
//sort4_1:希爾排序
//長間隔兩兩交換方式
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> array={14,13,9,8,1,2,6,4,12,7,11,16,5,10,3,15};
int n=array.size();
int h=1;
int inc_fac=3; //Increment Factor 間隔調節因子
while (h<n/inc_fac) h=inc_fac*h+1;
int time=0; //元素交換次數
while(h>=1)
{
for(int i=h;i<n;i++)
{
for(int j=i;j>=h && array[j]<array[j-h];j-=h)
{
int temp=array[j];
array[j]=array[j-h];
array[j-h]=temp;
time++;
}
}
h=h/inc_fac;
}
//列印排序后的陣列
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
cout<<"元素交換次數:"<<time;
return 0;
}
上面代碼中的 inc_fac是一個排序間隔因子，可以調節排序間隔：
當 inc_fac=3 的時候，排序間隔為：
[
1
,
4
,
13
]
[1,4,13]
[1,4,13]
排序完成時所需的元素交換次數time為 22.
當inc_fac=2 的時候，排序間隔為：
[
1
,
3
,
7
,
15
]
[1,3,7,15]
[1,3,7,15]
排序完成時所需的元素交換次數time為 30.
當inc_fac=4的時候，排序間隔為：
[
1
,
6
]
[1,6]
[1,6]
排序完成所需的元素交換次數time為 42.
因此，
h
h
h 的選取會影響演算法的效率，尤其對于長陣列，一般來說，其可能有多個
h
h
h 的選取方式可以使得演算法的效率達到相似的水平，當
h
h
h 很大的時候，我們就能將元素移動到很遠的地方，為實作更小的
h
h
h 有序創造方便，
實際上，上面的交換方式只是一種希爾排序的實作方式，其示意如下：
其通過間隔為
h
h
h 的元素事件交換排序達到將小數移動到前面的目的，隨著
h
h
h 的不斷減小，小的數逐漸移動到了陣列前列，
希爾排序還可以將相鄰比較遠的數分組，然后分別采用插入排序，如下圖所示：
可以看到，在
h
>
1
h>1
h>1時，對比交換排序的方式，插入排序是將分組后的長間隔陣列整體排序，而交換排序只是隨相距為
h
h
h 的兩個數進行了交換排序，因此在
h
=
1
h=1
h=1 之前，采用插入排序得到的中間陣列是更有序的，但是，采用插入排序的方法對長間隔分組陣列進行排序的時候，需要考慮如何分組的問題，即陣列的頭部取幾個元素，陣列的尾部取幾個元素，因此采用插入排序進行長間隔分組陣列排序的時候，分組常采用偶數分組，從而使得前面取
h
/
2
h/2
h/2 個元素，后面也取
h
/
2
h/2
h/2 個元素，如可以令分組間隔為2的指數形式：
[
1
,
2
,
2
2
,
2
3
,
2
4
,
.
.
.
]
[1,2,2^2,2^3,2^4,...]
[1,2,22,23,24,...]
注意最大的分組間隔不要超過陣列的個數，實際中，由于子陣列是相互獨立的，因此多采用的兩兩交換的排序方式，即將
h
?
h-
h?子陣列中的每個元素交換到比它大的元素之前去，下面給出采用這種指數間隔的插入排序實作希爾排序的代碼：
//sort4_2:希爾排序
//指數間隔插入實作
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> array = {14, 13, 9, 8, 1, 2, 6, 4, 12, 7, 11, 16, 5, 10, 3, 15};
int n = array.size();
int temp = 0;
int time = 0;
int gap = n / 2;
while (gap > 0)
{
for (int i = gap; i < n; i++)
{
temp = array[i];
int preIndex = i - gap;
while (preIndex >= 0 && array[preIndex] > temp)
{
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
time++;
}
array[preIndex + gap] = temp;
}
gap /= 2;
}
//列印排序后的陣列
for (int i = 0; i < n; i++)
{
cout << array[i] << " ";
}
cout << endl;
cout << "time: " << time;
return 0;
}
【總結】希爾排序可以提高效率的原因在于它權衡了子陣列的規模和有序性，通過在基本插入排序之前將陣列進行長間隔的多次提前排序，使得在進行最后一步間隔為1的基礎插入排序之前，得到是一個比較有序的陣列，從而使得最后一步的插入排序獲得了很高的效率，很有意思的是，到目前為止，人們依然沒有徹底弄清楚希爾排序的性能以及最優遞增序列的選擇，
4.3 演算法性能
時間復雜度：
- O ( n 1.3 ) ? O ( n 2 ) O\left( n^{1.3} \right) - O\left( n^{2} \right) O(n1.3)?O(n2)
空間復雜度：
- O ( 1 ) O(1) O(1)
5、歸并排序（詳解）
5.1 核心思想
歸并排序（Merge Sort），其最初的想法很簡單，那就是：如果要對一個大的有序陣列進行排序，則可以將其分成小的陣列然后分別對其排序，最后通過歸并的方法將排序后的小陣列歸并為大陣列，這里的歸并指的是：將兩個排序后的小陣列按照元素的大小次序依次排序，
歸并排序最吸引人的性質是，在任何情況下，對于長度為N的陣列，其排序所需的時間復雜度都不會超過
N
l
o
g
N
NlogN
NlogN，歸并排序的缺點是其空間復雜度（排序所需的額外空間）和
N
N
N 成正比，
歸并排是分治思想的典型應用（分治思想是高效排序演算法中的常用思想），在歸并演算法提出初期，人們嘗試了很多的方法希望找到一種原地的歸并排序方法，即只需要常數輔助空間的歸并方法，但是這些方法大都非常復雜，因此，實際中很少使用，實際可用的歸并演算法需要額外的非常數額外空間，歸并演算法可以分為兩種，分別是：
- 自頂向下的歸并排序
- 自底向上的歸并排序
下面分別介紹這兩種排序方法的代碼實作，
5.2 代碼實作
① 自頂向下的歸并排序
自頂向下的歸并是通過遞回實作的，即將大陣列分成兩個小陣列，兩個小陣列又可以分為兩個小陣列，其遞回順序為：
左陣列排序 —— 右陣列排序 —— 歸并
這里所謂的遞回順序指的是先遞回到最小不可分割的左陣列，遇到遞回終止條件回傳，對最小左陣列其排序后，然后對最小右陣列排序，然后將兩者合并，遞回這一程序，直到排序完成，其排序程序有些類似于二叉樹的后續遍歷，
自頂向下的歸并排序演算法如下：
//sort5_1：自頂向下的歸并排序（遞回）
#include<iostream>
#include<vector>
using namespace std;
void _merge(vector<int>& aux,vector<int>& a,int low,int mid,int high)
{
int i=low,j=mid+1;
for(int k=low;k<=high;k++) aux[k]=a[k]; //將a[low...high]復制到aux中
for(int k=low;k<=high;k++)
{
if(i>mid) a[k]=aux[j++]; //左半邊用盡（取右半邊元素）
else if(j>high) a[k]=aux[i++]; //右半邊用盡（取左半邊元素）
else if(aux[j]<aux[i]) a[k]=aux[j++]; //右半邊元素小于左半邊元素
else a[k]=aux[i++]; //右半邊元素大于左半邊元素
}
}
void _sort(vector<int>& aux,vector<int>& a,int low,int high)
{
if(high<=low) return; //遞回終止條件、
int mid=low+(high-low)/2;
_sort(aux,a,low,mid); //左陣列排序
_sort(aux,a,mid+1,high); //右陣列排序
_merge(aux,a,low,mid,high); //合并
}
int main()
{
vector<int> array={9,12,1,25,5,4,6,14,23,4,10,7,6,8,18,19,23};
int n=array.size();
vector<int> aux(n); //歸并所需輔助陣列，在類中可以將其作為私有成員
_sort(aux,array,0,n-1); //呼叫_sort()函式排序，注意這不是STL的sort()函式
//列印排序后的陣列
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
return 0;
}
將自定向下的排序方法，由于遞回的構建方式，是從左到右排序的，即先將陣列的左半邊遞回完成，然后又開始遞回排序右半邊的陣列，
② 自底向上的歸并排序
自底向上的歸并排序不是通過遞回實作的，而是先將陣列分為不可分割的最小陣列，然后兩兩歸并、再四四歸并、最后再八八歸并，一直下去，最后一次歸并的第二個陣列可能比第一個陣列要小（但是這對merge方法不是問題），直到排序完成，
自底向上的歸并排序演算法如下：
//sort5_2：自底向下的歸并排序（非遞回）
#include<iostream>
#include<vector>
#include<algorithm> //support for min()
using namespace std;
void _merge(vector<int>& aux,vector<int>& a,int low,int mid,int high)
{
int i=low,j=mid+1;
for(int k=low;k<=high;k++) aux[k]=a[k]; //將a[low...high]復制到aux中
for(int k=low;k<=high;k++)
{
if(i>mid) a[k]=aux[j++]; //左半邊用盡（取右半邊元素）
else if(j>high) a[k]=aux[i++]; //右半邊用盡（取左半邊元素）
else if(aux[j]<aux[i]) a[k]=aux[j++]; //右半邊元素小于左半邊元素
else a[k]=aux[i++]; //右半邊元素大于左半邊元素
}
}
void _sort(vector<int>& aux,vector<int>& a)
{
int N=a.size();
for(int sub_sz=1;sub_sz<N;sub_sz=sub_sz+sub_sz) //sub_sz子陣列長度
{
for(int low=0;low<N-sub_sz;low+=sub_sz+sub_sz)
{
_merge(aux,a,low,low+sub_sz-1,min(low+sub_sz+sub_sz-1,N-1));
}
}
}
int main()
{
vector<int> array={7,4,6,9,1,3,5,8,6,2};
int n=array.size();
vector<int> aux(n); //歸并所需輔助陣列，在類中可以將其作為私有成員
_sort(aux,array); //呼叫_sort()函式排序，注意這不是STL的sort()函式
//列印排序后的陣列
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
return 0;
}
自底向下的歸并排序是一種非遞回的排序，其中子陣列長度控制每次歸并的陣列長度，即：
- sub_sz=1時，從左到右，01歸并、23歸并、45歸并、67歸并…；
- sub_sz=2時，從左到右，01、23歸并、45、67歸并…
- sub_sz=4時，從左到右，0123、4567歸并…
- …
如下圖所示：
5.3 演算法性能
歸并排序演算法最重要的一點就是可以證明他在最壞的情況下時間復雜度不會超過
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)，對于歸并排序演算法：
時間復雜度：
- n l o g n nlogn nlogn
空間復雜度：
- O ( n ) O(n) O(n)
6、快速排序
快速排序（Quick Sort） 是應用最為廣泛的排序演算法，它由圖靈獎獲得者C. A. R. Hoare于1960年提出，被列為20實際十大演算法之一，快速排序簡單易懂，在大多數情況下排序效率優良，可以說是迄今為止最成功的排序演算法，無論是在C++ STL亦或是Java SDK的底層實作中均可以看到它的身影，
6.1 核心思想
快速排序的核心思想是：將待排序陣列經過一趟排序后分為兩個部分，其中左半部分小于陣列中的一個值 p p p，而有半部分大于值 p p p，我們將值 p p p 所在的位置稱為切分（ p a r t i t i o n partition partition）位置，然后再對左右兩個小陣列分別排序（可以是遞回的，也可以是非遞回的），
6.2 代碼實作
首先介紹如何將陣列排序為比
p
p
p 大和比
p
p
p 的兩部分，其實作其實很簡單，那就是：遇到比
p
p
p大的數就將其插入到
p
p
p 的右邊，遇到比
p
p
p 小的數就將其插入到
p
p
p 的左邊，
對于快速排序，如何將比
p
p
p 大的元素放到
p
p
p 的左邊、將比
p
p
p 小的元素放到
p
p
p 的右邊、以及
p
p
p 的選擇是快速排序的關鍵所在，其中
p
p
p 的選擇是一個至今仍在研究的問題，實際中，一般就都是將陣列的第一個元素作為切分元素，所以快速排序的關鍵問題就是如何將陣列以
p
p
p 為界限分為左右兩個部分，下面先給出代碼實作，然后講解其實作程序：
//sort6:快速排序
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//將陣列按切分值分為左右兩部分，并回傳切分值
int partition(vector<int>& array, int low, int high)
{
int i = low, j = high + 1;
int p = array[low];
while (1)
{
while (array[++i] < p) if (i == high) break; //a[i]>p 或 i==high 時跳出此while()回圈
while (p < array[--j]) if (j == low) break; //p>a[j] 或 j==low 時跳出此while()回圈
if (i >= j) break;
swap(array[i], array[j]);
}
swap(array[low], array[j]); //交換切分元素到正確位置
return j;
}
//排序
void sort(vector<int>& array, int low, int high)
{
if (high <= low) return; //遞回終止條件
int j = partition(array, low, high);
sort(array, low, j - 1);
sort(array, j+1, high);
}
int main()
{
vector<int> array = { 40,10,65,20,90,30,25,80,70,60 };
int low = 0;
int high = array.size() - 1;
sort(array, low, high);
//列印排序后陣列元素
for (auto val : array)
{
cout << val << " ";
}
return 0;
}
我們在上面的代碼中，遞回實作了快速排序，不過核心不是遞回，而是partition()函式，其作用是將傳入的陣列切分排序并回傳切值個sort()函式中的j，而 j-1 和 j+1 作為更小陣列的high和low又被遞回呼叫，下面說明partition()函式的作業程序：
- 從傳入陣列的頭部(low)和尾部(high)開始，令 i = l o w , j = h i g h i=low,j=high i=low,j=high，然后將傳如子陣列的第一個元素(low位置)作為切分值，即 p = a r r a y [ l o w ] ; p=array[low]; p=array[low];
- 先執行：
w
h
i
l
e
(
a
r
r
a
y
[
+
+
i
]
<
p
)
i
f
(
i
=
=
h
i
g
h
)
b
r
e
a
k
;
while (array[++i] < p) if (i == high) break;
while(array[++i]<p)if(i==high)break; 其作用是從
i
+
1
i+1
i+1開始從后向前尋找比
p
p
p大的元素，其位置為
i
i
i;
后執行： w h i l e ( p < a r r a y [ ? ? j ] ) i f ( j = = l o w ) b r e a k ; while (p < array[--j]) if (j == low) break; while(p<array[??j])if(j==low)break;其作用是從 j j j開始從前向后尋找比 p p p 小的元素，其位置為 j j j; - 將array[i]和array[j]交換，如果 i > = j i>=j i>=j 說明除了還在low位置的切分元素 p p p外，其余元素均以按要求分布，
- 最后，將位于low位置的切分元素array[0]和從左到右比 p p p 小的最后一個元素( j j j 位置處)交換，
其圖示說明如下：
另外需要說明的是，快速排序其實也是一種分治的排序演算法，它將一個陣列分為兩個陣列，將兩部分獨立地排序，快速排序和歸并排序是互補的：歸并排序將陣列分為兩個子陣列分別排序，并將有序的子陣列歸并并以將整個陣列排序；而快速排序將陣列排序的方式則是當兩個都有序時整個陣列自然也就有序了，在第一種情況中，遞回呼叫發生在處理整個陣列之前；在第二種情況中，遞回呼叫發生在處理整個陣列之后，在歸并排序中，一個陣列被分為兩半；在快速排序中，切分（ p a r t i t i o n partition partition）的位置取決于陣列的內容，
6.3 演算法性能
從統計角度，快速排序在多少情況下性能優良，可以肯定的是對于大小為
n
n
n 的陣列，上面給出的快排演算法的運行時間在
1.39
n
l
o
g
n
1.39nlogn
1.39nlogn 的某個常數因子的范圍之內，歸并排序其實也可以做到這一點，但是快速排序一般會更快，但是快速排序是不穩定的，且在切分不平衡上面給出的程式可能會極為低效，所以，后續對快排的改進大多都是對于切分方式的改進，總的來說，可以認為快速排序的性能如下：
時間復雜度：
- n l o g n nlogn nlogn
空間復雜度：
- O ( l o g n ) O(logn) O(logn)
7、堆排序（詳解）
堆的定義：堆是一棵完全二叉樹，每個結點的值都大于等于其左右孩子的結點的堆稱為大頂堆；每個結點的值都小于等于其左右孩子結點值的堆稱為小頂堆，從堆的定義可以知道，根節點一定是堆中所有結點最大（小）者，
注意：堆是完全二叉樹，既然是樹，那么想當然的我們就可以用指標實作其結構，即每個結點都需要三個指標來指到它的上下結點（父結點和兩個子節點各需要一個），但是，千萬不要忘了完全二叉樹由于其特殊的結構，其僅用一個陣列就能實作（因為其結點是層序連續的），所以我們用陣列就可以實作大頂堆，實際上，堆排序就是用原陣列不斷原地構建堆有序的完全二叉樹實作的，其不需要任何額外空間就可以達到對數世間復雜度，是一種相當相當經典的原地排序演算法，建議讀者在學習堆排序之前對二叉樹（尤其是完全二叉樹）進行充分的學習和理解，
下面給出一些完全二叉樹的定義和一些重要性質：
1、定義
對于一課具有
n
n
n 個結點的二叉樹按程式編號，如果編號
i
(
1
≤
i
≤
n
)
i(1\le i\le n)
i(1≤i≤n)的結點與同樣深度的慢二叉樹中編號為
i
i
i 的結點在二叉樹中位置完全相同，則這棵樹稱為完全二叉樹，
2、性質
① 具有
n
n
n 個結點的完全二叉樹的深度為
[
l
o
g
2
n
]
+
1
[log_2^{n}]+1
[log2n?]+1 ([ ]表示向下取整)，
② 如果對一棵有
n
n
n 個結點的完全二叉樹的結點按層序排序（從第1層到
[
l
o
g
2
n
]
+
1
[log_2^{n}]+1
[log2n?]+1 層，每層從左到右），對任一結點
i
i
i有：
- 如果 i = 1 i=1 i=1 ，則結點 i i i 是二叉樹的根；如果 i > 1 i>1 i>1，則其雙親是結點 [ i 2 ] [\frac {i}{2}] [2i?] ，
- 如果 2 i > n 2i>n 2i>n，則結點 i i i 無左孩子（對于完全二叉樹，當然也沒有右結點，因此其是一個葉子）；否則其左孩子是結點的 2 i 2i 2i，
- 如果 2 i + 1 > n 2i+1>n 2i+1>n，則結點 i i i 無右孩子；否則其右孩子是結點 2 i + 1 2i+1 2i+1，
由于堆是有序二叉堆，所以簡單點來說就是：對于堆，位置 i i i 的結點的父結點的位置為 [ i 2 ] [\frac {i}{2}] [2i?] ，兩個子節點的位置分別是 2 i 2i 2i 和 2 i + 1 2i+1 2i+1，對于堆排序，既可以用大頂堆實作，也可以用小頂堆實作，其只是在代碼上有微小的差別，基本思想是一致的，下面采用大頂堆實作堆排序，
7.1 核心思想
堆排序（Heap Sort） 的核心思想是先將待排序的序列構成一個有序堆，則堆頂的根節點就是整個序列的最大值（或者最小值），然后將最大值（最小值）（當前根節點、堆首位）移走（這里的移走實際上是將最大值與末位交換），然后將剩余的
n
?
1
n-1
n?1 個序列重新調整為一個有序堆，然后將其根節點移走（第二大值）并插入到最大值（最小值）的前面，重復這一程序，直至排序完成，
因此，堆排序的核心就是有序堆的構建，前面說過，由于堆是完全二叉樹，是層序連續的，所以且結構由陣列就可以實作，下面以大頂堆為例，說明如何將一個陣列構建成一個大頂堆，
7.2 代碼實作
假設我們要排序的原始陣列為：
2
,
6
,
3
,
1
,
7
,
4
,
9
,
5
,
8
{2,6,3,1,7,4,9,5,8}
2,6,3,1,7,4,9,5,8
則其對應的完全二叉樹如下所示：
堆排序演算法分為兩個步驟：
- 一是將原始無序陣列初始化為一個有序堆（本文以大頂堆為例）
- 二是回圈進行堆排序
為什么這兩個步驟要分開呢？原因是將原始無序陣列初始化為一個大頂堆是一個耗時的程序，而初始大頂堆建好后，則排序就變的容易的多，我們每次回圈和交換都可以將一個大元素放到陣列的后面，文字是不容易理解的，也很難清楚的描述這個程序，但是當大家充分理解后面的程式代碼后，就會很容易理解這個兩個步驟為什么要分開，也會理解對排序的精髓所在，下面先介紹如何將無序陣列初始化為一個大頂堆：
一般來說，有兩種方法可以將陣列初始化為大頂堆，一種是被稱為上浮（swim）的方法，另一種則是被稱為下沉（sink）的方法，這里我們選擇下沉的方法將無序陣列初始化為一個大頂堆 【注】 ：
【注】 堆排序由著名計算機科學家、圖靈獎得主弗洛伊德在1964年發明，是和快速排序（Quick Sort）齊名的高效排序演算法，堆排序用原地實作了對數時間復雜度的排序，它是我們已知的唯一能夠同時最優的利用空間和時間的方法，堆排序可以用大頂堆實作，也可以用小頂堆實作；可以用上浮（swim）實作堆的有序化，也可以用下沉（sink）實作，甚至可以兩者同時使用，并且上浮/下沉演算法可以用雙回圈實作，也可以用遞回方法實作，本文不可能用有限的篇幅將這些方法及其組合 一 一 實作，本文采用的是最經典的大頂堆元素下沉的方法實作無序陣列的初始化以及堆排序，不過只要理解了本文的程式，則其他程式解法也會很容易理解，所以各位朋友不必糾結于此，另外，如果有時間，本菜雞可以考慮單獨將堆排序寫一篇文章，對其進行詳細分析，大家可以關注一下，
由無序陣列構建大頂堆的核心方法是從下到上，從右到左回圈，將每個非葉子結點（比如上面的圖中就是 3—2—1— 0 結點）下沉到不能再下沉的位置，則最終得到的就是一個大頂堆，其中，假設陣列一共有 N N N 個元素，第 k （ k = 1 , 2... [ l o g 2 N ] + 1 ） k（k=1,2...[log_2{N}]+1） k（k=1,2...[log2?N]+1） 層的結點(非葉子結點)最多可能會下沉 [ l o g 2 N ] + 1 [log_2{N}]+1 [log2?N]+1 層，比如：
- 第0個結點（根節點2）會被比較3次
- 第1、2個結點（6和3）會被比較2次
- 第3個結點（結點1）會被比較1次
下沉時的原則是：如果父結點比某個孩子結點小，則將其與孩子結點的較大者交換，這是為了保證父節點的值比左右孩子結點的值都大，由原始陣列構建大頂堆的程序如下所示：
得到初始大頂堆后，排序就變的很簡單，后續程序是將堆頂元素（最大值9）和最后一個葉子結點（對應陣列最后一個元素）交換，然后將剩余的8個元素（陣列的0-7）重新調整為大頂堆，調整的程序不再需要像由原始陣列構建大頂堆一樣，需要對整個二叉樹進行重新構建，而只需要交換后的堆頂元素1下沉到不能在下沉即可（即只需要一次下沉），然后重復以上交換和下沉程序，直至陣列完全有序，其程序如下圖所示：
其中，首次由無序陣列初始化為大頂堆需要從右到左，從下到上回圈下沉所有的非葉結點，而大頂堆建好后，每次只要交換堆頂元素（當前對最大值）到新堆尾部，然后將交換后的較小的堆頂元素下沉到合適位置，即可完成堆的修復，然后重復 交換——重構大頂堆——交換 的程序，直至排序完成，完整的代碼如下：
//sort7:堆排序
//通過下沉方式實作
#include<iostream>
#include<vector>
using namespace std;
//下沉方式實作非葉結點i下沉
void sinkToAdjustHeap(vector<int>& array,int i,int n)
{
while(2*i+1<=n)
{
int j=2*i+1; //j是i的左孩子
if(j<n && array[j]<array[j+1]) j++; //如果有右孩子且右孩子比父結點i大
if(array[i]>array[j]) break; //如果結點i比其孩子的值大，跳出
else
{
swap(array[i],array[j]);
i=j;
}
}
}
//1、由無序陣列購進初始大頂堆
void buildMaxHeap(vector<int>& array,int n)
{
for(int i=(n/2-1);i>=0;i--) //依次下沉第3 2 1 0個堆元素
{
sinkToAdjustHeap(array,i,n);
}
}
int main()
{
vector<int> array={2,6,3,1,7,4,9,5,8};
int n=array.size()-1;
//1、由無序陣列構建大頂堆
buildMaxHeap(array,n);
//2、堆排序，每次回圈陣列尾部的排序陣列都會增加一個
while (n>0)
{
swap(array[0],array[n]); //交換堆頂元素和當前堆的最后一個元素
n--;
sinkToAdjustHeap(array,0,n); //重新調整堆為大頂堆
}
//列印排序后的陣列
for(int i=0;i<array.size();i++)
{
cout<<array[i]<<" ";
}
return 0;
}
至此，已經對基于非葉節點下沉方法的堆排序做了說明，堆排序比較難以理解但是非常經典，也是唯一一個能達到對數時間復雜度的原地排序演算法，雖然由于堆排序無法很好的利用快取導致現代系統中很少使用它，但是其深邃的思想仍然值得我們去解讀和鉆研，
7.3 演算法性能
堆排序是一種最壞情況下時間復雜度不會超過
2
n
l
o
g
n
2nlogn
2nlogn 的原地排序演算法，對于堆排序演算法：
時間復雜度：
- O ( n l o g n ) O(nlogn) O(nlogn)
空間復雜度：
- O ( 1 ) O(1) O(1)
上面介紹的排序方法都是比較排序，下面介紹的3中排序方法則屬于非比較排序，之所以不需要比較是因為有輔助的記號幫助其比較元素大小，
8、計數排序
計數排序（Counting Sort） 是一種比較土豪所以效率很高的排序演算法，它用大量的額外記憶體換取了很低的排序時間復雜度，計數排序一般僅僅用于整數排序，其思想和LeetCode 739 每日溫度的官方解法的思想比較類似，
8.1 核心思想
計數排序需要一個輔助陣列，輔助陣列的第
i
(
i
=
0
,
1
,
2...
[
m
a
x
(
a
r
r
a
y
)
?
m
i
n
(
a
r
r
a
y
)
]
)
i(i=0,1,2...[max(array)-min(array)])
i(i=0,1,2...[max(array)?min(array)]) 個元素的值是待排序陣列中值為
i
+
m
i
n
(
a
r
r
a
y
)
i+min(array)
i+min(array) 的元素的個數，也就是說，輔助陣列的下標和待排序陣列中元素的值是對應的，這樣，有序陣列下標是有序的，因此只需統計輔助陣列某個下標對應的值，就可以知道待排序陣列中值為
下
標
+
m
i
n
(
a
r
r
a
y
)
下標+min(array)
下標+min(array) 的元素的個數，然后根據這個個數將待排序陣列的
下
標
+
m
i
n
(
a
r
r
a
y
)
下標+min(array)
下標+min(array) 依次排列，就完成了陣列的排序，計數排序的程序如下：
8.2 代碼實作
有上面的圖示可以知道計數排序的步驟為：
- 求出待排序陣列array的最大值max和最小值min.
- 宣告一個大小為 m a x ? m i n + 1 max-min+1 max?min+1 的輔助陣列.
- 將待排序陣列從 [ m i n , m a x ] [min,max] [min,max] 映射到區間 [ 0 , m a x ? m i n ] [0,max-min] [0,max?min].
- 統計映射后的待排序陣列值為 i i i 的元素的個數，并將其個數作為輔助陣列下標為 i i i 的元素值.
- 利用輔助陣列得到排序后的陣列.
其代碼實作如下：
//sort8:計數排序
#include<iostream>
#include<vector>
#include<algorithm> //support for min() and max()
using namespace std;
int main()
{
vector<int> array={9,1,3,5,3,3,-1,8,-3,-1,5,3,7,8}; //待排序陣列
int len=array.size();
//求待排序陣列的最大值和最小值
int min_val=*min_element(array.begin(),array.end());
int max_val=*max_element(array.begin(),array.end());
//將待排序陣列映射到區間[0,max_val-min_val]
for(int i=0;i<len;i++)
{
array[i]-=min_val;
}
vector<int> bucket(max_val-min_val+1); //輔助陣列
//統計,統計后bucket包含了array的所有資訊
for(int i=0;i<len;i++)
{
bucket[array[i]]++;
}
//下標還原，完成排序
int index=0;
for(int i=0;i<bucket.size();i++)
{
int num=bucket[i];
while(num>0)
{
array[index]=i+min_val;
index++;
num--;
}
}
//列印排序后的陣列
for(int i=0;i<len;i++)
{
cout<<array[i]<<" ";
}
return 0;
}
上面的演算法還可以做一點小小的改進，那就是將映射和排序放在一起：
//sort8_1:計數排序小改進
#include<iostream>
#include<vector>
#include<algorithm> //support for min() and max()
using namespace std;
int main()
{
vector<int> array={9,1,3,5,3,3,-1,8,-3,-1,5,3,7,8}; //待排序陣列
int len=array.size();
//求待排序陣列的最大值和最小值
int min_val=*min_element(array.begin(),array.end());
int max_val=*max_element(array.begin(),array.end());
vector<int> bucket(max_val-min_val+1); //輔助陣列
//將待排序陣列映射到區間[0,max_val-min_val]，并計數
for(int i=0;i<len;i++)
{
array[i]-=min_val; //映射
bucket[array[i]]++; //計數
}
//下標還原，完成排序
int index=0;
for(int i=0;i<bucket.size();i++)
{
int num=bucket[i];
while(num>0)
{
array[index]=i+min_val;
index++;
num--;
}
}
//列印排序后的陣列
for(int i=0;i<len;i++)
{
cout<<array[i]<<" ";
}
return 0;
}
由于我們使用的是陣列這種資料結構輔助排序，使得計數排序在特殊情況如陣列中元素跨度很大如：
10000000
,
0
,
101
,
101
,
100
,
100
,
100
,
99
{10000000,0,101,101,100,100,100,99}
10000000,0,101,101,100,100,100,99
這種情況下，按照計數排序的原理，需要的輔助陣列長度為10000001，需要浪費大量的額外空間，但是對于密集的、跨度范圍小的陣列，計數排序效率極高，
8.3 演算法性能
對于計數排序，假設陣列長度為
n
n
n ，輔助陣列長度
k
=
m
a
x
?
m
i
n
+
1
k=max-min+1
k=max?min+1，則：
時間復雜度：
- O ( n + k ) O(n+k) O(n+k)
空間復雜度：
- O ( k ) O(k) O(k)
9、桶排序
9.1 核心思想
桶排序（Bucket Sort） 的核心思想是將待排序陣列劃分為數個范圍（數個桶），然后分別對每個非空桶進行排序，最后將所有的桶連接起來，桶排序其實也算一種分治思想，桶的范圍遠大，所需的額外輔助空間就越小，但是每個桶排序所用的時間就越長，對每個桶進行排序的時候，可以選擇仍一一種排序演算法（一般是用插入排序對各個桶進行排序），也可以遞回使用桶排序（遞回到1的時候回傳），
桶排序適用于元素基本均勻分布于陣列的最大最小值區內的情況，
9.2 代碼實作
我們使用鏈表來保存桶內的元素，這樣如果桶內沒有元素，則不需要占用空間，如下圖所示：
對應的代碼如下：
//sort9:桶排序
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
int main()
{
vector<int> array={9,1,3,5,3,3,-1,8,-3,-1,5,3,7,8};
int min_val=*min_element(array.begin(),array.end());
int max_val=*max_element(array.begin(),array.end());
int bucketSize=3; //桶范圍
int bucketCount=(max_val-min_val)/bucketSize+1; //桶個數
//vector<vector<int>> bucket(bucketCount,vector<int>(bucketSize)); //初始化桶
vector<list<int>> bucket(bucketCount); //初始化桶
//元素入桶
for(int i=0;i<array.size();i++)
{
int pos=(array[i]-min_val)/bucketSize; //判斷元素在哪個桶中
bucket[pos].push_back(array[i]); //入桶
}
//給各個桶中的元素排序,并將非空桶鏈接起來
int flag=0;
list<int> ans;
for(int i=0;i<bucket.size();i++)
{
if(bucket[i].size()>0)
{
++flag;
bucket[i].sort(); //給桶中的元素排序，這個演算法也可以自己寫
}
if(flag==1)
{
ans=bucket[i];
}
else
{
ans.merge(bucket[i]);
}
}
//列印排序后的元素
for(list<int>::iterator it=ans.begin();it!=ans.end();it++)
{
cout<<*it<<" ";
}
return 0;
}
說明：對于桶內的排序，為簡單起見，使用了list的sort()方法，這里也可以換成其他排序方法，包括桶內可以不用鏈表保存資料，而可以采用固定長度的陣列來統計資料，從而使得桶內又可以使用桶排序，
9.3 演算法性能
對于桶排序，設
n
n
n 為待排序陣列元素的個數，
k
k
k 為桶的個數，則
最好情況下時間復雜度：
- O ( n ) O(n) O(n)
空間復雜度：
- O ( k ) O(k) O(k)
10、基數排序
10.1 核心思想
基數排序（Radix Sort） 首先對每一個數按照最低位進行排序，然后按照下一個高位進行排序，直至排序完成，基數排序利用了桶的思想，基數排序聰明的地方在于他只用10個桶，因為任何十進制數的每一位數都在0-9之間，
10.2 代碼實作
基數排序有兩種方法，分別是：
- 從高位到低位的排序
- 從低位到高位的排序
下面給出從低位到高位的排序演算法：
//sort10:基數排序
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<cmath> //support for pow
using namespace std;
int main()
{
vector<int> array = { 39,2,4,17,1,28,29,35,37,21,52,20,65,37,23,54,50,59 };
int max_val = *max_element(array.begin(), array.end());
//求最大值的位數
int digits = 1;
while (max_val / 10 > 0)
{
++digits;
max_val /= 10;
}
//創建桶
vector<list<int>> bucket(10);
for (int i = 1; i <= digits; i++)
{
for (int j = 0; j < array.size(); j++)
{
//計算當前元素放在哪個桶
int radix = static_cast<int> (array[j]/pow(10, i - 1)) % 10;
bucket[radix].push_back(array[j]);
}
int k = 0;
for (int n = 0; n < 10; n++)
{
//每次按位排序后重新放到array中
for (auto value : bucket[n])
{
array[k++] = value;
}
//清空桶以便下一輪排序
bucket[n].clear();
}
}
//列印排序后的陣列
for (auto v : array)
{
cout << v << " ";
}
return 0;
}
10.3 演算法性能
設
n
n
n 為待排序陣列的元素個數，
k
k
k 為最大值的位數，則對于基數排序：
時間復雜度
- O ( n + k ) O(n+k) O(n+k)
空間復雜度：
- O ( m ) O(m) O(m)
其中， m = 10 m=10 m=10 是10進制數的位的范圍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282919.html
標籤：其他
上一篇：SQL Server 資料庫實驗課第十周——第七章資料庫設計總結
下一篇：【MBR病毒】實作與解決方案