题解 第三章排序与查找| #排序#

法1:

使用C语言自带的qsort写出的代码

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int main()
{
    int Num;
    scanf("%d", &Num);
    int Arr[Num];
    for (int i = 0; i < Num; i++)
        scanf("%d", &Arr[i]);
    //以上即录入了所有信息

    qsort(Arr, Num, sizeof(int), cmp);
    // https://baike.baidu.com/item/qsort/4747970?fr=aladdin

    for (int i = 0; i < Num; i++)
        printf("%d ", Arr[i]);
    printf("\n");
    return 0;
}

法2:

使用c++自带的sort算法

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int main()
{
    int Num;
    scanf("%d", &Num);
    int Arr[Num];
    for (int i = 0; i < Num; i++)
        scanf("%d", &Arr[i]);
    //以上即录入了所有信息

    qsort(Arr, Num, sizeof(int), cmp);
    // https://baike.baidu.com/item/qsort/4747970?fr=aladdin
    
    for (int i = 0; i < Num; i++)
        printf("%d ", Arr[i]);
    printf("\n");
    return 0;
}

法3:

其他人写出的各种算法

//所有基本的排序方法了，桶排序、基数排序暂不写了
#include<iostream>
using namespace std;
const int N = 110, MAX = 1e8;
int a[N];
int n;
int h[N], idx;//heap_sort用
int tmp[N];//merge_sort用
int bkt[MAX];//counting_sort用

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

void quick_sort(int l, int r){
    if(l>=r) return;
    int x = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while(i<j){
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j+1, r);
}

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

void down(int u){
    int t = u;
    if(u*2<=idx&&h[u*2]<h[t]) t = u*2;
    if(u*2+1<=idx&&h[u*2+1]<h[t]) t= u*2+1;
    if(t!=u){
        swap(h[t], h[u]);
        down(t);
    }
}
void heap_sort(){
    for(int i = 1; i <= n; i ++) h[i] = a[i-1];
    idx = n;
    for(int i = idx/2; i > 0; i --) down(i);
    for(int i = 0; i < n; i ++){
        a[i] = h[1];
        h[1] = h[idx--];
        down(1);
    }
}

void insertion_sort(){
    for(int i = 1; i < n; i ++){
        int cur_idx = a[i];
        int j;
        for(j = i-1; j >=0 && a[j]>cur_idx; j --){
            a[j+1] = a[j];
        }
        a[j+1] = cur_idx;
    }
}

void binary_insertion_sort(){
    for(int i = 1; i < n; i ++){
        int cur_idx = a[i];
        int l = 0, r = i - 1;
        while(l<r){
            int mid = (l + r + 1) / 2;
            if(a[mid]<=cur_idx) l = mid;
            else r = mid - 1;
        }
        if(a[l]>cur_idx) l = -1;
        int j;
        for(j = i - 1; j>l ;j --) a[j+1] = a[j];
        a[j+1] = cur_idx;
    }
}

void shell_sort(){
    for(int gap = n/2; gap>=1; gap /= 2){
        for(int i = gap; i < n; i ++){
            int cur_idx = a[i];
            int j;
            for(j = i - gap; j>=0 && a[j]>cur_idx; j -= gap){
                a[j+gap] = a[j];
            }
            a[j + gap] = cur_idx;
        }
    }
}

void merge_sort(int l, int r){
    if(l>=r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while(i<=mid) tmp[k++] = a[i++];
    while(j<=r) tmp[k++] = a[j++];
    for(int i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];
}

void counting_sort(){
    int max = 0;
    for(int i = 0 ; i < n; i ++){
        bkt[a[i]]++;
        if(a[i]>max) max = a[i];
    }
    int j = 0;
    for(int i = 0; i < max+1; i ++){
        while(bkt[i]){
            a[j++] = i;
            bkt[i]--;
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
//     buble_sort();
//     quick_sort(0, n - 1);
//     selection_sort();
//     heap_sort();
//     insertion_sort();
//     binary_insertion_sort();
//     shell_sort();
//    merge_sort(0, n - 1);
    counting_sort();
    for(int i = 0; i < n; i ++) printf("%d ", a[i]);
    return 0;
}