JavaScript算法实现——排序

  • 时间:
  • 浏览:0
  • 来源:大发pk10_pk10IOS下载_大发pk10IOS下载

  在计算机编程中,排序算法是最常用的算法之一,本文介绍了几种常见的排序算法以及它们之间的差异和复杂度。

冒泡排序

  冒泡排序应该是最简单的排序算法了,在所有讲解计算机编程和数据特征的课程中,无一例外都不 拿冒泡排序作为开篇来讲解排序的原理。冒泡排序理解起来也很容易,但是十个 多嵌套循环遍历数组,对数组中的元素两两进行比较,意味着着前者比后者大,则交换位置(这是针对升序排序而言,意味着着是降序排序,则比较的原则是前者比后者小)。五种人来看下冒泡排序的实现:

function bubbleSort(array) {
    let length = array.length;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
}

  中间这段代码但是经典的冒泡排序算法(升序排序),只不过交换十个 多元素位置的每种五种人没有用传统的写法(传统写法时需引入十个 多临时变量,用来交换十个 多变量的值),这里使用了ES6的新功能,五种人都后能 使用五种 语法特征很方便地实现十个 多变量值的交换。来看下对应的测试结果:

let array = [];
for (let i = 5; i > 0; i--) {
    array.push(i);
}

console.log(array.toString()); // 5,4,3,2,1
bubbleSort(array);
console.log(array.toString()); // 1,2,3,4,5

   在冒泡排序中,对于内层的循环而言,每一次全部都不 把五种 轮中的最大值放满最后(相对于升序排序),它的过程是原本的:第一次内层循环,找出数组中的最大值排到数组的最后;第二次内层循环,找出数组中的次大值排到数组的倒数第二位;第三次内层循环,找出数组中的第三大值排到数组的倒数第三位......以此类推。统统,对于内层循环,五种人都后能 不不每一次都遍历到length - 1的位置,而只时需遍历到length - 1 - i的位置就都后能 了,原本都后能 减少内层循环遍历的次数。下面是改进后的冒泡排序算法:

function bubbleSortImproved(array) {
    let length = array.length;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
}

  运行测试,结果和前面的bubbleSort()土办法得到的结果是相同的。

let array = [];
for (let i = 5; i > 0; i--) {
    array.push(i);
}

console.log(array.toString()); // 5,4,3,2,1
bubbleSortImproved(array);
console.log(array.toString()); // 1,2,3,4,5

  在实际应用中,五种人何必 推荐使用冒泡排序算法,尽管它是最直观的用来讲解排序过程的算法。冒泡排序算法的复杂度为O(n2)

选着 排序

  选着 排序与冒泡排序很类式,它也时需十个 多嵌套的循环来遍历数组,只不过在每一次循环中要找出最小的元素(这是针对升序排序而言,意味着着是降序排序,则时需找出最大的元素)。第一次遍历找出最小的元素排在第一位,第二次遍历找出次小的元素排在第二位,以此类推。五种人来看下选着 排序的的实现:

function selectionSort(array) {
    let length = array.length;
    let min;

    for (let i = 0; i < length - 1; i++) {
        min = i;
        for (let j = i; j < length; j++) {
            if (array[min] > array[j]) {
                min = j;
            }
        }

        if (i !== min) {
            [array[i], array[min]] = [array[min], array[i]];
        }
    }
}

  中间这段代码是升序选着 排序,它的执行过程是原本的,首先将第十个 多元素作为最小元素min,五种在内层循环中遍历数组的每十个 多元素,意味着着有元素的值比min小,就将该元素的值赋值给min。内层遍历完成后,意味着着数组的第十个 多元素和min不相同,则将它们交换一下位置。五种再将第十个 元素作为最小元素min,重复前面的过程。直到数组的每十个 多元素都比较完毕。下面是测试结果:

let array = [];
for (let i = 5; i > 0; i--) {
    array.push(i);
}

console.log(array.toString()); // 5,4,3,2,1
selectionSort(array);
console.log(array.toString()); // 1,2,3,4,5

  选着 排序算法的复杂度与冒泡排序一样,也是O(n2)

插入排序

  插入排序与前十个 多排序算法的思路不太一样,为了便于理解,五种人以[ 5, 4, 3, 2, 1 ]五种 数组为例,用下图来说明插入排序的整个执行过程:

  在插入排序中,对数组的遍历是从第十个 元素后后后后始于的,tmp是个临时变量,用来保存当前位置的元素。五种从当前位置后后后后始于,取前十个 多位置的元素与tmp进行比较,意味着着值大于tmp(针对升序排序而言),则将五种 元素的值插入到五种 位置中,最后将tmp放满数组的第十个 多位置(索引号为0)。反复执行五种 过程,直到数组元素遍历完毕。下面是插入排序算法的实现:

function insertionSort(array) {
    let length = array.length;
    let j, tmp;

    for (let i = 1; i < length; i++) {
        j = i;
        tmp = array[i];
        while (j > 0 && array[j - 1] > tmp) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = tmp;
    }
}

  对应的测试结果:

let array = [];
for (let i = 5; i > 0; i--) {
    array.push(i);
}

console.log(array.toString()); // 5,4,3,2,1
insertionSort(array);
console.log(array.toString()); // 1,2,3,4,5

  插入排序比冒泡排序和选着 排序算法的性能要好。

归并排序

  归并排序比前面介绍的几种排序算法性能全部都不 好,它的复杂度为O(nlogn)

  归并排序的基本思路是通过递归调用将给定的数组不断分割成最小的两每种(每一每种只十个 多元素),对这两每种进行排序,五种向上合并成十个 多大数组。五种人还是以[ 5, 4, 3, 2, 1 ]五种 数组为例,来看下归并排序的整个执行过程:

  首没有将数组分成十个 多每种,对于非偶数长度的数组,让人自行决定将多的分到左边意味着着右边。五种按照五种 土办法进行递归,直到数组的左右两每种都只十个 多元素。对这两每种进行排序,递归向上返回的过程中将其组成和十个 多全部的数组。下面是归并排序的算法的实现:

const merge = (left, right) => {
    let i = 0;
    let j = 0;
    const result = [];

    // 通过五种

while循环将left和right中较小的每种放满result中
    while (i < left.length && j < right.length) {
        if (left[i] < right[i]) result.push(left[i++]);
        else result.push(right[j++]);
    }

    // 五种将组合left或right中的剩余每种
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
};

function mergeSort(array) {
    let length = array.length;
    if (length > 1) {
        const middle = Math.floor(length / 2); // 找出array的中间位置
        const left = mergeSort(array.slice(0, middle)); // 递归找出最小left
        const right = mergeSort(array.slice(middle, length)); // 递归找出最小right
        array = merge(left, right); // 将left和right进行排序
    }
    return array;
}

  主函数mergeSort()通过递归调用五种得到left和right的最小单元,这里五种人使用Math.floor(length / 2)将数组中较少的每种放满left中,将数组中较多的每种放满right中,让人使用Math.ceil(length / 2)实现相反的效果。五种调用merge()函数对这两每种进行排序与合并。注意在merge()函数中,while循环每种的作用是将left和right中较小的每种存入result数组(针对升序排序而言),句子result.concat(i < left.length ? left.slice(i) : right.slice(j))的作用则是将left和right中剩余的每种加到result数组中。考虑到递归调用,但是最小每种意味着着排好序了,没有在递归返回的过程中只时需把left和right这两每种的顺序组合正确就能完成对整个数组的排序。

  对应的测试结果:

let array = [];
for (let i = 5; i > 0; i--) {
    array.push(i);
}

console.log(array.toString()); // 5,4,3,2,1
console.log(mergeSort(array).toString()); // 1,2,3,4,5

快速排序

  快速排序的复杂度也是O(nlogn),但它的性能要优于其它排序算法。快速排序与归并排序类式,其基本思路也是将十个 多大数组分为较小的数组,但它不像归并排序一样将它们分割开。快速排序算法复杂,大致过程为:

  1. 从给定的数组中选着 十个 多参考元素。参考元素都后能 是任意元素,也都后能 是数组的第十个 多元素,五种人这里选着 中间位置的元素(意味着着数组长度为偶数,则向下取十个 多位置),原本在大多数请况下都后能 提高下行速率 。
  2. 创建十个 多指针,十个 多指向数组的最左边,十个 多指向数组的最右边。移动左指针直到找到比参考元素大的元素,移动右指针直到找到比参考元素小的元素,五种交换左右指针对应的元素。重复五种 过程,直到左指针超过右指针(即左指针的索引号大于右指针的索引号)。通过五种 操作,比参考元素小的元素都排在参考元素完后 ,比参考元素大的元素都排在参考元素完后 (针对升序排序而言)。
  3. 以参考元素为分隔点,对左右十个 多较小的数组重复上述过程,直到整个数组完成排序。

  下面是快速排序算法的实现:

const partition = (array, left, right) => {
    const pivot = array[Math.floor((right + left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            [array[i], array[j]] = [array[j], array[i]];
            i++;
            j--;
        }
    }
    return i;
};

const quick = (array, left, right) => {
    let length = array.length;
    let index;
    if (length > 1) {
        index = partition(array, left, right);
        if (left < index - 1) {
            quick(array, left, index - 1);
        }
        if (index < right) {
            quick(array, index, right);
        }
    }
    return array;
};

function quickSort(array) {
    return quick(array, 0, array.length - 1);
}

  假定数组为[ 3, 5, 1, 6, 4, 7, 2 ],按照中间的代码逻辑,整个排序的过程如下图所示:

  下面是测试结果:

let array = [3, 5, 1, 6, 4, 7, 2];
console.log(array.toString()); // 3,5,1,6,4,7,2
console.log(quickSort(array).toString()); // 1,2,3,4,5,6,7

  快速排序算法理解起来五种难度,都后能 按照中间给出的示意图逐步推导一遍,以帮助理解整个算法的实现原理。

堆排序

  在计算机科学中,堆是五种特殊的数据特征,它通常用树来表示数组。堆有以下特点:

  • 堆是一棵全部二叉树
  • 子节点的值不大于父节点的值(最大堆),意味着着子节点的值不小于父节点的值(最小堆)
  • 根节点的索引号为0
  • 子节点的索引为父节点索引 × 2 + 1
  • 右子节点的索引为父节点索引 × 2 + 2

  堆排序是五种比较高效的排序算法。

  在堆排序中,五种人何必 时需将数组元素插入到堆中,而但是通过交换来形成堆,以数组[ 3, 5, 1, 6, 4, 7, 2 ]为例,五种人用下图来表示其初始请况:

  没有,咋样将其转加带十个 多符合标准的堆特征呢?先来看看堆排序算法的实现:

const heapify = (array, heapSize, index) => {
    let largest = index;
    const left = index * 2 + 1;
    const right = index * 2 + 2;
    if (left < heapSize && array[left] > array[index]) {
        largest = left;
    }
    if (right < heapSize && array[right] > array[largest]) {
        largest = right;
    }
    if (largest !== index) {
        [array[index], array[largest]] = [array[largest], array[index]];
        heapify(array, heapSize, largest);
    }
};

const buildHeap = (array) => {
    let heapSize = array.length;
    for (let i = heapSize; i >= 0; i--) {
        heapify(array, heapSize, i);
    }
};

function heapSort(array) {
    let heapSize = array.length;
    buildHeap(array);

    while (heapSize > 1) {
        heapSize--;
        [array[0], array[heapSize]] = [array[heapSize], array[0]];
        heapify(array, heapSize, 0);
    }

    return array;
}

  函数buildHeap()将给定的数组转加带堆(按最大堆出理 )。下面是将数组[ 3, 5, 1, 6, 4, 7, 2 ]转加带堆的过程示意图:

  在函数buildHeap()中,五种人从数组的尾部后后后后始于遍历去查看每个节点有无符合堆的特点。在遍历的过程中,五种人发现当索引号为6、5、4、3时,其左右子节点的索引大小都超出了数组的长度,这意味着着它们全部都不 叶子节点。没有五种人真正要做的但是从索引号为2的节点后后后后始于。虽然 从五种 点考虑,结合五种人利用全部二叉树来表示数组的特征,都后能 对buildHeap()函数进行优化,将其中的for循环修改为下面原本,以加带对子节点的操作。

for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
    heapify(array, heapSize, i);
}

  从索引2后后后后始于,五种人查看它的左右子节点的值有无大于买车人,意味着着是,则将其中最大的那个值与买车人交换,五种向下递归查找有无还时需对子节点继续进行操作。索引2出理 完完后 再出理 索引1,五种是索引0,最终转换出来的堆如图中的4所示。让人发现,每一次堆转换完成完后 ,排在数组第十个 多位置的但是堆的根节点,也但是数组的最大元素。根据五种 特点,五种人都后能 很方便地对堆进行排序,其过程是:

  • 将数组的第十个 多元素和最后十个 多元素交换
  • 减少数组的长度,从索引0后后后后始于重新转换堆

  直到整个过程后后后后始于。对应的示意图如下:

  堆排序的核心每种在于咋样将数组转加带堆,也但是中间代码中buildHeap()和heapify()函数每种。

  同样给出堆排序的测试结果:

let array = [3, 5, 1, 6, 4, 7, 2];
console.log(array.toString()); // 3,5,1,6,4,7,2
console.log(heapSort(array).toString()); // 1,2,3,4,5,6,7

有关算法复杂度

  中间五种人在介绍各种排序算法的完后 ,提到了算法的复杂度,算法复杂度用大O表示法,它是用大O表示的十个 多函数,如:

  • O(1):常数
  • O(log(n)):对数
  • O(log(n) c):对数多项式
  • O(n):线性
  • O(n2):二次
  • O(nc):多项式
  • O(cn):指数

  五种人咋样理解大O表示法呢?看十个 多例子:

function increment(num) {
    return ++num;
}

  对于函数increment(),无论我传入的参数num的值是哪几个数字,它的运行时间全部都不 X(相对于同一台机器而言)。函数increment()的性能与参数无关,五种五种人都后能 说它的算法复杂度是O(1)(常数)。

  再看十个 多例子:

function sequentialSearch(array, item) {
    for (let i = 0; i < array.length; i++) {
        if (item === array[i]) return i;
    }
    return -1;
}

  函数sequentialSearch()的作用是在数组中搜索给定的值,并返回对应的索引号。假设array有10个元素,意味着着要搜索的元素排在第十个 多,五种人说开销为1。意味着着要搜索的元素排在最后十个 多,则开销为10。当数组有100个元素时,搜索最后十个 多元素的开销是100。统统,sequentialSearch()函数的总开销取决于数组元素的个数和要搜索的值。在最坏请况下,没有找到要搜索的元素,没有总开销但是数组的长度。五种五种人得出sequentialSearch()函数的时间复杂度是O(n),n是数组的长度。

  同理,对于前面五种人说的冒泡排序算法,中间十个 多双层嵌套的for循环,五种它的复杂度为O(n2)。

  时间复杂度O(n)的代码不到一层循环,而O(n2)的代码有双层嵌套循环。意味着着算法有三层嵌套循环,它的时间复杂度但是O(n3)。

  下表展示了各种不同数据特征的时间复杂度:

数据特征 一般请况 最差请况
插入 删除 搜索 插入 删除 搜索
数组/栈/队列 O(1) O(1) O(n) O(1) O(1) O(n)
链表 O(1) O(1) O(n) O(1) O(1) O(n)
双向链表 O(1) O(1) O(n) O(1) O(1) O(n)
散列表 O(1) O(1) O(1) O(n) O(n) O(n)
BST树 O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n)
AVL树 O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))

数据特征的时间复杂度

节点/边的管理土办法 存储空间 增加顶点 增加边 删除顶点 删除边 轮询
领接表 O(| V | + | E |) O(1) O(1) O(| V | + | E |) O(| E |) O(| V |)
邻接矩阵 O(| V |2) O(| V |2) O(1) O(| V |2) O(1) O(1)

图的时间复杂度  

算法(用于数组) 时间复杂度
最好请况 一般请况 最差请况
冒泡排序 O(n) O(n2) O(n3)
选着 排序 O(n2) O(n2) O(n2)
插入排序 O(n) O(n2) O(n2)
归并排序 O(log(n)) O(log(n)) O(log(n))
快速排序 O(log(n)) O(log(n)) O(n2)
堆排序 O(log(n)) O(log(n)) O(log(n))

排序算法的时间复杂度

搜索算法

  顺序搜索是五种比较直观的搜索算法,中间介绍算法复杂度一小节中的sequentialSearch()函数但是顺序搜索算法,但是按顺序对数组中的元素逐一比较,直到找到匹配的元素。顺序搜索算法的下行速率 比较低。

  还有五种常见的搜索算法是二分搜索算法。它的执行过程是:

  1. 将待搜索数组排序。
  2. 选着 数组的中间值。
  3. 意味着着中间值正好是要搜索的值,则完成搜索。
  4. 意味着着要搜索的值比中间值小,则选着 中间值左边的每种,重新执行步骤2。
  5. 意味着着要搜索的值比中间值大,则选着 中间值右边的每种,重新执行步骤2。

  下面是二分搜索算法的具体实现:

function binarySearch(array, item) {
    quickSort(array); // 首先用快速排序法对array进行排序

    let low = 0;
    let high = array.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2); // 选着

中间位置的元素
        const element = array[mid];

        // 待搜索的值大于中间值
        if (element < item) low = mid + 1;
        // 待搜索的值小于中间值
        else if (element > item) high = mid - 1;
        // 待搜索的值但是中间值
        else return true;
    }

    return false;
}

  对应的测试结果:

const array = [8, 7, 6, 5, 4, 3, 2, 1];
console.log(binarySearch(array, 2)); // true

   五种 算法的基本思路特别类式于猜数字大小,每当我知道你出十个 多数字,我都不 告诉你是大了还是小了,经过几轮完后 ,你就都后能 很准确地选着 数字的大小了。

猜你喜欢

三洋 WT8655YM0S 8公斤超音波大容量全自动波轮洗衣机 全模糊智能控制 二步净洗涤(亮灰色)好不好,优缺点,是否值得买

2018-08-0713:19:32醒***悟5分东西收到了,用了哪几次才来评价,容量大,动力足,洗衣干净。2018-08-0608:33:23j***a5分不错不错后后购买三

2020-01-19

止暴制乱\林郑:首务止暴制乱救经济

图:今年头九个月,出入口较去年同期分别录得4.6%和6.5%跌幅特区政府今日回应第三季经济数据,本港经济步入技术性衰退几成定局。行政长官林郑月娥昨日出席“亚洲金融贸易未来”研讨

2020-01-19

亚摩勒比塔VS雷奥亚免费视频直播,亚摩勒比塔VS雷奥亚比赛集锦,亚摩勒比塔VS雷奥亚录像,亚摩勒比塔VS雷奥亚首发阵容

首页新闻视频直播数据APP懂球号直播君广告合作方式亚摩勒比塔雷奥亚直播君|分析|集锦近期比赛萨索洛意甲2-1都灵纽卡斯尔联英超1-0切尔西奥萨苏纳西甲0-0巴拉多利德那不勒斯意

2020-01-19

触宝今晚赴美上市,董事长张瞰发公开信:AI是未来方向

9月28日下午消息,北京时间今晚10点,全球移动互联网公司、中国出海企业触宝将正式在美国纽交所挂牌上市,股票代码:CTK。触宝此次全球发售4315万股美国存托股票(ADS),每

2020-01-19

港版联想Moto Z迎来安卓7.1.1升级

IT之家7月19日消息,目前香港和印度尼西亚的MotoZ用户可能收到Android7.1.1更新,该机去年预装Android6.0上市,之后 更新到了Android7.0。用

2020-01-19