数据结构里面的各种排序算法

各种排序算法的复杂度：

部分算法实现代码：

#include<cstdio>
#include<cstdlib>
#include <iostream>
using namespace std;
typedef int ElementType;

void swap(int &a,int &b){
    int num=a;
    a=b;
    b=num;
}

/*void Bubble_Sort(ElementType a[],const int N){
     for (int i=N-1;i>=0;i--){
        int tag=0;
        for(int j=0;j<i;j++){
          if(a[j]>a[j+1]){
            swap(a[j],a[j+1]);
            tag++;
          }
        }
        if(tag==0) break;
     }
}//冒泡排序*/

/*int ScanforMin(ElementType a[],int start,int last){
    int minNum=0x7FFFFFFF,position;
    for(int i=start;i<=last;i++){
        if(a[i]<minNum){
            minNum=a[i];
            position=i;
        }
    }
    return position;
}//找出最小的位置

void Select_Sort(ElementType a[],const int N){
    int MinPosition;
    for(int i=0;i<N-1;i++){
        MinPosition=ScanforMin(a,i,N-1);
        swap(a[i],a[MinPosition]);
    }
}//选择排序*/

/*void Insertation_Sort(ElementType a[],const int N){
    int j;
    for(int i=1;i<N;i++){
        int tmp=a[i];
        for(j=i;j>0&&tmp<a[j-1];j--)
            a[j]=a[j-1];
        a[j]=tmp;
    }
}//插入排序*/

/*void Shell_Sort(ElementType a[],const int N){
    int j;
    for(int D=N/2;D>0;D/=2){
        for(int i=D;i<N;i++){//插入排序，跨度为D
             int tmp=a[i];
             for(j=i;j>=D&&tmp<a[j-D];j-=D)
                a[j]=a[j-D];
             a[j]=tmp;
        }
    }
}//希尔排序*/

/*ElementType middin(ElementType a[],int left,int right){
    int mid=(left+right)/2;
    if(left>mid) swap(left,mid);
    if(left>right) swap(left,right);
    if(mid>right) swap(mid,right);
    swap(a[mid],a[right-1]);
    return a[right-1];
}//寻找中间值
int cutoff=3;
void QuickSort(ElementType a[],int left,int right){
    if(left-right>=cutoff){
        int poit=middin(a,left,right);//第一个对照的数字
        int i=left;
        int j=right;
        for(;;){
            for(;++i<poit;){}
            for(;--j>poit;){}
            if(i<j)swap(a[i],a[j]);
            else break;//以及完成
        }
        swap(a[i],a[right-1]);
        QuickSort(a,left,i-1);
        QuickSort(a,i,right+1);
    }
    else
        Insertation_Sort(a,right-left+1);//插入排序
}
void Quick_Sort(ElementType a[],const int N){
    QuickSort(a,0,N-1);
}//快速排序的封装函数*/

void Merge(ElementType a[],ElementType tmpa[],int l,int r,int rightend){
    int leftend=r-1;
    int tmp=l;
    int numlength=rightend-l+1;//元素的个数
    while(l<=leftend&&r<=rightend){
        if(a[l]>a[r]) a[tmp++]=a[r++];
        else a[tmp++]=a[l++];
    }
    while(l<=leftend){//右边的为空
        a[tmp++]=a[l++];
    }
    while(r<=rightend){
        a[tmp++]=a[r++];
    }
}//两组合并
void Merge_pass(ElementType a[],ElementType tmpa[],int N,int length){
    int i;
    for(i=0;i<=N-2*length;i+=2*length){
        Merge(a,tmpa,i,i+length,i+2*length-1);
    }
    if(i+length<N){
        Merge(a,tmpa,i,i+length,N-1);
    }
    else{
        for(int p=i;p<=N-1;p++) tmpa[p]=a[p];
    }//只剩下一个length把他直接加入
}
void Print_num(ElementType a[],const int N);
void Merge_Sort(ElementType a[],const int N){
    int length=1;
    ElementType *tmpa;
    tmpa=(ElementType*)malloc(N*sizeof(ElementType));
    if(tmpa!=NULL){
        while(length<N){
            Merge_pass(a,tmpa,N,length);
            Print_num(a,N);
            length*=2;
            Merge_pass(tmpa,a,N,length);
            Print_num(a,N);
            length*=2;
        }
        free(tmpa);//用完后清空
    }
    else cout<<"空间不足！";
}//归并排序

void Print_num(ElementType a[],const int N){
    for(int i=0;i<N;i++){
        cout<<a[i]<<"   ";
    }
    cout<<endl;
}

int main(){
    int N=11;
    ElementType a[11]={1,5,6,3,4,5,12,11,10,19,1};
    //Bubble_Sort(a,N);//冒泡排序
    //Select_Sort(a,N);//选择排序
    //Insertation_Sort(a,N);//插入排序
    //Shell_Sort(a,N);//希尔排序
    //Quick_Sort(a,N);//快速排序
    Merge_Sort(a,N);//归并排序
    Print_num(a,N);
}