十大排序算法串讲

十大排序算法串讲

各大编程语言为我们内置了sort函数用于排序，其效率要比我们自己实现的排序算法高效的多（元素为基本数据类型使用快速排序；元素为自定义数据类型使用归并排序；样本数量小使用插入排序；样本数量大先使用快速排序或归并排序削减规模，后使用插入排序），那我们为什么还要学习手写排序算法呢？

数据结构与算法是程序员的基本功，排序算法则是基本功中的基本功，我们接触到的第一个数据结构是数组，第一个算法则是冒泡排序，企业面试也热衷于考察面试者是否具备手写排序算法的能力；其次排序算法不单单是用来排序的，许多的经典问题也用到了排序算法的思想，例如TopK问题（快速排序 | 堆排序）、差值问题（桶排序）、逆序对问题（归并排序）等等。

对十大排序算法我们可以大致将其分为三种类型：①冒泡排序、选择排序、插入排序（代码简单，效率低）；②堆排序、归并排序、快速排序、希尔排序（代码复杂，效率高）；③桶排序、基数排序、计数排序（非比较的排序）。其中堆排序、归并排序、快速排序尤为重要。

本文将依次讲解十大排序算法的原理，并给出C++版本的代码实现。此外要补充的是，排序算法的稳定性并不是指其时间复杂度是不是稳定的，而是指数组中相同元素在排序前后的相对次序是否保持不变，例如在“姓名-班级-成绩”组中先按照成绩排序，接着使用稳定排序方法对班级进行排序，则在班级相同的情况下，成绩是排好序的，如果使用不稳定的排序方法对班级排序，那么在班级相同的情况下，成绩是乱序的。

冒泡排序

发明人：未知

额外空间复杂度： \(O(1)\)

时间复杂度： \(O(N^2)\)

稳定性：稳定

通过在遍历时不断交换元素，让最大的元素移动到了数组右端，下一次遍历时便不需要考虑最后一个元素，因为最后一个位置已经确定了。

void BubbleSort(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = 1; j < nums.size() - i; ++j) {
            if (nums[j] < nums[j-1]) {
                swap(nums[j], nums[j-1]);
            }
        }
    }
}

考虑传入一个有序数组，上面的代码就显得有些蠢笨了，我们可以适当的修改使得冒泡排序在最好的情况下达到 \(O(N)\) 的时间复杂度。

void BubbleSort(vector<int>& nums) {
    bool flag = true;
    for (int i = 0; i < nums.size() && flag; ++i) {
        flag = false;
        for (int j = 1; j < nums.size() - i; ++j) {
            if (nums[j] < nums[j-1]) {
                flag = true;
                swap(nums[j], nums[j-1]);
            }
        }
    }
}

再考虑数组 2,3,4,5,1 ，虽然数组是基本有序的，但是flag并没有发挥它的作用，于是冒泡排序有了进一步的改进，称之为鸡尾酒排序，或双向冒泡排序。

void BubbleSort(vector<int>& nums) {
    int l = 0, r = nums.size()-1;
    bool flag = true;
    while (l < r && flag) {
        flag = false;
        for (int i = l; i <= r; ++i) {
            for (int j = l + 1; j <= r - i; ++j) {
                if (nums[j] < nums[j-1]) {
                    flag = true;
                    swap(nums[j], nums[j-1]);
                }
            }
        }
        --r;
        for (int i = r; i >= l; --i) {
            for (int j = r - 1; j >= l; --j) {
                if (nums[j] > nums[j+1]) {
                    flag = true;
                    swap(nums[j], nums[j+1]);
                }
            }
        }
        ++l;
    }
}

选择排序

发明人：未知

额外空间复杂度： \(O(1)\)

时间复杂度： \(O(N^2)\)

稳定性：不稳定

通过遍历寻找剩余元素中的最小元素，并将其移动到数组左端，下一次遍历时便不需要考虑第一个元素，因为第一个位置已经确定了。

选择排序是十大排序算法里最菜的，不仅时间复杂度高还不稳定，其实选择排序也可以双向选择，但是大可不必为了提升的那一点点性能让代码变得更加复杂还难以理解。

void SelectSort(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
        int m = i;
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] < nums[m]) {
                m = j;
            }
        }
        swap(nums[i], nums[m]);
    }
}

插入排序

发明人：Herman Hollerith

额外空间复杂度： \(O(1)\)

时间复杂度： \(O(N^2)\)

最好时间复杂度： \(O(N)\)

稳定性：稳定

对于当前元素，向前寻找合适位置插入，在遍历的过程中数组前端一直保持有序状态。

void InsertSort(vector<int>& nums) {
    for(int i = 1; i < nums.size(); ++i) {
        int j, basic = nums[i];
        for(j = i; j > 0 && nums[j-1] > basic; --j) {
            nums[j] = nums[j-1];
        }
        nums[j] = basic;
    }
}

虽然插入排序与冒泡排序、选择排序同属简单排序，但是插入排序在数据规模小或数据基本有序时是一个非常不错的选择。

在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。究其原因在于插入排序时间复杂度常数项是小于快速排序时间复杂度常数项的，设插入排序时间复杂度为 \(O(CI\times{N^2})\) ，快速排序时间复杂度为 \(O(CQ\times{N\log{N}})\) ，即当 \(CI\times{N^2} < CQ\times{N\log{N}}\) 使用插入排序会更快。

上面代码在向前寻找合适位置插入的过程中，是遍历寻找的，这里可以使用二分法优化。二分法插入排序的时间复杂度是要远低于普通插入排序的（我用这段代码AC了卡 \(O(N^2)\) 排序的 题目 ），但还没有到 \(O(N\log{N})\) 。

void InsertSort(vector<int>& nums) {
    for (auto i = nums.begin(); i != nums.end(); ++i) {
        auto j = lower_bound(nums.begin(), i, *i);
        rotate(j, i, i+1);
    }
}

堆排序

发明人：Robert W．Floyd

额外空间复杂度： \(O(1)\)

时间复杂度： \(O(N\log{N})\)

稳定性：不稳定

堆是一颗二叉树，可以用数组来表示，大顶堆即每个节点的值都大于它的子节点。我们每一次都拿出堆的根节点，即最大值，放到数组的后端。这样当堆的大小为0时，整个数组就已经升序排列完成了。

void HeapSort(vector<int>& nums) {
    // 构建大顶堆
    for (int i = 0; i < nums.size(); ++i) {
        int c = i, p = (c-1)/2;
        while (nums[c] > nums[p]) {
            swap(nums[c], nums[p]);
            c = p;
            p = (c-1)/2;
        }
    }
    int size = nums.size();
    while (size) {
        // 根节点与末节点交换
        swap(nums[0], nums[--size]);
        // 根节点下沉，使其符合大顶堆的特性
        int c = 0, l = 2*c+1;
        while (l < size) {
            int r = l + 1;
            int g = r < size && nums[l] < nums[r] ? r : l;
            if (nums[c] >= nums[g]) {
                break;
            } else {
                swap(nums[c], nums[g]);
                c = g;
                l = 2*c+1;
            }
        }
    }
}

归并排序

发明人：John von Neumann

额外空间复杂度： \(O(N)\)

时间复杂度： \(O(N\log{N})\)

稳定性：稳定

将数组划分为两部分，令其分别有序，再将两部分合并，使整段区间有序。

void MergeSort(vector<int>& nums, int l, int r) {
    if (l >= r - 1) return;
    int m = (l + r) / 2;
    MergeSort(nums, l, m);
    MergeSort(nums, m, r);
    // merge
    int i = 0, p1 = l, p2 = m;
    vector<int> help(r-l);
    while (p1 < m && p2 < r) {
        help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
    }
    while (p1 < m) {
        help[i++] = nums[p1++];
    }
    while (p2 < r) {
        help[i++] = nums[p2++];
    }
    for (int j = 0; j < r-l; ++j) {
        nums[l+j] = help[j];
    }
}

快速排序

发明人：C. A. R. Hoare

额外空间复杂度： \(O(\log{N})\)

时间复杂度： \(O(N\log{N})\)

稳定性：不稳定

将数组划分为三部分，左边全部小于某个值，中间全部等于某个元素值，右边全部大于某个元素值。接着递归划分左右部分。

void QuickSort(vector<int>& nums, int l, int r) {
    if (l >= r-1) return;
    int basic = nums[l];
    // 计算断点m, n
    int i = l, m = l, n = r;
    while (i < n) {
        if (nums[i] < basic) {
            swap(nums[i++], nums[m++]);
        } else if(nums[i] > basic) {
            swap(nums[i], nums[--n]);
        } else {
            ++i;
        }
    }
    QuickSort(nums, l, m);
    QuickSort(nums, n, r);
}

希尔排序

发明人：Donald L. Shell

额外空间复杂度： \(O(1)\)

最坏时间复杂度： \(O(N^2)\)

最好时间复杂度： \(O(N)\)

稳定性：不稳定

每一次根据不同的步长将子序列进行排序。步长越大，子序列越短且越无序；步长越小，子序列越长且越有序。希尔排序使用插入排序法对子序列进行排序，因为无序时元素少，元素多时基本有序的特点，插入排序充分的发挥了它的优势。

void ShellSort(vector<int>& nums) {
    for (int step = nums.size() / 2; step > 0; step /= 2) {
        for (int begin = 0; begin < step; ++begin) {
            for (int i = begin + step; i < nums.size(); i += step) {
                int j, basic = nums[i];
                for (j = i; j > begin && nums[j-step] > basic; j -= step) {
                    nums[j] = nums[j-step];
                }
                nums[j] = basic;
            }
        }
    }
}

桶排序

发明人：未知

额外空间复杂度： \(O(N+K)\)

时间复杂度： \(O(N+K)\)

稳定性：稳定

与其说是一种排序算法，不如说是一种思想，基数排序和计数排序都是桶思想的实现。通过上面给出的图片不难理解，桶排序就是数据范围分割为不同段，再在各段内进行排序，最后合并到一起就是有序的序列。

对于如何令各个桶分别有序，可以采用递归或其他的排序算法来进行，这里就以库排序函数来演示，主要体现的是通过桶来降低数据规模的思想。假设数据范围在0到99，共设10个桶，每个桶的范围为10。

void BucketSort(vector<int>& nums) {
    vector<vector<int>> help(10, vector<int>(0));
    for (auto i : nums) {
        help[i/10].push_back(i);
    }
    int i = 0;
    for (auto v : help) {
        sort(v.begin(), v.end());
        for (auto j : v) {
            nums[i++] = j;
        }
    }
}

计数排序

发明人：Harold H. Seward

额外空间复杂度： \(O(N+K)\)

时间复杂度： \(O(N+K)\)

稳定性：稳定

计数排序运用了桶的思想，是非比较的排序，适用于数据量大但数据范围小的情况。需要注意的是help数组的长度。举个例子，数据范围在100-200，如果把help的大小开到200，那么有一半的空间是浪费的，因此需要对下标做一个转换。

void CountSort(vector<int>& nums) {
    int l = *min_element(nums.begin(), nums.end());
    int h = *max_element(nums.begin(), nums.end());
    int n = h - l + 1, k = 0;
    vector<vector<int>> help(n, vector<int>(0));
    for (auto i : nums) {
        help[i-l].push_back(i);
    }
    for (int i = l; i <= h; ++i) {
        if (0 == help[i-l].size()) continue;
        for (auto j : help[i-l]) {
            nums[k++] = j;
        }
    }
}

上面代码将help开成了二维数组，是为了保证排序的稳定性，还有一种巧妙地方法是使用前缀数组，免去了vector动态扩容带来的额外负担。

举个例子， nums = {7,4,3,4,7,8,7,5,6} ， help = {1,3,4,5,8,9} ，我们逆序遍历nums，对于 nums[6] == 7 这个元素，对应的 help[7-min(nums)] 就是这个7应该在排序后的数组中的位置，接着 help[7-min(nums)] 做自减运算，变成 nums[4] == 7 在排序后的数组中的位置。

void CountSort(vector<int>& nums) {
    int l = *min_element(nums.begin(), nums.end());
    int h = *max_element(nums.begin(), nums.end());
    vector<int> help(h-l+1, 0);
    vector<int> result(nums.size());
    for (auto i : nums) {
        ++help[i-l];
    }
    for (int i = 1; i < h-l+1; ++i) {
        help[i] += help[i-1];
    }
    for (auto i = nums.rbegin(); i != nums.rend(); ++i) {
        result[--help[*i-l]] = *i;
    }
    nums = result;
}

基数排序

发明人：Herman Hollerith

额外空间复杂度： \(O(N+K)\)

时间复杂度： \(O(N\times{K})\)

稳定性：稳定

基数排序运用了桶的思想，是非比较的排序，先按照最末位排序，再按照次末位排序...直到按照最高位排好序。在排序前需要先求出所有元素的最大位数。

void RadixSort(vector<int>& nums) {
    int d = 0;
    for (auto i : nums) {
        int c = 1;
        while (i /= 10) ++c;
        d = max(c, d);
    }
    for (int k = 0; k < d; ++k) {
        vector<vector<int>> help(10, vector<int>(0));
        for (auto i : nums) {
            int j = 0, n = i;
            for (int t = 0; t <= k; ++t) {
                j = n % 10;
                n /= 10;
            }
            help[j].push_back(i);
        }
        int j = 0;
        for (auto v : help) {
            for (auto i : v) {
                nums[j++] = i;
            }
        }
    }
}

与计数排序类似，基数排序也可以通过前缀数组进行优化，但是和计数排序相比，因为要计算第i位上的数字，代码会更复杂一点。

void RadixSort(vector<int>& nums) {
    int d = 0;
    for (auto i : nums) {
        int c = 1;
        while (i /= 10) ++c;
        d = max(c, d);
    }
    for (int k = 0; k < d; ++k) {
        vector<int> help(10);
        vector<int> result(nums.size());
        for (auto i : nums) {
            int j = 0, n = i;
            for (int t = 0; t <= k; ++t) {
                j = n % 10;
                n /= 10;
            }
            ++help[j];
        }
        for (int i = 1; i < 10; ++i) {
            help[i] += help[i-1];
        }
        for (auto i = nums.rbegin(); i != nums.rend(); ++i) {
            int j = 0, n = *i;
            for (int t = 0; t <= k; ++t) {
                j = n % 10;
                n /= 10;
            }
            result[--help[j]] = *i;
        }
        nums = result;
    }
}

总结一下，十大排序算法中，堆排序、归并排序、快速排序需要完全理解并掌握，其中涉及了堆数据结构、分治和递归思想。桶排序、计数排序、基数排序的适用范围有限，主要是去掌握它的思想。

本文图源： visualgo ， algorithm visualizer