手寫三大排序（快排，歸并，堆排序）

歸并排序(Merge_Sort)

首當其沖的是歸并排序，我認為這個演算法是除了O(n^2)那些垃圾的排序演算法（冒泡，插入，選擇）之外同樣好理解的，學習成本最低，而且復雜度明顯降低的，

個人認為歸并排序就兩個步驟：遞回分治（recrusive）+子段合并（merge）

背景：

6個月前就學習了這種演算法，今天再來寫一遍，第一次學都會有些困惑，不過多看幾遍就OK了！不加任何注釋，我認為我寫的代碼已經勉強可以規范了，不需要注釋，多看幾遍代碼肯定懂，看不懂就再看億遍！

語言規范：

類C語言：cpp最好在外部定義，java寫到類中即可，其他語言個人認為不適合寫演算法（NOIP和ACM你看哪個不是用的C+STL/C++）

先看代碼：

int a[100001]={0},t[100001]={0};
void _merge(int l,int mid,int r){

int l1=l,r1=mid,l2=mid+1,r2=r;

int t_l=l,t_r=l;

while(l1<=r1&&l2<=r2){

if(a[l1]<a[l2]){

t[t_l++]=a[l1++];

}else{

t[t_l++]=a[l2++];

}

}

while(l1<=r1){

t[t_l++]=a[l1++];

}

while(l2<=r2){

t[t_l++]=a[l2++];

}

while(l<=r){

a[l++]=t[t_r++];

}

}
void _div(int l,int r){

if(l>=r) return;

int mid=(r-l)/2+l;

_div(l,mid);

_div(mid+1,r);

_merge(l,mid,r);

}

關于復雜度

歸并的復雜度比較確定，無論資料規模，無論元素大小，時間和空間都是唯一確定的

空間復雜度O(n),時間O(n*logn)

對于這種排序，在合并的時候要利用一個新表來存取被合并的兩段到一段中去，然后在復制到原表，要不然你可以用一個陣列試一試，肯定會錯位的，對于這種淺比較排序，每個元素e的永久位置并不極大的依賴于比較，而是暫時依賴的（不像那些深比較排序：冒泡，選擇，這些深比較排序可以用swap(a,b)），等到這個元素所在的段被另外的大段合并時，這個元素e非常不可能在原來的位置，所以這是一種不穩定的排序

快速排序(Quick_Sort）

我的看法和做法：

這種排序我也沒看出他快在哪？反正人家就是快，追求運氣二字，不過，這種演算法最壞的復雜度是O（n^2），平均也是O（n*logn）的，空間人家是 O(1)，比歸并省空間，不過還要說說他這個運氣是怎么回事？他這個哨兵模式的排序方法看的就是基準數字的選擇，你這個基準數字選擇的好，排序就快，但是對于這個基準數字的選擇問題？是個玄學問題，我一般用C的種子亂數解決，播下隨著time不同的種子，每次的數字不同，只要下標index在[1,n]中，資料中任取一個亂數a[index]就可；您要嫌麻煩，直接取最中間的數字a[(1+n)/2]也沒事

srand(time(NULL));
int index=rand()%(n-1+1)+1;

上代碼：

這個代碼是某谷上某位dalao寫的，因為自己寫的太過于難懂晦澀（垃圾），所以...,可以看到這位dalao寫的非常的短，極度清晰...對于這樣的代碼，我愿稱之為：藝術；對于他原稱為：詩人，曾有大犇說過：好的代碼像一首詩，而不是演算紙.

void _swap(int *a,int *b){
    int t=*a;*a=*b,*b=t;
}
void quick_sort(int l,int r){

int i=l,j=r,pivot=a[(l+j)/2];

do{

while(a[i]<pivot) i++;

while(a[j]>pivot) j--;

if(i<=j) _swap(a+i,a+j),i++,j--;

}while(i<=j);

if(l<j) quick_sort(l,j);

if(i<r) quick_sort(i,r);

}

堆排序(Heap_Sort）

• 在時間和空間上，這是一種優秀的演算法，時間：O（n*logn），沒有最壞情況，空間 O(1)
• 然而這其實已經不是一種專門的演算法了，是一種持久化可維護的資料結構
• 堆呢，分大根堆和小根堆；其實STL 的優先級佇列（priority_queue）就是這種結構并且可以用這種比較器來定義堆的創建方法

greater<int>();

所以，我自己手寫個小根堆，將所有的資料以此填入堆中，全部填充完后，在一個一個地出隊輸出即可，不得不說這個堆的手寫還是蠻有難度的，要考慮陣列下標越界和浮動情況

代碼：

int n,a[1000001]={0},l=0;
int q_read(){

int x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

return x*f;

}
void _swap(int * a,int * b){

int t=a;a=b,b=t;

}
void out_put(){

for(int i=0;i<l;i++){

printf("%d ",a[i]);

}puts("");

}

void init_heap(){

n=q_read(),l=n;

for(int i=0;i<n;i++){

a[i]=q_read();

}

for(int i=(n-2)/2;i>=0;i--){

int index=i;

//printf("%s %d","change index ",i);

while(index<n-1&&2index+1<=n-1){

int t_i=2index+1;

if(2index+2<=n-1){

if(a[t_i]>a[2index+2]){

t_i=2index+2;

}

if(a[t_i]<a[index]){

_swap(a+t_i,a+index);

//printf(" %s %d %d ","swap",t_i,index);

}

index=t_i;

//這個位置是有問題的 因為不能因為一個順序正確就break了 應該繼續浮動

}else{

if(a[2index+1]<a[index]){

_swap(a+2index+1,a+index);

//printf(" %s %d %d ","swap",2index+1,index);

}

index=t_i;

}

}

//puts("");

//out_put();

}

}
void _add(int x){
}
int _delete(){

//index from 0~l-1

int first=a[0],last=a[l-1];

int index=0,t_i=0;

while(index<l&&2index+1<l-1){

t_i=2index+1;

if(2index+2<=l-1){

if(a[2index+2]<a[t_i]){

t_i=2*index+2;

}

}

a[index]=a[t_i];

index=t_i;

}

a[index]=last;

l--;

//out_put();

return first;

}

說明：

• 這個堆排序，還算比較好理解，但是實作起來比較復雜，你要注意下標越界和上浮溢位關系的錯位問題，而且每個人的實作方式略有不同，（請原諒我這驚奇的碼風），謝謝！！！
• _add()方法沒有實作，你可以自己試著實作，因為在初始化堆的時候已經建好了結構，所以添加不會很難
• 如果實在不理解上浮程序，你可以把我注釋過的代碼寫上，然后debug跟蹤元素e的上浮程序

DESC:

• 可以看到這種資料結構的底層只是一個一維陣列，但需要隨資料量變長，然而對于確定的資料量來講，也不需要變長了；
• 對于資料結構上來說，他沒有任何的空間上的浪費：堆以每個元素的下標index來組織資料，時間呢？也沒有：他以樹形化的層次關系向上浮動資料
• 堆又叫優先級佇列，顧名思義，是在排隊的時候有優先級，那么根據我的經驗來講：他的任何元素在任何元素出隊之后整個的樹形結構和資料位置都會發生很大的改變
• 形象的比喻是這樣：我們在食堂買飯，這個打飯的大媽有個親戚，這個親戚在長長的隊伍后面，這個親戚不愿插隊還想快點吃飯，于是只要他一到食堂，食堂大媽就叫他的名字，他就走出去（出隊）打飯
• 這種自己寫的堆，最好陣列下標index從零開始，不然會出很多麻煩
• 樹形結構初始化時從index=（n-1）/2開始，因為從這個元素開始有兒子，左兒子index* 2+1,右兒子index* 2+2
• 所以他可算作是：一種非常抽象化的樹形結構，

標籤：C++

上一篇：C/C++編程知識：網路編程之 Https 詳細分析，超詳細知識點！

下一篇：學習第38天