JavaScript的排序算法

booster 发布于2019-08-26 10:34 / 1290人阅读

摘要：基本概念时间复杂度算法执行所耗费的时间。内排序所有排序操作都在内存中完成。常用的排序算法冒泡排序基本概念依次比较相邻的两个数将小数放在前面，大数放在后面。实现原理通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。

1：基本概念

时间复杂度：算法执行所耗费的时间。

这个复杂度直接和样本的个数有关，复杂度反映了算法的性能，一般来说，复杂度越低，算法所消耗的时间越短。

    /* O(N1) */
    for (var i = 0; i < data.length; i++) {
        ...
    }
    
    /* O(N2) */
    for (var i = 0; i < data.length; i++) {
        for (var j = 0; j < data.length; j++) {
            ...
        }
    }

空间复杂度：运行一个程序所需内存的大小。

空间复杂度和时间复杂度是对立的，比如说，时间复杂度越高，空间复杂度越低；反之则相反。

内排序：所有排序操作都在内存中完成。

2：常用的排序算法 冒泡排序（Bubble Sort）

基本概念：依次比较相邻的两个数,将小数放在前面，大数放在后面。

时间复杂度：O(N2)。

实现原理：重复的走访要排序的数列，一次比较两个元素，大的元素放后面，如果它们的顺序错误就把它们交换过来。

代码实现：有两层循环嵌套，外循环遍历数组的每一项，内循环用于两两元素的比较，每次内循环减1。

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

选择排序（Selection Sort）

时间复杂度：O(N2)。

实现原理：从未排序的序列中找到最小(大)的元素存放到指定的起始位置，再从未排序的序列元素中重复上一步，直至排序完成。

代码实现：两层循环嵌套，外循环遍历数组的每一项，内循环用于找到样本里面的最小值或者最大值，每次内循环减1。

    function selectionSort(arr) {
        var length = arr.length;
        var minIndex, temp;
        for (var i = 0; i < length - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
        }
        return arr;
    }

快速排序（Quick Sort）

时间复杂度：O(N * log2N)。

实现原理：通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。

代码实现：找到一个数作为参考，然后比这个数字大的放在数字左边，比它小的放在右边，分别再对左右两边的序列做相同的操作。

    function partition(arr, low, high) {
      let pivot = arr[low];
      while (low < high) {
        while (low < high && arr[high] > pivot) {
          --high;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) {
          ++low;
        }
        arr[high] = arr[low];
      }
      arr[low] = pivot;
      return low;
    }
    function quickSort(arr, low, high) {
      if (low < high) {
        let pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
      }
      return arr;
    }

插入排序（Insertion Sort）

时间复杂度：O(N2)。

实现原理：构建一个有序序列，未排序数据在已排序序列中从后向前扫描，找到正确位置插入。

代码实现：两层循环嵌套，创建已排序数组, 起始包含数组的第一个元素，比这个数字大的放在数字左边，比它小的放在右边。

    function insertSort(arr) {
        for(let i = 1; i < arr.length; i++) {
            for(let j = i; j > 0; j--) {
                if(arr[j] < arr[j-1]) {
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                } else {
                    break;
                }
            }
        }
        return arr;
    }

海外云主机 GPU服务器字母的排序算法最好的排序算法选择排序的算法过程最好的快速排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106395.html

深入浅出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

caoym 2019-07-31 10:56 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

microcosm1994 2019-08-20 16:30 评论0 收藏0
常用排序算法之JavaScript实现

摘要：代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序，排序的速度快于任何比较排序算法。赞助我以写出更好的文章，give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1）算法简介插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它...

jerry 2019-08-21 12:27 评论0 收藏0
优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...

cheukyin 2019-08-26 10:17 评论0 收藏0