对公司几万名员工按年龄排序（时间复杂度为O(N)）

素颜马尾好姑娘i 2022-05-27 09:40 158阅读 0赞

### 【0】 目录 ###

**【1】题目**  
**【2】分析**  
**【3】测试代码**  
**【4】测试结果**

### **【1】题目：** ###

**面试官：** 请实现一个排序算法，要求时间复杂度为O（N）  
**应聘者：**请问对什么数字进行排序，共有多少数字？  
**面试官：**我们想对公司所有员工按年龄排序，我们公司共有几万名员工；  
**应聘者**：也就是说数字的大小在一个较小的范围之内，对吗？  
**面试官**：是的  
**应聘者：**可以使用辅助空间吗？  
**面试官：**看你用多少内存，只允许使用常量大小的辅助空间，不得超过O(N);  
**应聘者：**好的，我知道了；，

### 【2】分析： ###

通过面试官的要求，我们可以确定的是，是要求在一个有限范围内排序，并且实现效率为O（N），那么我们可以将员工年纪设置在0~99范围内，借助一个辅助空间，可以是一个数组，用来保存从0到99岁这100个年龄出现的次数，某个年纪每出现一次，就给对应下标的空间加1，然后再根据这个数组中记录的次数，确定该年纪在原数组中相应出现多少次；

### 【3】测试实现： ###

#include<iostream>
    using namespace std;
    //=====================================算法==========================================
    int sortage(int ages[], int length)
    {
        if(ages == NULL || length <= 0)
        {
            printf("参数传递错误：ages == NULL || length <= 0\n");
                return -1;
        }
    
        const int oldestage = 99;
        int timesofage[oldestage + 1];
    
        for (int i =0 ; i<= oldestage ; ++i)
            timesofage[i] = 0;
    
        for(int i = 0; i< length; ++i )
        {
            int age = ages[i];
            if(age <= 0 ||age >oldestage )
                {
                    printf("年纪不在有效范围内\n");
                    return -1;
                  }
    
            ++timesofage[age];
        }
    
        int index = 0;
        for(int i = 0; i< oldestage ;++i )
        {
            for(int j = 0; j<timesofage[i]; ++j )
            {
                ages[index] = i;
                ++index;
            }
        }
        return 0;
    }
    //==================================测试代码=====================================
    void test()
    {
        int arr[20]={
       20,30,44,32,22,34,66,77,55,44,31,22,44,32,44,65,24,22,20, 35};
        int length = sizeof(arr)/sizeof(arr[0]);
        printf("共有%d位员工年纪待排序\n",length );
        int ret = sortage(arr,length);
        if(ret == 0)
        {
            printf("排序后：");
            for(int i = 0;i<length ; ++i )
            {
                printf("%d ",arr[i]);
            }
            printf("\n");
        }
    }
    
    int main()
    {
        test();
        return 0;
    }

### 【4】测试结果如下： ###

**这里已20位员工为例：**  
**1、ages\[20\] = \{20,30,44,32,22,34,66,77,55,44,31,22,44,32,44,65,24,22,20, 35\}**  
![这里写图片描述][70]  
**2、ages\[20\] = \{100,30,44,32,22,34,66,77,55,44,31,22,44,32,44,65,24,22,20, 35\}**  
![这里写图片描述][70 1]

**3、int ret = sortage( NULL , length);**  
![这里写图片描述][70 2]

**3、int ret = sortage( arr , 0);**  
![这里写图片描述][70 3]

[70]: /images/20220527/658e36d00ec74495a1cab406f5a59140.png
[70 1]: /images/20220527/25618b37d2e7499688b2b4344edeb13f.png
[70 2]: /images/20220527/d1ed1411ef4a4fa3a6f508688bd824f0.png
[70 3]: /images/20220527/376186c3201848609092a8cae264380e.png