面试手撕代码

快排

// 简易版本 quick sort，面试手撕
void Quick_Sort(int *arr, int begin, int end)
{
    if (begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while (i != j)
    {
        while (arr[j] >= tmp && j > i)
            j--;
        while (arr[i] <= tmp && j > i)
            i++;
        if (j > i)
        {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i - 1);
    Quick_Sort(arr, i + 1, end);
}

归并排序

void merge(vector<int> &arr, int L, int M, int R)
{
    vector<int> help(R - L + 1, 0);
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R)
    {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M)
    {
        help[i++] = arr[p1++];
    }
    while (p2 <= R)
    {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.size(); i++)
    {
        arr[L + i] = help[i];
    }
}
void process(vector<int> &arr, int L, int R)
{
    if (L == R)
    {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}
void mergeSort(vector<int> &arr)
{
    if (arr.size() < 2)
    {
        return;
    }
    process(arr, 0, arr.size() - 1);
}

堆排序

void swap(vector<int> &arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
void heapInsert(vector<int> &arr, int index)
{
    // 停止条件：当前来到头结点或者当前节点不在比它的父节点大
    while (arr[index] > arr[(index - 1) / 2])
    {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
void heapify(vector<int> &arr, int index, int heapSize)
{
    int left = index * 2 + 1;
    while (left < heapSize)
    {
        // two children choose bigger one
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // 父和较大孩子之间，谁的值大，把下标给largest
        largest = arr[largest] > arr[index] ? largest : index;
        if (index == largest)
        {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}
void heapSort(vector<int> &arr)
{
    if (arr.size() < 2)
    {
        return;
    }
    // O(N)
    for (int i = 0; i < arr.size(); i++)
    {
        // O(logN)
        heapInsert(arr, i);
    }
    int heapSize = arr.size();
    swap(arr, 0, --heapSize);
    // O(N)
    while (heapSize > 0)
    {
        // O(logN)
        heapify(arr, 0, heapSize);
        // O(1)
        swap(arr, 0, --heapSize);
    }
}

桶排序（基数排序）

int maxbits(vector<int> &arr)
{
    int max = INT32_MIN;
    for (int i = 0; i < arr.size(); i++)
    {
        max = std::max(max, arr[i]);
    }
    int res = 0;
    while (max != 0)
    {
        res++;
        max /= 10;
    }
    return res;
}
int getDigit(int x, int d)
{
    return ((x / (int)pow(10, d - 1)) % 10);
}
// digit：这一批数中最大的值有多少十进制位
void radixSort(vector<int> &arr, int L, int R, int digit)
{
    const int radix = 10;
    int i = 0, j = 0;
    // 有多少个数准备多少个辅助空间
    vector<int> bucket(R - L + 1);
    for (int d = 1; d <= digit; d++)
    {
        // 10个空间
        // count[0] 当前位(d位)是0的数字有多少个
        // count[1] 当前位(d位)是（0和1）的数字有多少个
        // count[i] 当前位(d位)是（0~i）的数字有多少个
        vector<int> count(radix);
        for (i = L; i <= R; i++)
        {
            j = getDigit(arr[i], d);
            // 词频数组
            count[j]++;
        }
        for (i = 1; i < radix; i++)
        {
            // 前缀和数组
            count[i] = count[i] + count[i - 1];
        }
        for (i = R; i >= L; i--)
        {
            j = getDigit(arr[i], d);
            // 词频-1作为index放到临时数组bucket里面，每次区分出一个进制位的排序结果分区
            // 至于为什么要从R向L遍历，主要是为了保证排序结果的稳定性
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }
        for (i = L, j = 0; i <= R; i++, j++)
        {
            arr[i] = bucket[j];
        }
    }
}
// only for no-negative value
void radixSort(vector<int> &arr)
{
    if (arr.size() < 2)
    {
        return;
    }
    radixSort(arr, 0, arr.size() - 1, maxbits(arr));
}