十種排序算法——C++實作

排序算法：插入排序，希爾排序，冒泡排序，歸并排序，快速排序，堆排序。

#include "iostream"
#include "vector"
using namespace std;

void swap(int &a,int &b){
    int tmp;
    tmp=a;
    a=b;
    b=tmp;
}
//插入排序
void insert_sort(vector<int> &v){
    int tmp,j;
    for (int i = 1; i < v.size(); ++i) {
        tmp=v[i];
        for (j = i; j>0 && v[j-1]>tmp; j--) {
            v[j]=v[j-1];
        }
        v[j]=tmp;

    }
}
//希爾排序
void shell_sort(vector<int> &v){
    for (int d=v.size()/2;d>0;d=d/2){
        int tmp,j;
        for (int i = d; i < v.size(); ++i) {
            tmp=v[i];
            for(j=i;j>0 && v[j-d]>v[j];j=j-d){
                v[j]=v[j-d];
            }
            v[j]=tmp;
        }
    }
}
//冒泡排序
void bubble_sort(vector<int> &v){
    for (int i = 0; i < v.size()-1; ++i) {
        int flag=0;
        for (int j = 1; j < v.size()-i; ++j) {
            if (v[j-1]>v[j]){
                swap(v[j-1],v[j]);
                flag=1;
            }
        }
        if (flag==0)
            break;
    }
}
//歸并排序  遞歸
void merge1(vector<int> &v,vector<int> &tmpv,int L,int R,int Rightend){
    int Leftend,Size;
    int t=L;
    Leftend=R-1;
    Size=Rightend-L+1;
    while (L<=Leftend && R<=Rightend){
        if (v[L]<=v[R]){
            tmpv[t++]=v[L++];
        } else{
            tmpv[t++]=v[R++];
        }
    }
    while (L<=Leftend){
        tmpv[t++]=v[L++];
    }
    while (R<=Rightend){
        tmpv[t++]=v[R++];
    }
    for (int i = 0; i < Size; ++i,Rightend--) {
        v[i]=tmpv[i];
    }
}
void msort1(vector<int> &v,vector<int> &tmpv,int L,int Rightend){
    int Center;
    if (L<Rightend){
        Center=(L+Rightend)/2;
        msort1(v,tmpv,L,Center);
        msort1(v,tmpv,Center+1,Rightend);
        merge1(v,tmpv,L,Center+1,Rightend);
    }
}
void mergesort1(vector<int> &v){
    int N=v.size();
    vector<int> tmpv(v.size());
    msort1(v,tmpv,0,N-1);
}

//歸并排序  非遞歸
void merge2(vector<int> &v,vector<int> &tmpv,int L,int R,int Rightend){
    int Leftend,Size;
    int t=L;
    Leftend=R-1;
    Size=Rightend-L+1;
    while (L<=Leftend && R<=Rightend){
        if (v[L]<=v[R]){
            tmpv[t++]=v[L++];
        } else{
            tmpv[t++]=v[R++];
        }
    }
    while (L<=Leftend){
        tmpv[t++]=v[L++];
    }
    while (R<=Rightend){
        tmpv[t++]=v[R++];
    }
}
 void msort2(vector<int> &v,vector<int> &tmpv,int N,int length){
    int i,j;
     for (int i = 0; i <=N-2*length ; i+=2*length) {
         merge2(v,tmpv,i,i+length,i+2*length-1);
     }
     if (i+length<N){
         merge2(v,tmpv,i,i+length,N-1);
     } else{
         for (j = i; j < N; ++j) {
             tmpv[j]=v[j];
         }
     }
}
void mergesort2(vector<int> &v){
    int N=v.size();
    int length=1;
    vector<int> tmpv(v.size());
    while (length<N){
        msort2(v,tmpv,N,length);
        length *=2;
        msort2(tmpv,v,N,length);
        length *=2;
    }
}

//快速排序
//求中位數
int median3(vector<int> &v,int Left,int Right){
    int Center=(Right+Left)/2;
    if (v[Left]>v[Center]){
        swap(v[Left],v[Center]);
    }
    if (v[Left]>v[Right]){
        swap(v[Left],v[Right]);
    }
    if (v[Center]>v[Right]){
        swap(v[Center],v[Right]);
    }
    swap(v[Center],v[Right-1]);
    return v[Right-1];
}
void qsort3(vector<int> &v,int Left,int Right){
    if (Left>=Right){
        return;
    }
    int pivot=median3(v,Left,Right);
    int i=Left;
    int j=Right-1;
    while (i<j){
        while (v[++i]<pivot);
        while (v[--j]>pivot);
        if (i<j){
            swap(v[i],v[j]);
        }
    }
    swap(v[i],v[Right-1]);
    qsort3(v,Left,i-1);
    qsort3(v,i+1,Right);
}

//使用最左值快速排序
/*
void qsort(vector<int>&v, int Left, int Right) {
    if (Left< Right)
    {
        int i = Left, j = Right, pivot = v[Left];
        while (i < j)
        {
            while(i < j && v[j]>= pivot) // 從右向左找第一個小于x的數
                j--;
            if(i < j)
                v[i++] = v[j];
            while(i < j && v[i]<= pivot) // 從左向右找第一個大于等于x的數
                i++;
            if(i < j)
                v[j--] = v[i];
        }
        v[i] = pivot;
        qsort(v, Left, i - 1); // 遞歸調用
        qsort(v, i + 1, Right);
    } }  */
void qsort(vector<int> &v, int low, int high){
    if (low >= high){
        return ;
    }
    int frist = low, last = high, pivot = v[low];
    while (frist < last){
        while (frist < last && v[last] >= pivot) {
            --last;
        }
        v[frist] = v[last];
        while (frist < last && v[frist] <= pivot){
            ++frist;
        }
        v[last] = v[frist];
    }         
    v[frist] = pivot;
    qsort(v, low, frist - 1);
    qsort(v, frist + 1, high);
}


void quicksort(vector<int> &v)
{
    int N=v.size();
    //qsort3(v,0,N-1);
    qsort(v,0,N-1);
}


//堆排序
void percdown(vector<int> &v,int p,int N){
    int Parent,Child;
    int tmp;
    tmp=v[p];
    for ( Parent = p; (Parent*2+1) < N; Parent=Child) {
        Child=Parent*2+1;
        if (Child!=N-1 && v[Child]<v[Child+1]){
            Child++;
        }
        if (tmp>=v[Child]){
            break;
        } else{
            v[Parent]=v[Child];
        }
    }
    v[Parent]=tmp;
}
void heapsort(vector<int> &v){
    int N=v.size();
    for (int i = N/2-1; i>=0; i--) {
        percdown(v,i,N);
    }
    for (int i = N-1; i >0 ; --i) {
        swap(v[0],v[i]);
        percdown(v,0,i);
    }
}





int main(){
    vector<int> v={5,1,3,2,0,9};

    //insert_sort(v);
    //bubble_sort(v);
    //shell_sort(v);

    //mergesort2(v);
    quicksort(v);

    //heapsort(v);

    for (int i = 0; i < v.size(); ++i) {
        cout<<v[i]<<endl;
    }




    return 0;
}