排序相关

冒泡排序

稳定 ，复杂度为n2

void mao(int a[], int n){
    int i, j;
    for(i = 0; i < n; i++){
        for(j = i; j < n; j++){
            if(a[i] < a[j]){
                swap(a[i], a[j]);
            }
        }
    }
}

插入排序

稳定，复杂度为n2

void ins(int a[], int n){
    int i, j;
    int tmp;

    for(i = 2; i <= n; i++){
        tmp = a[i];
        j = i - 1;
        while(j >= 1 && tmp < a[j]){
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = tmp;
    }

    return ;
}

希尔排序

不稳定，复杂度为nlogn

void shell(int a[], int n){

    int i, j, k, tmp;

    for(i = n/2; i >= 1; i /= 2){
        for(j = i; j <= n; j += i){
            tmp = a[j];
            k = j - i;
            while(k > 0 && a[k] > tmp){
                a[k + i] = a[k];
                k -= i;
            }
            a[k + i] = tmp;
        }
    }
    return ;
}

 

归并排序

 下标从1开始，稳定，复杂度为nlogn

int b[maxn];

void Merge(int a[], int l, int mid, int r){
    int i = l;
    int j = mid + 1;
    int k = l - 1;

    while(i <= mid && j <= r){
        if(a[i] < a[j]){
            b[++k] = a[i++];
        }
        else
            b[++k] = a[j++];
    }
    while(i <= mid) b[++k] = a[i++];
    while(j <= r) b[++k] = a[j++];
    for(i = l; i <= k; i++){
        a[i] = b[i];
    }
    return ;
}
void Mergesort(int a[], int l, int r){

    if(l == r){
        return ;
    }
    else {
    int mid = (l + r) >> 1;
    Mergesort(a, l, mid);
    Mergesort(a, mid + 1, r);
    Merge(a, l, mid, r);
    }
    return ;
}

 

快速排序

 复杂度nlogn，不稳定

void quicksort(int a[], int l, int r){

    if(l > r){
        return ;
    }
    int pos = l;
    int i = l, j = r;
    int tmp = a[l];
    while(i < j){
// 之所以是先动j，是因为如果a[l]是个最小的值，这样的话，就会徒劳的增加复杂度
        while(i < j && a[j] > tmp){
            j--;
        }
        while(i < j && a[i] <= tmp){
            i++;
        }
        if(i < j){
            swap(a[i], a[j]);
        }
    }
    a[l] = a[i];
    a[i] = tmp;
    quicksort(a, l, i - 1);
    quicksort(a, i + 1, r);

    return ;
}

 

选择排序

 复杂度 n^2，选择排序并不稳定，比如 5 8 5 2 9，第一次2和5互换，这样5 和 5 的相对位置就会变化

void select_sort(int a[], int l, int r){

    int i, j, pos;
    for(i = 1; i <= r; i++){
        pos = i;
        for(j = i + 1; j <= r; j++){
            if(a[j] < a[pos]){
                pos = j;
            }
        }
        if(pos != i){
            swap(a[pos], a[i]);
        }
    }

    return ;
}

 

堆排序

 nlogn，不稳定

void deal(int a[], int l, int r){
    int tmp = a[l];
    int i, j;
    for(i = l * 2; i <= r; i *= 2){
        i += (i + 1 <= r && a[i] > a[i + 1]);
        if(a[i] < a[l]){
            swap(a[i], a[l]);
            l = i;
        }
        else break;
    }

    return ;
}

void heap_sort(int a[], int l, int r){
    int i;
    for(i = r; i > 1; i--){
        swap(a[1], a[i]);
        deal(a, 1, i - 1);
    }
    return ;

}
int main(){
    int a[10];
    int n, i;

    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }

    for(i = n/2; i >= 1; i--){
        deal(a, i, n);
    }
    heap_sort(a, 1, n);

 

计数排序

不稳定，复杂度2*n + k， k为要排序的数的范围

map<int,int>vis;
void count_sort(int a[], int l, int r){
    int i, j;
    int flag = 1;
    vis.clear();
    int minn = inf;
    int maxx = -1;
    for(i = l; i <= r; i++){
        vis[a[i]]++;
        minn = min(minn, a[i]);
        maxx = max(maxx, a[i]);
    }
    for(i = minn; i <= maxx; i++){
        vis[i] += vis[i - 1];
    }
    for(i = r; i >= 1; i--){
        sto[vis[a[i]]] = a[i];
        vis[a[i]]--;
    }
    return ;
}

桶排序

复杂度 n + k，k为要排序的数的范围 ，不稳定

map<int,int>vis;
void ton_sort(int a[], int l, int r){
    int i, j;
    int flag = 1;
    vis.clear();
    int minn = inf;
    int maxx = -1;
    for(i = l; i <= r; i++){
        vis[a[i]]++;
        minn = min(minn, a[i]);
        maxx = max(maxx, a[i]);
    }
    int k = r;
    for(i = maxx; i >= minn; i--){
        while(vis[i]){
            vis[i]--;
            sto[k--] = i;
        }
    }
    return ;
}