算法面试小结

1. 求一个数转化为二进制后，包含1的数量

int func(int x)
{
    int count = 0;
    while(x)
    {
        count ++;
        x = x & (x - 1);
    {
    return count;
}

2. 求平均值

int func(int x, int y)
{
    return (x & y) + ((x^y)>>1);
}

解析：x&y是取相同位与，结果是x和y相同位的和的一半；x^y是取x和y的不同位，右移相当于除以2，所以这个函数的功能是取平均值。

3. 有1千万条短信，有重复，以文本的形式保存，一行一条，有重复。请用5分钟的时间，找出重复出现最多的前10条。

• 方法一：hashTable

1. 分组，边扫描边建散列表
2. 第一次扫描，取首尾字符，中间随便两字节作为Hash Code，插入hash table，记录其地址和信息长度和重复次数；同hash code且等长即疑似相同。相同记录只加1次进hash table，将重复次数加1。
3. 第一次扫描已经记录各自的重复次数，扫描第二次，用线性时间可在O(n)级别上完成前10条寻找
4. 分组后每份中的top10必须保证各不相同，可hash保证，也可直接按hash值的大小来分类

• 方法二：排序

1. 除非群发，一般字数越少，越有可能。先从1字、2字的开始统计，找出各自top10
2. 对于字数长的，除了用hash，还可以用首尾和中间字节，可以加快查询速度，但未必准确，需要标记
3. 遍历各组的top10，寻找备选top10，遇到标记，则统计相同字数下的短信，精确找出真正的top10

• 方法三：内存映射——待深入理解

1. 可以采用内存映射文件（文件过大，可以分段映射）
2. 对每条短信的第i（i从0到70）个字母按照ASCII进行分组，就是创建树，i是树的深度，也是短信第i个字母

4. 1亿个浮点数，请找出最大的1万个

假设每个浮点数占4个字节，1亿个浮点就要占有相当大的空间。

• 阈值过滤

先读出100万个数据，找出最大的1万个，如果数据理想，那么以1万个数据里面最小的为基准，可以过滤掉1亿数据里面99%的数据
最后在剩下的100万里找出最大的1万个。

• 分块查找

100万一个块，分别找出最大的1万个，筛选出100万个
采用快速排序方法，分2堆，如果大的那个堆的个数N大于1万个，继续对大堆快排一次分成2堆，如果大堆个数N小于1万，就在小的那堆里面快排一次，找出第10000-N大的数字。递归以上过程

5. 排序

• 排序的稳定性

待排序记录相同时，经过排序后具有相同关键字的记录之间的相对次序保持不变，则是稳定的。

• 分类

内外存交换：若在排序过程中，整个文件都是放在内存中，排序时不涉及数据的内、外存交换，则称为内部排序，否则是外部排序；前者适合记录个数不多的小文件

策略：插入排序、选择排序、交换排序、归并排序、分配排序

快速排序

采用了分治法的思想

快排是一种不稳定的排序方法，平均时间复杂度为O(nlogn)，最差时间复杂度为O(n^2)

void QuickSort(SeqList R, int low, int high)
{
    int privotpos;
    if (low < high)
    {
        privotpos = Partition(R, low, high);
        QuickSort(R, low, privotpos-1);
        QuickSort(R, privotpos+1, high);
    }
}
int Partition(SeqList R, int i, int j)
{
    ReceType pivot = R[i];
    while(i < j)
    {
        while(i<j && R[j].key >= pivot.key)
            j--;
        if (i < j)
            R[i++] = R[j];
        while(i<j && R[i].key <= pivot.key)
            i ++;
        if(i<j)
            R[j--] = R[i];
    }
    R[i] = pivot;
    return i;
}

冒泡排序

扫描n-1次，每次扫描让无序区中的最“轻”气泡上升到“顶部”
若原始数据是正序的，则比较次数为n-1，移动次数为0，时间复杂度为O(n);若原始为反序，则比较次数和移动次数都达到O(n^2)；
算法的平均时间复杂度为O(n^2)
冒泡排序为就地排序，是稳定的。但性能要比快速排序要差很多。

void BubbleSort(SeqList R)
{
    int i, j;
    Boolean exchange;
    for(i=1;i<n;i++) // 1,..., n是待排序的数
    {
        exchange = FALSE;
        for(j=n-1;j>=i;j--)
        {
            if(R[j+1].key < R[j].key)
            {
                R[0] = R[j+1];
                R[j+1] = R[j];
                R[j] = R[0];
                exchange = TRUE;
            }
        }
        if(!exchange)
            return ;
    }
}

shell排序（希尔排序）

插入排序的一种，本质是一种分组插入的方法
当增量为1时，与insertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j>0以防止下标越界
执行时间依赖于增量序列，最后一个增量必须为1，应尽量避免序列中的中（尤其是相邻的值）互为倍数的情况

性能优于直接插入排序，原因如下：

• 当文件初态基本有序时，直接插入排序所需的比较和移动次数都比较少
• 当n较小时，n与n^2差别也比较小，即直接插入排序的最好时间复杂度和最坏复杂度差别不大
• 希尔排序开始增量较大，分组多，每组记录少，故各组直接插入排序较快。增量逐渐减少，各组数量虽然增多，但接近有序，所有新的一趟排序也较快
• 希尔排序是不稳定的。

void ShellPass(SeqList R, int d)
{
    for(i=d+1; i<=n;i++)
    {
        if (R[i].key < R[i-d].key){
            R[0] = R[i];
            j = i-d;
            do {
                R[j+d] = R[j];
                j = j-d;
            }while(j>0 && R[0].key<R[j].key);
            R[j+d] = R[0];
        }
    }
}
void ShellSort(SeqList R)
{
    int increment = n; //增量初值
    do {
        ShellPass(R, increment);
        increment = increment / 3 + 1;
    }while (increment > 1)
}

总结

稳定排序	时间复杂度	空间复杂度
冒泡排序	最差、平均都是O(n^2)；最好是O(n)	1
鸡尾酒排序	最差、平均都是O(n^2)；最好是O(n)	1
插入排序	最差、平均都是O(n^2)；最好是O(n)	1
归并排序	最差、平均、最好都是O(nlogn)	O(n)
桶排序	O(n)	O(k)
基数排序	O(dn) d是常数	O(n)
二叉树排序	O(nlogn)	O(n)
图书馆排序	O(nlog(n)	(1+ξ)n

不稳定的排序	时间复杂度	空间复杂度
选择排序	最差、平均都是O(n^2)	1
希尔排序	O(nlogn)	1
堆排序	最差、平均、最好都是O(nlogn)	1
快速排序	平均是O(nlogn) ；最坏都是O(n^2)	O(n)

不同条件下排序方法的选择：

1. 若n较小 (如n<50), 可采用直接插入或者直接选择排序

当规模小时，直接插入排序较好；否则，因为直接选择移动的记录数少于直接插入，应该直接选择排序为宜。

2. 若文件初始状态基本有序(指正序)，则应该选用直接插入排序、冒泡排序或者随机的快速排序为宜
3. 若n较大，应采用时间复杂度为O(nlogn)的排序方法（快排、堆排序、归并排序）

快速排序是目前基于比较的内部排序中最好的方法。当待排序的关键字随机分布时，快速排序的平均时间最短

4. 堆排序所需要的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，但和快排都是不稳定的
5. 若要求排序稳定，则可选归并排序。但不提倡从单个记录起进行两两归并，通常和直接插入排序合在一起用，先利用直接插入法求得较长的有序子文件，然后再两两归并。

6. 以下哪种结构，平均来讲获取任意一个指定值最快，为什么？

• [ ] A. 二叉排序树
• [x] B. 哈希表
• [ ] C. 栈
• [ ] D. 队列

7. 辗转相除法的时间复杂度是多少？

解析：算法的思想：gcd(a, b) = gcd(b, a mod b)，时间复杂度是O(logn)

8.字符串

8.1 怎么将整数转化为字符串数，并且不用函数itoa？

解析：整数转化为字符串，可以采用加’0’，再逆序的办法，整数加’0’就会隐形转化成char类型的数。

8.2 怎么将字符串转化成整数？

解析：字符串转化为整数，可以采用’0’再乘10累加的方法，字符串减’0’就会隐形转化成int类型的数

8.3 不使用C++/C的字符串库函数，编写函数strcpy

char *strcpy(chr *strDest, const char *strSrc)
{
    assert ((strDest != NULL) && (strSrc != NULL));
    char *address = strDest;
    while( (*strDest++ = *strSrc) != '\0' )
    NULL;
    return address;
}

8.4 strcpy能把strSrc的内容复制到strDest，为什么还要char *类型的返回值?

解析：为了实现链式表达式，返回具体的值int length=strlen(strcpy(strDest, “hello world”))