算法导论 线性时间排序 决策树模型 计数排序

比较排序；堆排序，归并排序，快速排序，插入排序等，都是元素间的相互比较，得到有序数列（这几种排序的源码可以看我之前的博客）

线性时间排序；说线性时间时间排序，我们的大脑可能已经猜想出该类排序的时间复杂度是O(n)，所以叫做线性时间排序，不错！你的大脑满满的都是逻辑。（此句转载于liao_hb）（仅对n个数进行出现次数的记录，其他是常量，本题的列子是O（3*n+k）  ->  转换   O(n)）；

决策树模型；验证比较排序的逻辑

元素个数3（n），结果（矩形）有6个，3！=6；

故决策树的叶节点数量是输入条件个数的阶乘，其中的一个叶节点是我们想要的结果，它的最长高度就是该算法的最坏的状态求高度h

n！<=2^h 

h>=log 2 n!

斯特林公式

h>=log 2 (n/e)^n=n*log 2 n/e=n*log 2 n-n*log 2e=省略低阶和常量=n*log 2 n=n*lg n ；

因此比较排序的时间在O（n*lg n）左右，排序时间与他相近的基本是优秀的比较排序算法。不考虑常数因子（低阶常量）

写到这里，计算排序走起；

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 1000
#define K 100
void happen_rand(int* p, int n);
void count_sort(int* p, int n);
int main()
{
    int array[N];
    happen_rand(array, N);
    count_sort(array, N);
    for (int i = 0; i < N; i++) {
        printf("%d\n", array[i]);
    }




    return 0;
}
void happen_rand(int* p, int n)
{
    srand();
    for (int i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

void count_sort(int* p, int n)
{
    int tmp[N], count[K];
    for (int i = 0; i < K; i++) {//count数组初始化0，记录每个原始出现的次数，初始是0；
        count[i] = 0;
    }
    for (int i = 0; i < N; i++) {//当某个元素出现后，计数+1
        count[p[i]] ++;
    }
    for (int i = 1; i <K; i++) {//count记录每个元素所在位置
        count[i] = count[i] + count[i - 1];
    }
    for (int i = 0; i < N; i++) {
        tmp[count[p[i]]-1] = p[i];//这里要-1，因为，比如该元素在第八个位置，它就放到下标是七的位置
        count[p[i]]--;位置计数-1
    }
    for (int i = 0; i < N; i++) {
        p[i] = tmp[i];//复制带原数组
    }
}