面试知识点详细解读之排序算法实现及效率分析

快速排序
归并排序
计数排序
堆排序

排序算法实现及效率分析

快速排序

首先快排是不稳定排序，因为它是通过交换元素来实现的。快排适用于完全乱序的序列，不适用于基本有序或基本逆序的序列，STL中对快排的优化方法：

优化一，在选择哨兵的时候使用三数取中法，即取序列第一个元素、中间元素以及最后一个元素，再取这三个元素的中位数作为哨兵，这样可以避免取到边缘值而导致每次分割不均匀的情况；
优化二，因为在递归分割序列时，序列的长度会越来越短，又因为短序列排序中插入排序效率最高，所以可以设置一个阈值，当序列长度分割到阈值时切换到插入排序，提高效率；
优化三，当序列中存在大量相同元素，或者全是相同元素时，使用快排仍然会得到最低的效率，这时可以采用聚集相等元素的方法，每次选择哨兵后，将与哨兵相同的元素放到序列中间，下次分割时中间这些值不参与分割；
优化四，当递归层数过深的时候改用堆排序，虽然第一个优化方法避免了取到边缘哨兵，但还是有可能取到较边缘的哨兵，最坏的情况会导致递归层数过深，从而降低快排效率，所以每次递归要判断递归层数，达到一定深度就改用堆排序。之所以要用堆排序，我猜想可能是因为快排和归并都是基于递归的排序，此时递归深度已经太深，肯定不能再用了，而对于较长的序列使用插入排序效率也不是太高，所以选择了堆排序。

最后，快排的时间复杂度最好情况为O(NlogN)，最坏为O(N^2)，空间复杂度最好的情况为O(logN)，因为递归时函数压栈需要空间，最坏情况为O(N)。

// 洗牌算法
void shuffle(vector<int> &nums) {
    int n = nums.size();
    for (int i = 0 ; i < n; i++) {
        int j = rand() % ((n - 1) - i + 1) + i; // 返回 [i, n - 1] 内的随机数
        swap(nums[i], nums[j]);
    }
}

/* 左闭右闭区间, 以首元素作为轴点 */

// 版本一, 数据结构视频 9.1.5 节
// int partition(vector<int> &nums, int lo, int hi)
// {
//     // 随机置乱数组
//     shuffle(nums.begin(), nums.end(), default_random_engine(time(nullptr)));
//     int pivot = nums[lo];
//     while (lo < hi)
//     {
//         while (lo < hi && (pivot <= nums[hi])) hi--;
//         nums[lo] = nums[hi];
        
//         while (lo < hi && (nums[lo] <= pivot)) lo++;
//         nums[hi] = nums[lo];
//     }
//     nums[lo] = pivot;
//     return lo;
// }

// 版本二, 算法 4 书籍
int partition(vector<int> &nums, int lo, int hi) {
    // 随机置乱数组
    shuffle(nums.begin(), nums.end(), default_random_engine(time(nullptr)));
    int i = lo; // 左闭
    int j = hi + 1; // 右开
    while(1) {
        while(nums[++i] < nums[lo]) {
            if(i == hi) {
                break;
            }
        }
        while(nums[lo] < nums[--j]) {
            if(j == lo) {
                break;
            }
        }
        if(j <= i) {
            break;
        }
        swap(nums[i], nums[j]);
    }
    swap(nums[lo], nums[j]);
    return j;
}

// 版本三, 数据结构视频 9.3.4 节
int partition(vector<int> &nums, int lo, int hi) {
    // 随机置乱数组
    shuffle(nums.begin(), nums.end(), default_random_engine(time(nullptr)));
    int i = lo;
    int j = lo;
    while(++j <= hi) {
        if(nums[j] < nums[lo]) {
            swap(nums[++i], nums[j]);
        }
    }
    swap(nums[lo], nums[i]);
    return i;
}

// 左闭右闭区间
void quickSort(vector<int> &nums, int lo, int hi) {
    if(lo >= hi) {
        return;
    }
    int pivot = partition(nums, lo, hi);
    quickSort(nums, lo, pivot - 1);
    quickSort(nums, pivot + 1, hi);
}

void quickSort(vector<int> &nums) {
    quickSort(nums, 0, nums.size() - 1);
}

归并排序（`Top-down Approach`）

// 注意以下的 vector 参数传的都是引用
// 左闭右闭区间
// [lo, mi] 和 [mi + 1, hi] 分别是有序的
void merge(vector<int> &nums, int lo, int mi, int hi) {
    // 辅助空间, 存储 [mi + 1, hi] 元素
    vector<int> helper(nums.begin() + mi + 1, nums.begin() + hi + 1);
    // 对两个数组中的元素, 依次从后向前比较
    // 从后向前放置元素, 先放较大者
    int i = mi;
    int j = helper.size() - 1;
    int k = hi;
    // 注意 i 的终止条件
    while(i >= lo && j >= 0) {
        // 注意, 这里如果是 >= 就不稳定了
        if(nums[i] > helper[j]) {
            nums[k--] = nums[i--];
        }
        else {
            nums[k--] = helper[j--];
        }
    }
    while(j >= 0) {
        nums[k--] = helper[j--];
    }
}

// 左闭右闭区间
void mergeSort(vector<int> &nums, int lo, int hi) {
    // 单元素自动有序
    if(hi - lo < 1) {
        return;
    }
    int mi = lo + (hi - lo) / 2;
    mergeSort(nums, lo, mi);
    mergeSort(nums, mi + 1, hi);
    merge(nums, lo, mi, hi);
}

// 左闭右闭区间
void mergeSort(vector<int> &nums) {
    // 排序 [0, nums.size()) 之间的元素
    mergeSort(nums, 0, nums.size() - 1);
}

归并排序（`Bottom-up Approach`）

// 左闭右闭区间
// [lo, mi] 和 [mi + 1, hi] 分别是有序的
void merge(vector<int> &nums, int lo, int mi, int hi) {
    // 辅助空间, 存储 [mi + 1, hi] 元素
    vector<int> helper(nums.begin() + mi + 1, nums.begin() + hi + 1);
    int n = helper.size();
    // 对两个数组中的元素, 依次从后向前比较
    // 从后向前放置元素, 先放较大者
    int i = mi;
    int j = n - 1;
    int k = hi;
    // 注意 i 的终止条件
    while(i >= lo && j >= 0) {
        // 注意, 这里如果是 >= 就不稳定了
        if(nums[i] > helper[j]) {
            nums[k--] = nums[i--];
        }
    	else {
            nums[k--] = helper[j--];
        }
    }
    while(j >= 0) {
        nums[k--] = helper[j--];
    }
}

void mergeSort(vector<int>& nums) {
    int sz = nums.size();
    // 中间节点相对于起点的位置是 1 个 step
    // 终点相对于起点是 2 个 step
    // step 从 1 开始直到等于数组的长度 sz 
    for(int step = 1; step <= sz; step *= 2) {
        // 注意, 这里 lo 从 0 开始直到等于 sz - 1
        for(int lo = 0; lo < sz; lo += 2 * step) {
            // 因为 merge 函数实现的原因, 都是闭区间, 而且 [lo, mi] 和 [mi + 1, hi] 分别是有序的
            // 所以这里求出的 mi 和 hi 都需要减 1
            merge(nums, lo, min(lo + step - 1, sz - 1), min(lo + 2 * step - 1, sz - 1));
        }
    }
    return nums;
}

计数排序

计数排序要求待排序的n个元素的大小在[0, k]之间，并且k与n在一个数量级上，即k = O(n)，此时使用计数排序可以把时间复杂度降到O(n)上；
计数排序不是基于比较的排序算法，它基于计数策略；
写计数排序算法时，应该把它写成稳定排序的；
计数排序还是原址排序，但需要借助额外的内存空间；

// 找出待排序的数组中最大的元素 maxVal 和最小元素 minVal
// 统计数组中每个值为 val 的元素出现的次数, 存入数组 count 的第 val - minVal 项
// 对所有的计数累加, 从 count 中的第一个元素开始, 每一项和前一项相加
// 反向填充目标数组: 将每个元素 val 放在新数组的第 count(val - minVal) 项
// 每放一个元素就将 count(val - minVal) 减去 1
void CountSort(vector<int> &nums) {
    int minVal = *min_element(nums.begin(), nums.end());
    int maxVal = *max_element(nums.begin(), nums.end());
    int valRange = maxVal - minVal;
    
    // 注意: 这个数组的大小为 valRange + 1, 用于统计 [0, valRange]范围内的元素
    vector<int> count(valRange + 1, 0);

    // 统计待排序数组中每一个元素的个数
    for(auto x : nums) {
        count[x - minVal]++;
    }
    // 此处计算待排序数组中小于等于第i个元素的个数
    for(int i = 1; i <= valRange; ++i) {
        count[i] += count[i - 1];
    }
    // 把待排序的数组放到输出数组中, 为了保持排序的稳定性, 从后向前添加元素
    vector<int> backup(nums);
    for (int i = nums.size() - 1; i >= 0; i--) {
        int index = count[backup[i] - minVal] - 1;
        nums[index] = backup[i];
        // 因为可能有重复的元素, 所以要减 1, 为下一个重复的元素计算正确的下标
        count[backup[i] - minVal]--;
    }
}

堆排序

秩为i的元素，其父节点若存在，其秩必为(i - 1) / 2；其左孩子若存在，其秩必为2 * i + 1；其右孩子若存在，其秩必为左孩子秩加1。

下滤：将首元素依次和其孩子中较大者交换。上滤：将末元素依次和其父亲交换。时间复杂度均为O(logn)。

批量建堆：可以是所有的内部节点，自右往左依次下滤（复杂度正比于所有下滤节点的高度），或者是末元素依次上滤（复杂度是正比于所有上滤节点的深度），相比之下，前者的时间复杂度为O(n)，后者时间复杂度为O(nlogn)。第一个内部节点其实就是末元素的父亲，之后的内部节点依次递减即可。

堆排序：先执行批量建堆操作，时间复杂度为O(n)，然后进行n次取最大值操作，时间复杂度为O(nlogn)。具体实现可以是建完堆后，反复进行将首元素和未排序的末元素交换，然后对首元素进行下滤的操作。总体时间复杂度为O(n) + O(nlogn) = O(nlogn)。

void sortArray(vector<int> &nums) {
    // 下滤操作, 复杂度正比于完全二叉树的高度为 log(n)
    // 参数 n 代表 [有效堆] 数组的长度, 可用于验证待下滤元素 hole 的左右孩子节点的合法性
    auto down = [&](int hole, int n) {
        // 先保存待下滤的值, hole 代表洞号
        int holeVal = nums[hole];
        // 先找到待下滤元素的左孩子
        for(int lc = 2 * hole + 1; lc < n; lc = 2 * hole + 1) {
            // 如果右子节点存在并且左子节点的值小于等于右子节点
            if(lc + 1 < n && nums[lc] <= nums[lc + 1]) {
                lc++;
            }
            // 此时, lc 指向孩子节点中较大的那一个
            // 如果待下滤的值比孩子中较大的还大, 就不需要下滤了
            if(nums[lc] <= holeVal) {
                break;
            }
            nums[hole] = nums[lc];
            // 产生新的洞号
            hole = lc;
        }
        nums[hole] = holeVal;
    };
    int n = nums.size();
    // 从第一个内部节点开始执行下滤操作, 进行建堆, 复杂度为 O(n)
    for(int i = (n - 1 - 1) / 2; i >= 0; i--) {
        down(i, n);
    }
    for(int i = n - 1; i > 0; i--) {
        // 此时最大元素是首元素
        // 首尾交换, 末元素就位
        swap(nums[i], nums[0]);
        // 将新首元素下滤
        down(0, i);
    }
}

排序算法实现及效率分析

快速排序

归并排序（Top-down Approach）

归并排序（Bottom-up Approach）

计数排序

堆排序

归并排序（`Top-down Approach`）

归并排序（`Bottom-up Approach`）