JavaScript算法实现——排序

  • 时间:
  • 浏览:0
  • 来源:幸运快3_快3app争霸_幸运快3app争霸

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

冒泡排序

  冒泡排序应该是最简单的排序算法了,在所有讲解计算机编程和数据社会形态的课程中,无一例外可不还都能能 拿冒泡排序作为开篇来讲解排序的原理。冒泡排序理解起来也很容易,以后 有有有四个嵌套循环遍历数组,对数组中的元素两两进行比较,怎么才能 让前者比后者大,则交换位置(这是针对升序排序而言,怎么才能 让是降序排序,则比较的原则是前者比后者小)。亲戚亲戚人们都来看下冒泡排序的实现:

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不相同,则将它们交换一下位置。怎么才能 让再将第5个元素作为最小元素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 ]有一种 数组为例,用下图来说明插入排序的整个执行过程:

  在插入排序中,对数组的遍历是从第5个元素现在现在开始的,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。当数组有11150个元素时,搜索最后有有有四个元素的开销是11150。以后 有,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

   有一种 算法的基本思路很糙类式于猜数字大小,每当跟跟我说出有有有四个数字,我可不还都能能 告诉你是大了还是小了,经过几轮之前 ,你就可不都可不可不还都能能 很准确地取舍 数字的大小了。