查找和排序

• 查找相对而言较为简单，不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找
• 能够信手拈来写出完整正确的二分查找代码
• 哈希表和二叉排序树查找的重点在于考查对应的数据结构而不是算法。
• 经常要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。强烈建议应聘者在准备面试的时候，一定要对各种排序算法的特点烂熟于胸，能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。
• 要求应聘者写出快速排序的代码

实现快速排序算法的关键在于先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边：

int Partition(int data[], int length, int start, int end)
{
    if(data == NULL || length <= 0 || start < 0 || end >= length)
        throw new std::exception("invalid parameters");
    int index = RandomInRange(start, end);    /* 从数组中随机获取一个数 */
    Swap(&data[index], &data[end]);            //swap交换
    int small = start - 1;
    for(index = start; index < end; ++index){
        if(data[index] < data[end]){
            ++small;
            if(small != index)
                Swap(&data[index], &data[small]);
        }
    }
    ++samll;
    Swap(&data[small], &data[end]);
    return small;
}

• 函数 Partition 除了可以用在快速排序算法中，还可以用来实现在长度为n的数组中查找第k大的数字。

用递归的思路分别对每次选中的数字的左右两边排序

void QuickSort(int data[], int length, int start, int end)
{
    if(start == end)
        return;
    int index = Partition(data, length, start, end);
    if(index > start)
        QuickSort(data, length, start, index-1);
    if(index < end)
        QuickSort(data, length, index+1, end);
}

快速排序虽然总体的平均效率是最好的，但也不是任何时候都是最优的算法。比如数组本身已经排好序了，而每一轮排序的时候都是以最后一个数字作为比较的标准，此时快速排序的效率只有O（n2）。因此在这种场合快速排序就不是最优的算法。

面试官：请实现一个排序算法，要求时间效率O（n）。
应聘者：对什么数字进行排序，有多少个数字？
面试官：我们想对公司所有员工的年龄排序。我们公司总共有几万名员工。
应聘者：也就是说数字的大小是在一个较小的范围之内的，对吧？
面试官：嗯，是的。
应聘者：可以使用辅助空间吗？
面试官：看你用多少辅助内存。只允许使用常量大小辅助空间，不得超过 O（n）。

void SortAges(int ages[], int length)
{
     if(ages == NUL || length <= 0)
         return;
    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)
            throw new std::exception("age out of range");
        ++timesOfAge[age];
    }
    int index = 0;
    for(int i=0; i<=ouldestAge; ++i)
    {
        for(int j=0; j<timesOfAge[i]; ++j)
        {
            ages[index] = i;
            ++index;
        }
    }
}