其实排序挺重要的

排序算法

1 桶排序

#include <stdio.h>

int main()
{
    int a[14] = {61,91,23,87,98,61,91,23,87,32,54,85,10,80};

    int tong[100] = {};

    for(int i = 0; i < 14; i++){
        printf("%d  ",a[i]);
    }

    printf("\n=========\n");

    for(int i = 0; i < 14; i++){
        tong[a[i]]++;
    }

    for(int i = 0; i < 100; i++){
        if(tong[i] != 0){
            for(int j = 0; j < tong[i]; j++){
                printf("%d  ",i);
            }
            
        }
    }

    return 0;
}

2 冒泡排序

• 每趟只能将一个数归位， $n$ 个数，需要 $n-1$ 趟。复杂度 $O(N^2)$

• 用冒泡法将学生的成绩排序

冒泡

#include <stdio.h>

struct student{
    char name[10];
    int score;
};

int main()
{
    struct student a[5];
    
    for(int i = 0; i<5; i++){
        scanf("%s %d",&a[i].name,&a[i].score);
    }

    for(int i = 0; i<5; i++){
        printf("%s's score is %d\n",a[i].name,a[i].score);
    }

    for(int i = 1; i<5; i++){
        for(int j = 1; j<=5-i; j++){
            if(a[j-1].score<a[j].score){
                struct student temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }

    printf("============\n");

    for(int i = 0; i<5; i++){
        printf("%s's score is %d\n",a[i].name,a[i].score);
    }


    return 0;
}

3 快速排序

最差的时候是 $O(N^2)$，平均是 $O(NlogN)$。

快排 递归

#include <stdio.h>

int a[10] = {61,91,23,87,98,32,54,85,10,80};

void quick(int left, int right){ // 0,9
    if (left > right){
        return;
    }

    int temp = a[left]; // 作为基准
    int i = left;
    int j = right;

    while(i<j){
        while (i<j && a[j]>= temp){
            j--;
        }
        if(i<j){
            a[i] = a[j];
            i ++;
        }

        while(i<j && a[i]<= temp){
            i++;
        }
        if(i<j){
            a[j] = a[i];
            j--;
        }
    }

    // 基准归位
    a[i] = temp;

    quick(left,i-1);
    quick(i+1,right);
}

int main()
{
    for(int i = 0; i < 10; i++){
        printf("%d  ",a[i]);
    }

    printf("\n=========\n");

    quick(0,9);

    for(int i = 0; i < 10; i++){
        printf("%d  ",a[i]);
    }

    return 0;
}