IT虾米网

算法-时间复杂度为On的排序

lxf 2023年01月21日 编程语言 2019 0

问题:请实现一个排序算法,要求排序一个公司几万名员工的年龄,要求时间复杂度为O(n)。

思路:要排序的序列元素数量比较大,不适合用传统的排序方法,但问题的要求是排序员工的年龄,也就是说,每个元素都在一个很小的范围之内(1-100)。

又要求时间复杂度为O(n),但没有要求空间复杂度,所以此时我们应该想到利用一段辅助空间来帮助排序。

利用一个timesOfAge[100]的数组,每个位置存储该年龄有多少名员工,比如timesOfAge[20] = 5,表明该公司年龄为20岁的员工有5名。timesOfAge[50]=0,表明没有50岁的员工

将所有员工的年龄存入timesOfAge中后,最后在遍历一遍timesOfAge数组,忽略timesOfAge[I]=0的位置,将timesOfAge[I]!=0的位置重新放入age数组中。

void sortAges(int age[], int length) 
{ 
    int timeOfAges[101]; 
     
    for(int i = 0; i < length; ++i) 
        timeOfAges[i] = 0; 
     
    for(int i = 0; i < length; ++i) 
    { 
        timeOfAges[ age[i] ]++; 
    } 
     
    int index = 0; 
    for(int i = 0; i < 101; ++i) 
    { 
        if(timeOfAges[i] != 0) 
        { 
            for(int j = 0; j < timeOfAges[i]; ++j) 
            { 
                age[index++] = i; 
            } 
        } 
    } 
     
} 
 
 
int main(int argc, const char * argv[]) { 
     
    int age[] = {18,20,21,22,22,23,18,18,18,30,25,26,29,22}; 
    int size = sizeof(age)/sizeof(int); 
    sortAges(age, size); 
     
    for(int i = 0; i < size; ++i) 
        cout<<age[i]<<" "; 
    cout<<endl; 
         
     
        return 0; 
}


评论关闭
IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!