文章包括：冒泡/地精/奇偶/梳子/快速/选择/锦标赛/堆/插入/希尔/耐心/归并排序，使用C++编写

Exchange sorts

 

冒泡排序 (Bubble sort)

稳定性：稳定

时间复杂度：O(n2)

void mysort(int* a,int n){
    
    for(int i=n-1;i>0;i--){
        for(int j=0;j<i;j++){
            if(a[j]>a[j+1])swap(a[j],a[j+1]);
        }
    }
}

 

地精排序 (Gnome sort)

稳定性：稳定

时间复杂度：O(n2)

void mysort(int* a,int n) {
    int i=0;
    while(i<n-1){
        //找到第一个逆序的元素
        if(i==-1 || a[i]<=a[i+1])i++;
        //放到前面合适的位置
        else {swap(a[i],a[i+1]);i--;}
    }
}

 

奇偶排序 (Odd-Even sort)

稳定性：稳定

时间复杂度：O (n2)

void mysort(int* a,int n) {
    bool sorted = false;

    while(!sorted){
        sorted = true;
        for(int i=0;i<n-1;i+=2){
            if(a[i]>a[i+1]){sorted=false;swap(a[i],a[i+1]);}
        }
        for(int i=1;i<n-1;i+=2){
            if(a[i]>a[i+1]){sorted=false;swap(a[i],a[i+1]);}
        }
    }
}

举例：

  • 3 4 -1 0 9 6 5
  • 3 4 -1 0 6 9 5
  • 3 -1 4 0 6 5 9
  • -1 3 0 4 5 6 9
  • -1 0 3 4 5 6 9

 

梳子排序 (Comb sort)

稳定性：不稳定

时间复杂度：O (nlogn)

void mysort(int* a,int n) {

    int gap = n;
    bool swapped = true;

    while(gap>1 || swapped){
        swapped = false;
        gap = gap>1?(gap/1.25):gap;
        for(int i=0;i+gap<n;i++){
            if(a[i]>a[i+gap]){swap(a[i],a[i+gap]);swapped=true;}
        }
    }
}

 

快速排序 (Quick sort)

稳定性：不稳定

平均时间复杂度：O(nlogn)

最差时间复杂度：O(n2)

void qksort(int* a,int n)
{
    int i=0,j=n-1;
    const int s = (a[0]+a[n-1])/2;

    while(i<=j)
    {
        while(a[i]<s)i++;
        while(a[j]>s)j--;
        if(i<=j)swap(a[i++],a[j--]);
    }
    if(j>0)qksort(a,j+1);
    if(i<n-1)qksort(&a[i],n-i);
}

 

Selection sorts

 

选择排序 (Selection sort)

稳定性：不稳定

时间复杂度：O(n2)

void mysort(int* a,int n)
{
    for(int i=0;i<n-1;i++){
        int min = i;
        for(int j=i+1;j<=n-1;j++){
            if(a[j]<a[min])min=j;
        }
        swap(a[i],a[min]);
    }
}

 

锦标赛排序 (Tournament sort)

稳定性：不稳定

时间复杂度：O(nlogn)

#define INF 2147483647;
int n;int* tmp;

//返回较小数的索引
int winner(int i,int j){
    int u = i >= n ? i : tmp[i];
    int v = j >= n ? j : tmp[j];
    return tmp[u] <= tmp[v] ? u : v;
}

//右侧存初始数据，左侧存右侧数据的索引
void create_tree(const int* a){
    for(int i=0;i<n;i++) tmp[n+i]=a[i];
    for(int i=n-1;i>0;i--) tmp[i]= winner(2*i+1,2*i);
}

void recreat(){
    int i = tmp[1];
    while(i>1){
        if(i%2==0) tmp[i/2]=winner(i,i+1);
        else tmp[i/2]=winner(i,i-1);
        i/=2;
    }
}

void mysort(int* a,int num)
{
    if(num<=1)return;
    n = num;
    tmp = new int[2*n];

    create_tree(a);

    for(int i=0;i<n;i++){
        a[i]=tmp[tmp[1]];
        tmp[tmp[1]]=INF;
        recreat();
    }
    delete[] tmp;
    tmp=NULL;
}

 

堆排序 (Heap sort)

稳定性：不稳定

时间复杂度：O(nlogn)

//维护，时间复杂度O(logn),i是待维护节点
void heapify(int* tree,int n,int i){

    int lson = i * 2 + 1;
    int rson = i * 2 + 2;
    int max = i;

    if(lson < n && tree[max]<tree[lson]) max = lson;
    if(rson < n && tree[max]<tree[rson]) max = rson;
    if(max != i){
        swap(tree[max],tree[i]);
        heapify(tree,n,max);
    }
}

void heap_sort(int* arr, int n){
    //建堆，时间复杂度O(n)
    for(int i = n/2-1;i>=0;i--){
        heapify(arr,n,i);
    }

    //排序
    for(int i=n-1;i>0;i--){
        swap(arr[0],arr[i]);
        heapify(arr,i,0);
    }
}

 

Insertion sorts

 

插入排序 (Insertion sort)

稳定性：稳定

时间复杂度：O(n2)

void mysort(int* a,int n){
    
    int i,j;
    for(i=1;i<n;i++){
        if(a[i]>=a[i-1])continue;
        
        int tmp = a[i];
        for(j=i;j>0 && tmp<a[j-1];j--) a[j]=a[j-1];
        a[j] = tmp;
    }
}

 

希尔排序 (Shell sort)

稳定性：不稳定

void shell_sort(int* a,int n){
    int gap = 1;
    while(gap < n/3){
        gap = gap * 3 + 1;
    }
    int i,j;
    while(gap>=1) {
        for (i=gap;i<n;i++) {
            if(a[i]>=a[i-gap])continue;

            int tmp = a[i];
            for (j=i;j>=gap && tmp<a[j-gap];j-=gap)a[j]=a[j-gap];
            a[j] = tmp;
        }
        gap = (gap-1)/3;
    }
}

 

耐心排序 (Patience sort)

稳定性：稳定

//重载一个运算符以便于拼接数组
vector<int>& operator+=(vector<int> &a1, const vector<int>& a2){
    int j(0),k(a1.size());
    a1.resize(a1.size()+a2.size());
    for(auto i : a2) a1[k+j++]=i;
    return a1;
}

//反转数组
void reverse(vector<int> &a){
    for(int i=0;i<a.size()-i-1;i++)swap(a[i],a[a.size()-i-1]);
}

void patience_sort(vector<int> &a){
    int n = a.size();if(n<2)return;
    vector<vector<int>> pile;
    //入桶
    int pileNum(0);
    for(int i=0;i<n;i++) {
        int j(0);
        for(j=0;j<pileNum;j++)
            if(a[i]<pile[j][0]) {pile[j].push_back(a[i]);break;}
        if(j==pileNum) {pile.push_back({a[i]});pileNum++;}
    }
    //出桶
    a.clear();
    for(auto& i : pile){
        reverse(i);
        patience_sort(i);
        a+=i;
    }
}

 

Merge sorts

 

归并排序 (Merge sort)

稳定性：稳定

时间复杂度：O(nlogn)

void mgsort(int* a, int n){
    if(n<2)return;
    int mid = n/2;

    mgsort(a,mid);
    mgsort(&a[mid],n-mid);

    int i(0),j(mid),k(0); int *tmp = new int[n];
    while(i<mid && j<n) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];

    j = k-1;
    while(i<mid) a[k++] = a[i++];
    for(;j>=0;j--) a[j]=tmp[j];

    delete[] tmp; tmp = NULL;
}