第二十八篇，C++面经之手写代码（二）

第二篇以几个经典排序算法开始吧。

一、快速排序

void QuickSort(int* pArray, const int nLeft, const int nRight)
{
    if (nLeft >= nRight)
        return;
 
    int i = nLeft, j = nRight;
    int nKey = pArray[i];
 
    while (i < j)
    {
        while (i<j && pArray[j]>=nKey)
        {
            j--;
        }
        pArray[i] = pArray[j];
 
        while (i < j && pArray[i] <= nKey)
        {
            i++;
        }
        pArray[j] = pArray[i];
    }
    pArray[i] = nKey;
 
    QuickSort(pArray, nLeft, i - 1);
    QuickSort(pArray, i + 1, nRight);
}

快速排序算法要理解其分治思想，我觉得一大优点是对分治界限的选取不敏感，省去了专门找key的过程，不过也有一些对key的选取做改良的做法，可以参考看看。
选定key之后，从数据堆里把比它大的和比它小的分别扒拉出来，用“扒拉”这个接地气的词来描述，就像买土豆挑选时的动作一样，我觉得能充分体现出快排算法的精妙，你不用太精细地考虑啥时候能排完，只管找那一个个key就行，其余的水到渠成。
理解了快排的设计思想之后，背过这段代码还是相对容易的。（递归实现）

二、冒泡排序

void BubbleSort(int* pArray, const int nSize)
{
    int tmp = 0;
    for (int i = nSize-1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (pArray[j] > pArray[j + 1])
            {
                tmp = pArray[j];
                pArray[j] = pArray[j + 1];
                pArray[j + 1] = tmp;
            }
        }
    }
}

冒泡可以说比快排还要经典了，计算机专业的同学大一应该就学了吧。
双循环遍历，且为了避免不再对已冒出的元素再次排序，外层循环要逐次递减，每次冒出的元素都是本轮剩余元素中最大（最小）的。

三、插入排序

void InsertSort(int* pArray, const int nSize)
{
    int tmp = 0;
    for (int i = 1; i < nSize; i++)
    {
        int j = i;
        tmp = pArray[j];
        while (j > 0 && tmp < pArray[j - 1])
        {
            pArray[j] = pArray[j - 1];
            j--;
        }
        pArray[j] = tmp;
    }
}

也是双循环，内循环里先不用急着让新数据参与交换，比大小、已有数据移位、找到位置后，再直接放进去即可。
插入排序在对有序数据集中插入新元素排序的情景非常适用，笔者层发表过一篇论文，研究中值滤波算法中排序部分可提升的点，其中就用到了插入排序，效果良好。

四、数组查找问题

标题起的比较宽泛了，这一类的问题根据需求不同会衍生出各式各样的题干，后续应该还会写到这一类的题目，姑且都叫这个标题吧。
这一题的题干是这样的：一个数组中，有两个数据出现一次，其他数据都出现两次，找到这两个只出现一次的数据。

void Find2UniqueElements(std::vector<int>& array, int* num1, int* num2)
{
    std::map<int, int> map1;
    for (const auto& it : array)
    {
        map1[it]++;
    }
    
    bool ifNum1 = true;
    for (const auto& it : map1)
    {
        if (ifNum1 == true)
        {
            if (it.second == 1)
            {
                *num1 = it.first;
                ifNum1 = false;
            }
        }
        else
        {
            if (it.second == 1)
            {
                *num2 = it.first;
                break;
            }
        }
    }
}

这道题中输入数组可以用std::vector，后两个输入指针用来返回找到的两个数据。
思路是借用std::map数据结构，key为数组中出现的各个元素，value为响应的出现次数，照此生成std::map后，遍历map，找到两个计数为1的key即可。

五、字符串匹配算法

int KMP(std::string s, std::string t)
{
    int i = 0, j = -1;
    int slen = s.length(), tlen = t.length();
    std::vector<int> next;
    next.resize(tlen);

    while (i < tlen)
    {
        if (j == -1 || t[i] == t[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

    i = 0; j = 0;
    while (i < slen && j < tlen)
    {
        if (j == -1 || s[i] == t[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }

    if (j == tlen)
        return i - j;
    else
        return -1;
}

本来不好意思写KMP，背又背不过，理解又理解不了，但想来想去还是写一下吧，哪怕当做个记录也好，万一以后用得着。
输入s为源字符串，t为目标字符串，若匹配成功返回首字母在s中的index，若匹配不成功返回-1。