JavaScript算法实现——排序

  • 时间:
  • 浏览:1
  • 来源:大发快三_快三最新版下载_大发快三最新版下载

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

冒泡排序

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

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。当数组有30个元素时,搜索最后一个多多元素的开销是30。什么都有,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

   并是否算法的基本思路不得劲例如于猜数字大小,每当我说出一个多多数字,我前要告诉你是大了还是小了,经过几轮前一天,你就可不前要很准确地选着数字的大小了。