前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >排序算法(二)

排序算法(二)

作者头像
多云转晴
发布2020-04-10 16:02:24
4360
发布2020-04-10 16:02:24
举报
文章被收录于专栏:webTower

归并排序

归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。提到分而治之一般就需要用到递归。

假如有两个排好序的数组:

代码语言:javascript
复制
// left 数组
[1,3,6]

// right 数组
[2,4,5]

将这两个数组放入下面的算法中:

代码语言:javascript
复制
let left = [1,3,6], right = [2,4,5];
function sort<T>(left: T[], right: T[]): T[]{
    let i = 0, j = 0;
    const result: T[] = [];
    while(i < l.length && j < r.length){
        result.push(l[i] < r[j] ? l[i ++] : r[j ++]);
    }
    return result.concat(i < l.length ? l.slice(i) : r.slice(j));
}
// 执行函数:
sort<number>(left, right);

程序会这样运算:

代码语言:javascript
复制
// 判断循环条件(满足)
1 < 2;  result = [1];   i=1; j=0;
3 > 2;  result = [1,2]; i=1; j=1;
3 < 4;  result = [1,2,3]; i=2; j=1;
6 > 4;  result = [1,2,3,4]; i=2; j=2;
6 > 5;  result = [1,2,3,4,5]; i=2; j=3;
// j = 3; 循环结束
result.concat(l.slice(2))  --> result = [1,2,3,4,5,6]。

通过上面的算法可以看到,两个排好序的数组使用 merge 函数后可以合并成一个大的排好序的数组。归并排序就是利用这样的规则构建的。那小数组又如何排序呢?当一个数组只有一个元素时,这个数组不相当于排好序了吗?当 left、right 两个数组都是长度为 1 时,将他们传入 merge 函数中可以得到正确的排序结果。而我们可以把一个大数组分解成只有单个元素的小数组,然后合并、合并,最终就合并成了一个排好序的数组了!首先我们分解数组,然后合并数组,这就像是递归中的递推与回溯。比如下面的示意图:

归并排序

实现代码:

代码语言:javascript
复制
function mergeSort<T>(array: T[]): T[]{
    var len = array.length;
    if(len > 1){
        // len 大于 1,表明数组最少有两个元素
        const middle = Math.floor(len / 2);
        // 把这个元素分裂成左右两个数组
        const left = mergeSort(array.slice(0, middle));
        const right = mergeSort(array.slice(middle, len));
        // 将这两个数组再合并成排好序的数组
        array = merge(left, right);
    }

    function merge(l: T[], r: T[]): T[]{
        let i = 0, j = 0;
        const result: T[] = [];
        // while 循环停止时,r 或 l 数组必定有一个,它们里面的元素全部 push 进了 result 中
        // l 或 r 都是已经排好序的小数组
        while(i < l.length && j < r.length){
            result.push(l[i] < r[j] ? l[i ++] : r[j ++]);
        }
        // 把剩下的元素合并到 result 数组后面(没有 push 到 result 中的元素都是值比较大的元素)
        return result.concat(i < l.length ? l.slice(i) : r.slice(j));
    }
    // 当 length > 1 时,返回的是 left 和 right 小数组
    // 执行完 merge 函数后,返回的是排序后的结果
    return array;
}

堆排序

堆排序可以参考之前的一篇消息,里面介绍了二叉堆和堆排序的内容(堆排序在文章最后)。

链接:二叉堆与堆排序

排序算法的稳定性

在百度百科上,排序算法的稳定性定义为:

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]r[j]之前,而在排序后的序列中,r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的。

这很好理解,比如我们之前的冒泡排序,两个元素相等时是不去做交换的,冒泡排序算法是稳定的。希尔排序则不是一个稳定的算法,比如下面的图片,第一个 16 最终会跑到第二个 16 的后面:

希尔排序不稳定

选择排序也不是一个稳定排序算法,例如有这么一个数组:[6,5,4,6,1,2],第一轮排序时会选择 1 与第一个 6 交换,第一个 6 本来在前面,却跑到了第二个 6 的后面。

快速排序同样也是一个非稳定排序算法。假如主元就是数组的最后一个元素,而主元的前一个元素是与它相等的元素,例如:[6,45,10,4,11,36,23,29,29],运行代码如下:

代码语言:javascript
复制
[6,45,10,4,11,36,23,29,29]

// 45 与 23 交换
[6,23,10,4,11,36,45,29,29]
// 最后 left 与 right 指针会指向 36 的位置
// 29 与 36 做交换,结果主元 29 跑到了倒数第二个元素(也是 29)的前面。

算法复杂度

算法复杂度分为时间复杂度和空间复杂度。

时间复杂度用来描述一个算法的运行时间,算法复杂度并不能准确地计算出一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。

空间复杂度是指执行这个算法所需要的内存空间(寄存器)。

这里主要说一下时间复杂度。

大 O 表示法

算法的复杂度可以用大 O 表示法表述。例如我们常见的冒泡排序的时间复杂度:O(n^2),它是怎么算出来的呢?

假设有这么一个搜索程序:

代码语言:javascript
复制
function find(array, item){
    for(let i = 0;i < array.length;i ++){
        if(array[i] === item){
            return i;
        }
    }
    return -1;
}

将包含 10 个元素的数组:[1, ..., 10] 传递给函数,假如搜索 1 这个元素,那么循环中的判断语句就会执行 1 次,如果要搜索 11 这个元素,那么循环中的判断语句就会执行 10 次(找到最后都没找到)。这个函数在最好的情况下,开销是 1,在最坏的情况下开销是 10。可以得出这个函数的时间复杂度是 O(n),n 是输入数组的大小(n 也表示为一个问题的规模)。

三种规则

大 O 表示法有三个运算规则。

  1. 用常数 1 取代运算时间中的所有加法常数;

例如下面的函数:

代码语言:javascript
复制
function fn(sum){
    sum += 10;  // {1}
    console.log(sum);   // {2}
}

当执行 fn 函数时,函数内部第一行会执行一次({1} 处),第二行也会执行一次({2}处),程序一共执行了两次,即:f(n) = 1 + 1。根据第一条规则,fn 函数的时间复杂度可以表示为 O(1)

  1. 只保留最高项;
  2. 去除最高阶的常数;

例如下面的代码:

代码语言:javascript
复制
let number = 1; // 语句执行 1 次
while(number < n){  // 语句会执行 logn 次
    number *= 2;    // 语句执行 logn 次
}

上面算法中,假如这个循环执行了 m 次,那么 2^m = n,即:m = logn(log 以 2 为底)。所以整段代码的执行次数为 1 + 2*logn,时间复杂度为 O(logn)(只保留最高项,并且去掉高阶的常数)。

又例如下面的代码:

代码语言:javascript
复制
for(let i = 0;i < n;i ++){  // 执行 n 次
    for(let j = 0;j < n;j ++){  // 执行 n^2 次
        console.log(i * j);     // 执行 n^2 次
    }
}

外层循环和内层循环都是从零到 n,外层循环执行 n 次,内层循环就执行了 n^2 次,内层循环中的语句也执行了 n^2 次。因此总共执行了 2*n^2 + n 次,时间复杂度是 O(n^2)(去掉最高阶常数、只保留最高项)

指数阶

代码语言:javascript
复制
function f(n){
    if(n == 0){
        return 1;
    }
    return f(n - 1) + f(n - 1);
}
  • n = 0,f(n) 执行 1 次;
  • n = 1,f(n)=f(0)+f(0),执行 2 次;
  • n = 2,f(n)=f(1)+f(1),执行 4 次;
  • n = 3,f(n)=f(2)+f(2),执行 8 次;

当 n 趋于无穷大时,f(n) = 2^0 + 2^1 + 2^2 +...+ 2^n = 2^(n+1) - 1。因此时间复杂度是 O(2^n)

常见的时间复杂度比较

O(n!) > O(2^n) > O(n^3) > O(n^2) > O(n*logn) > O(n) > O(logn) > O(1)

常见的时间复杂度图表

复杂度越小说明算法设计的越合理,运算时间也就越短。

冒泡排序的时间复杂度

下面是冒泡排序的代码:

代码语言:javascript
复制
function bubbleSort(array){
    var len = array.length;
    for(let i = 0;i < len;i ++){
        for(let j = 0;j < len - 1 - i;j ++){    // n*(n/2)
            if(array[j] > array[j + 1]){
                swap(array, j, j + 1);
            }
        }
    }
    return array;
}

假如 array 的长度是 n,则外层循环会被执行 n 次,而内层循环第一轮会执行 n-1 次,第二轮循环会执行 n-2 次,第 n 轮循环会执行 1 次,因此内层循环一共会执行 n*(n/2) 次。所以冒泡排序的时间复杂度是 O(n^2)

下面是常见的排序算法的时间复杂度:

排序算法复杂度

更多有关算法的学习资料可以参考 CSND 上的一篇博文,这篇博文里面使用了许多动图生动的展示了各个排序算法排序过程。

超详细十大经典排序算法总结(java 代码)[1]

数组搜索算法

在一个数组中搜索特定的元素最简单的做法就是遍历数组,没有这个元素就返回 -1,有就返回索引。

代码语言:javascript
复制
function find<T>(array: T[], item: T): number{
    for(let i = 0;i < array.length;i ++){
        if(array[i] === item)   return i;
    }
    return -1;
}

这种搜索算法是线性的(时间复杂度是 O(n))。而且它适用于没有排好序的数组。

二分查找

二分查找算法的条件是被查找的数组是排好序的。

二分查找的思路:首先查找数组中间位置的元素是不是与被查找元素相等,如果相等就返回索引值,如果不相等,就看中间元素大于被查找元素,还是小于被查找元素。

如果小于就接着查找中间元素左边的所有子元素,也是先找中间的元素与被查找元素的关系。

如果大于就接着查找中间元素右边的所有子元素,也是先找中间的元素与被查找元素的关系。

这是一个递归的过程,如果被查找的数组长度是 1,并且不等于被查找元素,则说明没找到,返回 -1(递归的出口)。

代码实现:

代码语言:javascript
复制
function binarySearch<T>(array: T[], target: T): number{
    var len = array.length;
    // 空数组就直接返回 -1
    if(!len)    return -1;
    // 有元素就调用 find 函数
    return find<T>(array, target);

    function find<T>(array: T[], target: T, low = 0, high = len - 1): number{
        // 说明 low 与 high 指向同一个元素
        if(low === high){
            return array[low] === target ? low : -1;
        }
        // 不是指向同一个元素就求中间值
        var mid = Math.floor((low + high) / 2);
        if(array[mid] > target){
            // 中间值大于目标元素,说明目标元素在数组的左半部分
            return find(array, target, low, mid - 1);
        }else if(array[mid] < target){
            // 中间值小于目标元素,说明目标元素在数组的右半部分
            return find(array, target, mid + 1, high);
        }
        // 等于目标元素,就直接返回中间索引
        return mid;
    }
}

二分查找速度很快。在最坏情况下二分查找的时间复杂度为 O(logn),每次查找数组长度都会折半(n --> n/2 --> n/2/2 --> n/2^i)。假如一个数组的长度是 8,那么在最坏的情况下只需查找 3 次就可以找到目标元素。

参考资料

[1]

超详细十大经典排序算法总结(java 代码): https://blog.csdn.net/weixin_41190227/article/details/86600821

【2】 排序算法(一):点击查看

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-04-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 WebTower 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 归并排序
  • 堆排序
  • 堆排序可以参考之前的一篇消息,里面介绍了二叉堆和堆排序的内容(堆排序在文章最后)。
  • 排序算法的稳定性
  • 算法复杂度
    • 大 O 表示法
      • 三种规则
    • 指数阶
      • 常见的时间复杂度比较
      • 冒泡排序的时间复杂度
  • 数组搜索算法
    • 二分查找
      • 参考资料
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档