javascript数据结构与算法 --- 高级排序算法

qianfeng 发布于2019-08-26 11:34 / 1777人阅读

摘要：高级排序算法总结希尔排序间隔序列可以动态定义，不过对于大部分的实际应用场景，算法要用到的间隔序列可以提前定义好有一些公开定义的间隔序列，使用它们会得到不同的结果。

高级排序算法总结

希尔排序

    function shellsort(array, gaps) {
      for (var g = 0; g < gaps.length; g++) {
        for (var i = gaps[g]; i < array.length; i++) {
          var temp = array[i];
          for (var j = i; (j >= gaps[g]) && (temp < array[j-gaps[g]]);j -= gaps[g]) {
            array[j] = array[j - gaps[g]];
          }
          array[j] = temp;
        }
        console.log(array);
      }
    }

间隔序列 gaps可以动态定义，不过对于大部分的实际应用场景，算法要用到的间隔序列可以提前定义好,有一些公开定义的间隔序列，使用它们会得到不同的结果。例如Marcin Ciura 在2001 的论文“Best Increments for theAverage Case of Shell Sort”中的间隔序列[701, 301, 132, 57, 23, 10, 4, 1],下一节将介绍具有动态间隔序列的希尔排序.

动态间隔序列希尔排序

    function dynOrdShellsort(array) {
      var N = array.length;
      var h = 1;
      while (h < N/3) {h = 3 * h + 1;
      }
      while (h >= 1) {
        for (var i = h; i < N; i++) {
          for (var j = i; j >= h && array[j] < array[j-h]; j -= h) {
            // swap(array, j, j-h);
            [array[j], array[j-h]] = [array[j-h], array[j]];
          }
        }h = (h-1)/3;
      }
    }

在《算法（第 4 版）》（人邮版）的合著者 Robert Sedgewick 定义了一个   shellsort() 函数，在这个函数中可以通过一个公式来对希尔排序用到的间隔序列进行动态计算。Sedgewick 的算法是通过上面的代码片段来决定初始间隔值的,并添加到外层 for 循环.

归并排序

    let mergeSort = (function () {
      function mergeSort(arr) {
        if (arr.length < 2) {
          return;
        }
        var step = 1;
        var left, right;
        while (step < arr.length) {
          left = 0;
          right = step;
          while (right + step <= arr.length) {
            mergeArrays(arr, left, left+step, right, right+step);
            left = right + step;
            right = left + step;
          }
          if (right < arr.length) {
            mergeArrays(arr, left, left+step, right, arr.length);
          }
          step *= 2;
        }
      }
      function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
        var rightArr = new Array(stopRight - startRight + 1);
        var leftArr = new Array(stopLeft - startLeft + 1);
        k = startRight;
        for (var i = 0; i < (rightArr.length-1); ++i) {
          rightArr[i] = arr[k];
          ++k;
        }
        k = startLeft;
        for (var i = 0; i < (leftArr.length-1); ++i) {
          leftArr[i] = arr[k];
          ++k;
        }
        rightArr[rightArr.length-1] = Infinity; // 哨兵值
        leftArr[leftArr.length-1] = Infinity; // 哨兵值
        var m = 0;
        var n = 0;
        for (var k = startLeft; k < stopRight; ++k) {
          if (leftArr[m] <= rightArr[n]) {
            arr[k] = leftArr[m];
            m++;
          }
          else {
            arr[k] = rightArr[n];
            n++;
          }
        }
        // console.log("left array - ", leftArr);
        // console.log("right array - ", rightArr);
      }
      return mergeSort;
    })()

快速排序

    function qSort(arr){
      if (arr.length == 0) {
        return [];
      }
      var left = [];
      var right = [];
      var pivot = arr[0];
      for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
      }
      return qSort(left).concat(pivot, qSort(right));
    }

云服务器 GPU云服务器算法与数据结构数据结构与算法排序算法图解排序算法总结

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

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

javascript数据结构与算法 --- 基本排序算法

摘要：基本排序算法总结前言随着的兴起将推向的一个前所未有的高度作为为建立高性能的服务端而创建的运行平台随着时间的推移和生态链的完善已经不再局部于服务端包括前端后端桌面这篇文章介绍的传统的散打排序方法并用实现其功能如有需要可以对其封装在随后会介绍高基本排序算法总结前言随着node的兴起, 将javascript推向的一个前所未有的高度, node作为为建立高性能的服务端而创建的js运行平...

wangdai 2019-08-26 11:33 评论0 收藏0
javascript实现排序算法

摘要：高级排序算法有希尔排序归并排序快速排序。冒泡排序首先声明，这是最慢的排序算法之一，但是也是最容易实现的排序算法。稳定性冒泡排序为一种稳定排序。快速排序快速排序是出力大数据集最快的排序算法之一。简介对计算机中存储的数据执行的两种最常见的操作是排序和检索，也是面试经常会被问到的一个知识点，本文将整理数据排序的基本算法和高级算法。其中基本排序算法有：冒泡排序、选择排序、插入排序。高级排序...

xiangzhihong 2019-08-22 10:39 评论0 收藏0
Nicolas讲算法：Computer Science in JavaScript

摘要：使用来描述算法和数据结构的教程很少，目前市面上用描述算法和数据结构的书屈指可数，并且就我看过的那本而言我只看过数据结构与算法语言描述质量实在堪忧。使用JavaScript来描述算法和数据结构的教程很少，目前市面上用JS描述算法和数据结构的书屈指可数，并且就我看过的那本而言（我只看过《数据结构与算法 JavaScript 语言描述》）质量实在堪忧。碰巧有次看到Nicolas博客中的C...

codergarden 2019-08-19 17:30 评论0 收藏0
JavaScript数据结构和算法

摘要：栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构，比如下面介绍的二叉查找树。前言在过去的几年中，得益于Node.js的兴起，JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器，程序员发现他们需要更多传统语言（比如C++和Java）提供的工具。这些工具包括传统的数据结构（如链表，栈，队列，图等），...

EastWoodYang 2019-08-21 16:23 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

aaron 2019-08-01 17:38 评论0 收藏0