4

十大排序算法串讲

 1周前 阅读数 4
以下为 快照 页面,建议前往来源网站查看,会有更好的阅读体验。
原文链接: http://www.cnblogs.com/nahz/p/14017586.html

十大排序算法串讲

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

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

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

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

冒泡排序

发明人:未知

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

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

稳定性:稳定

eq67vyi.gif!mobile

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

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)\)

稳定性:不稳定

rURbUfM.gif!mobile

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

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

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)\)

稳定性:稳定

ZBzQvaZ.gif!mobile

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

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})\)

稳定性:不稳定

Y3qYBbR.gif!mobile

堆是一颗二叉树,可以用数组来表示,大顶堆即每个节点的值都大于它的子节点。我们每一次都拿出堆的根节点,即最大值,放到数组的后端。这样当堆的大小为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})\)

稳定性:稳定

7FBRraN.gif!mobile

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

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})\)

稳定性:不稳定

zIbuUra.gif!mobile

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

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)\)

稳定性:不稳定

M7Zjie6.gif!mobile

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

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)\)

稳定性:稳定

6nEfum7.gif!mobile

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

对于如何令各个桶分别有序,可以采用递归或其他的排序算法来进行,这里就以库排序函数来演示,主要体现的是通过桶来降低数据规模的思想。假设数据范围在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)\)

稳定性:稳定

bMZRne.gif!mobile

计数排序运用了桶的思想,是非比较的排序,适用于数据量大但数据范围小的情况。需要注意的是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})\)

稳定性:稳定

ZfUNRff.gif!mobile

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

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;
    }
}

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

本文图源: visualgoalgorithm visualizer


猜你喜欢

  • 28
    • 博客园 www.cnblogs.com 1年前
    • 快照

    十大排序算法 - 不该相遇在秋天

    前言 你好,我是小赵,最近在系统的整理算法方面的知识,当你度过了新手阶段,想要成为牛逼的技术达人,算法是必须要掌握的东西,而算法中的排序,是每个程序员都绕不开的基本功,重要性就没必要多说了。 在工作之

  • 19
    • www.tuicool.com 1年前
    • 快照

    损失函数串讲

    本来是不想起这么大而空的名字的,但是今天确实特别自闭,所以想来个刺激一点标题刺激一下自己,也刺激一下别人。 时至今日,距离上一篇blog更新已经过去快九个月了,距离我在MSRA实习已经快八个月了,这么一看好像我的blog是为...

  • 4

    前言 平时很少写总结性的文章,感觉还是需要阶段性总结一些可以串在一起的知识点,所以这次写了下。因为我写的内容主要在时序、时空预测这个方向,所以主要还是把rnn,lstm,gru,convlstm,convgru以及ST-LSTM...

  • 21

    GitHub Repo:Sort Article Follow: MisterBooo · GitHub 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序

  • 31

    作者 | 不该相遇在秋天 冒泡排序 冒泡排序无疑是最为出名的排序算法之一,从序列的一端开始往另一端冒泡(你可以从左往右冒泡,也可以从右往左冒泡,看心情),依次比较相邻的两个数的大小(到底是比大还是比小也看你心情)。 图解冒泡 以 [ 8,2,5,9,7 ]

  • 173

    排序算法(Sort) 引言 我们平时对计算机中存储的数据执行的两种最常见的操作就是排序和查找,对于计算机的排序和查找的研究,自计算机诞生以来就没有停止过。如今又是大数据,云计算的时代,对数据的排序和查找的速度、效率要求更高,因此要对排序和查找的算法进...

  • 106
    • 掘金 juejin.im 3年前
    • 快照

    解读排序算法

    算法算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。 简单点说,算法就是解决问题的方法。确切来说它是相对于计算机程序的,大多数情况并不与具体某一种编程语言有关,但今天我们...

  • 85
    • 微信 mp.weixin.qq.com 3年前
    • 快照

    高级排序算法

  • 91

    小白学数据结构——四、排序算法Python(桶、计数、基数排序)

  • 75

    数据结构(十二)——排序算法一、排序简介1、排序的一般定义排序是计算机中经常进行的操作,目的在于将一组无序的数据元素调整为有序的数据元素。序列:1,20,45,5,2,12排序后:1,2,5,12,20,452、排序的数学定义3、排序的稳定性如果序列中的两个元素R[i]、...

关于极客头条


聚合每日国内外有价值,有趣的链接。

AD