JavaScript中常见排序算法详解,面试中常见算法问题详解

JavaScript 面试中常见算法难点详解

2017/02/20 · JavaScript
· 1 评论 ·
算法

原稿出处:
王下邀月熊_Chevalier   

JavaScript
面试中常见算法难题详解 翻译自
Interview Algorithm Questions in Javascript()
{…}
从属于小编的 Web
前端入门与工程执行。下文提到的重重难点从算法角度并不一定要么困难,但是用
JavaScript 内置的 API 来成功或者须要一番勘验的。

图片 1

JavaScript中常见排序算法详解

 

有句话怎么说来着:

雷锋推倒开封铁塔,Java implements JavaScript.

当下,想依靠抱Java大腿火一把而不惜把温馨名字给改了的JavaScript(原名LiveScript),如明儿晚上已光芒万丈。node
JS的产出更是让JavaScript可往日后端通吃。虽然Java仍然制霸集团级软件开发领域(C/C
+
+的大神们不要打我。。。),但在Web的人间,JavaScript可谓风头无两,坐上了头把交椅。

不过,在观念的统计机算法和数据结构领域,一大半标准教材和本本的默许语言都是Java或者C/C+
+。那给近日想恶补算法和数据结构知识的我造成了迟早麻烦,因为我想搜寻一本以JavaScript为默许语言的算法书籍。当自己打听到O’REILLY家的动物丛书体系里有一本叫做《数据结构与算法JavaScript描述》时,便快乐的花了两日时间把那本书从头到尾读了几回。它是一本很好的对准前者开发者们的入门算法书籍,不过,它有一个很大的败笔,就是内部有为数不少显明的小错误,显著到就连自己那种半路出家的程序猿都能一眼看出来。还有一个标题是,很多至关主要的算法和数据结构知识并从未在那本书里被提到。那一个题材对于作为一个末期精神分裂症伤者的自家来说简直不可以忍。于是乎,一言不合我就控制自己找材料总括算法。那么,我就从算法领域里最基础的知识点——排序算法总括起好了。

我相信以下的代码里肯定会有好几bug或不当或语法不标准等难题是本身要好不可以察觉的,所以敬请诸君大神可以提议错误,因为只有在不断改错的道路上自家才能收获短期的前行。

JavaScript Specification

正文提到的洋洋难题从算法角度并不一定要么困难,不过用 JavaScript 内置的
API 来成功或者要求一番勘测的。
1.演讲下 JavaScript 中的变量升高
所谓提升,顾名思义即是 JavaScript
会将兼具的宣示升高到眼前成效域的顶部。那也就代表大家得以在某个变量表明前就使用该变量,但是尽管JavaScript 会将宣示进步到顶部,然则并不会执行真的早先化进程。
2.阐述下 use strict; 的作用

十大经典算法

一张图概括:

图片 2

 

名词解释:

n:数据规模

k:“桶”的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

安居:排序后2个至极键值的依次和排序以前它们的次第相同

有句话怎么说来着:

阐释下 JavaScript 中的变量提高

所谓提升,顾名思义即是 JavaScript
会将具备的扬言进步到当前功能域的顶部。那也就代表大家得以在某个变量表明前就动用该变量,不过固然JavaScript 会将宣示进步到顶部,然则并不会执行真的开头化进程。

….

冒泡排序

作为最简便的排序算法之一,冒泡排序给自身的觉得就像是Abandon在单词书里涌出的痛感一样,每一趟都在首先页第三位,所以最熟识。。。冒泡排序还有一种优化算法,就是立一个flag,当在一趟系列遍历中元素没有发出沟通,则表明该种类已经逐步。但这种创新对于提高品质来说并没有怎么太大作用。。。

雷锋推倒西塔,Java implements JavaScript.

阐述下 use strict;JavaScript中常见排序算法详解,面试中常见算法问题详解。 的作用

use strict; 顾名思义也就是 JavaScript
会在所谓严厉格局下实施,其一个重点的优势在于可以强制开发者幸免接纳未声明的变量。对于老版本的浏览器仍旧实施引擎则会自动忽略该指令。

JavaScript

// Example of strict mode “use strict”; catchThemAll(); function
catchThemAll() { x = 3.14; // Error will be thrown return x * x; }

1
2
3
4
5
6
7
8
// Example of strict mode
"use strict";
 
catchThemAll();
function catchThemAll() {
  x = 3.14; // Error will be thrown
  return x * x;
}
如曾几何时候最快

 

当输入的数量现已是正序时(都早就是正序了,我还要你冒泡排序有啥用啊。。。。)

那儿,想借助抱Java大腿火一把而不惜把团结名字给改了的JavaScript(原名LiveScript),目前晚已光芒万丈。node
JS的面世更是让JavaScript可以上下端通吃。固然Java如故制霸公司级软件开发领域(C/C
+
+的大神们不用打我。。。),但在Web的下方,JavaScript可谓风头无两,坐上了头把交椅。

诠释下什么样是 伊芙nt Bubbling 以及哪些幸免

伊芙nt Bubbling
即指某个事件不仅会接触当前因素,还会以嵌套顺序传递到父元素中。直观而言就是对于某个子元素的点击事件相同会被父元素的点击事件处理器捕获。幸免伊芙nt Bubbling 的章程可以行使event.stopPropagation() 或者 IE 9
以下使用event.cancelBubble

怎么时候最慢

 

当输入的数额是反序时(写一个for循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吧。。。)

只是,在传统的微机算法和数据结构领域,一大半规范教材和图书的默许语言都是Java或者C/C+
+。那给方今想恶补算法和数据结构知识的本人造成了自然苦恼,因为自己想寻找一本以JavaScript为默许语言的算法书籍。当我通晓到O’REILLY家的动物丛书连串里有一本叫做《数据结构与算法JavaScript描述》时,便快乐的花了两日时间把那本书从头到尾读了一回。它是一本很好的针对前者开发者们的入门算法书籍,可是,它有一个很大的后天不足,就是内部有成百上千明确的小错误,明显到就连自己那种半路出家的程序猿都能一眼看出来。还有一个标题是,很多重中之重的算法和数据结构知识并从未在那本书里被波及。那么些题材对于作为一个中期性障碍患者的自身的话几乎不可以忍。于是乎,一言不合我就控制自己找资料计算算法。那么,我就从算法领域里最基础的知识点——排序算法总括起好了。

== 与 === 的界别是什么样

=== 也就是所谓的严加相比,关键的分别在于===
会同时比较类型与值,而不是仅比较值。

JavaScript

// Example of comparators 0 == false; // true 0 === false; // false 2 ==
‘2’; // true 2 === ‘2’; // false

1
2
3
4
5
6
// Example of comparators
0 == false; // true
0 === false; // false
 
2 == ‘2’; // true
2 === ‘2’; // false
冒泡排序动图演示

 

图片 3

 

自家深信不疑以下的代码里一定会有少数bug或错误或语法半间半界等难题是本人要好无法察觉的,所以敬请诸君大神可以提出错误,因为只有在时时刻刻改错的征途上我才能获得长时间的腾飞。

解释下 null 与 undefined 的区别

JavaScript 中,null 是一个足以被分配的值,设置为 null
的变量意味着其无值。而 undefined
则象征着某个变量纵然声称通晓则从未开展过任何赋值。

JavaScript代码达成

 

 function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;}

十大经典算法

解释下 Prototypal Inheritance 与 Classical Inheritance 的区别

在类继承中,类是不可变的,区其他语言中对于多两次三番的协助也分裂,有些语言中还支持接口、final、abstract
的定义。而原型继承则越发灵活,原型本身是可以可变的,并且对象可能一连自七个原型。

选料排序

展现最平静的排序算法之一,因为随便怎么数据进去都是O(n²)的时光复杂度。。。所以用到它的时候,数据规模越小越好。唯一的补益恐怕就是不占用额外的内存空间了呢。

一张图概括:

数组

选料排序动图演示

 

图片 4

 

图片 5

找出整型数组中乘积最大的三个数

给定一个饱含整数的无序数组,须求找出乘积最大的多少个数。

JavaScript

var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];
computeProduct(unsorted_array); // 21000 function sortIntegers(a, b) {
return a – b; } // greatest product is either (min1 * min2 * max1 ||
max1 * max2 * max3) function computeProduct(unsorted) { var
sorted_array = unsorted.sort(sortIntegers), product1 = 1, product2 = 1,
array_n_element = sorted_array.length – 1; // Get the product of
three largest integers in sorted array for (var x = array_n_element; x
> array_n_element – 3; x–) { product1 = product1 *
sorted_array[x]; } product2 = sorted_array[0] *
sorted_array[1] * sorted_array[array_n_element]; if (product1
> product2) return product1; return product2 };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];
 
computeProduct(unsorted_array); // 21000
 
function sortIntegers(a, b) {
  return a – b;
}
 
// greatest product is either (min1 * min2 * max1 || max1 * max2 * max3)
function computeProduct(unsorted) {
  var sorted_array = unsorted.sort(sortIntegers),
    product1 = 1,
    product2 = 1,
    array_n_element = sorted_array.length – 1;
 
  // Get the product of three largest integers in sorted array
  for (var x = array_n_element; x > array_n_element – 3; x–) {
      product1 = product1 * sorted_array[x];
  }
  product2 = sorted_array[0] * sorted_array[1] * sorted_array[array_n_element];
 
  if (product1 > product2) return product1;
 
  return product2
};
JavaScript代码已毕

 

 function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;}

名词解释:

找寻连续数组中的缺失数

给定某无序数组,其蕴涵了 n 个延续数字中的 n – 1
个,已知上下面界,必要以O(n)的复杂度找出缺失的数字。

JavaScript

// The output of the function should be 8 var array_of_integers = [2,
5, 1, 4, 9, 6, 3, 7]; var upper_bound = 9; var lower_bound = 1;
findMissingNumber(array_of_integers, upper_bound, lower_bound); //8
function findMissingNumber(array_of_integers, upper_bound,
lower_bound) { // Iterate through array to find the sum of the numbers
var sum_of_integers = 0; for (var i = 0; i <
array_of_integers.length; i++) { sum_of_integers +=
array_of_integers[i]; } // 以高斯求和公式计算理论上的数组和 //
Formula: [(N * (N + 1)) / 2] – [(M * (M – 1)) / 2]; // N is the
upper bound and M is the lower bound upper_limit_sum = (upper_bound
* (upper_bound + 1)) / 2; lower_limit_sum = (lower_bound *
(lower_bound – 1)) / 2; theoretical_sum = upper_limit_sum –
lower_limit_sum; // return (theoretical_sum – sum_of_integers) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// The output of the function should be 8
var array_of_integers = [2, 5, 1, 4, 9, 6, 3, 7];
var upper_bound = 9;
var lower_bound = 1;
 
findMissingNumber(array_of_integers, upper_bound, lower_bound); //8
 
function findMissingNumber(array_of_integers, upper_bound, lower_bound) {
 
  // Iterate through array to find the sum of the numbers
  var sum_of_integers = 0;
  for (var i = 0; i < array_of_integers.length; i++) {
    sum_of_integers += array_of_integers[i];
  }
 
  // 以高斯求和公式计算理论上的数组和
  // Formula: [(N * (N + 1)) / 2] – [(M * (M – 1)) / 2];
  // N is the upper bound and M is the lower bound
 
  upper_limit_sum = (upper_bound * (upper_bound + 1)) / 2;
  lower_limit_sum = (lower_bound * (lower_bound – 1)) / 2;
 
  theoretical_sum = upper_limit_sum – lower_limit_sum;
 
  //
  return (theoretical_sum – sum_of_integers)
}

插入排序

插入排序的代码完毕即使尚未冒泡排序和抉择排序那么不难暴虐,但它的规律应该是最不难精晓的了,因为一旦打过扑克牌的人都应有力所能及秒懂。当然,假若您说你打扑克牌摸牌的时候没有按牌的大小整理牌,那估量那辈子你对插入排序的算法都不会时有暴发任何兴趣了。。。

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。对于那种算法,得了懒癌的自己就沿用教科书上的一句经典的话吧:感兴趣的同班能够在课后活动钻研。。。

n:数据规模

数组去重

给定某无序数组,要求删减数组中的重复数字并且再次来到新的无重复数组。

JavaScript

// ES6 Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8] // ES5
Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
uniqueArray(array); // [1, 2, 3, 5, 9, 8] function uniqueArray(array)
{ var hashmap = {}; var unique = []; for(var i = 0; i <
array.length; i++) { // If key returns null (unique), it is evaluated as
false. if(!hashmap.hasOwnProperty([array[i]])) {
hashmap[array[i]] = 1; unique.push(array[i]); } } return unique; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// ES6 Implementation
var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
 
Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]
 
 
// ES5 Implementation
var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
 
uniqueArray(array); // [1, 2, 3, 5, 9, 8]
 
function uniqueArray(array) {
  var hashmap = {};
  var unique = [];
  for(var i = 0; i < array.length; i++) {
    // If key returns null (unique), it is evaluated as false.
    if(!hashmap.hasOwnProperty([array[i]])) {
      hashmap[array[i]] = 1;
      unique.push(array[i]);
    }
  }
  return unique;
}
插入排序动图演示

 

图片 6

 

k:“桶”的个数

数组中元素最大差值总括

给定某无序数组,求取任意多个要素之间的最大差值,注意,这里须求差值统计中较小的元素下标必须低于较大要素的下标。譬如[7, 8, 4, 9, 9, 15, 3, 1, 10]以此数组的统计值是
11( 15 – 4 ) 而不是 14(15 – 1),因为 15 的下标小于 1。

JavaScript

var array = [7, 8, 4, 9, 9, 15, 3, 1, 10]; // [7, 8, 4, 9, 9, 15, 3,
1, 10] would return `11` based on the difference between `4` and
`15` // Notice: It is not `14` from the difference between `15`
and `1` because 15 comes before 1. findLargestDifference(array);
function findLargestDifference(array) { //
假诺数组仅有一个要素,则一贯重返 -1 if (array.length <= 1) return -1;
// current_min 指向当前的纤维值 var current_min = array[0]; var
current_max_difference = 0; //
遍历整个数组以求取当前最大差值,假若发现某个最大差值,则将新的值覆盖
current_max_difference // 同时也会追踪当前数组中的最小值,从而确保
`largest value in future` – `smallest value before it` for (var i =
1; i < array.length; i++) { if (array[i] > current_min &&
(array[i] – current_min > current_max_difference)) {
current_max_difference = array[i] – current_min; } else if
(array[i] <= current_min) { current_min = array[i]; } } // If
negative or 0, there is no largest difference if
(current_max_difference <= 0) return -1; return
current_max_difference; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var array = [7, 8, 4, 9, 9, 15, 3, 1, 10];
// [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15`
// Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1.
 
findLargestDifference(array);
 
function findLargestDifference(array) {
 
  // 如果数组仅有一个元素,则直接返回 -1
 
  if (array.length <= 1) return -1;
 
  // current_min 指向当前的最小值
 
  var current_min = array[0];
  var current_max_difference = 0;
  
  // 遍历整个数组以求取当前最大差值,如果发现某个最大差值,则将新的值覆盖 current_max_difference
  // 同时也会追踪当前数组中的最小值,从而保证 `largest value in future` – `smallest value before it`
 
  for (var i = 1; i < array.length; i++) {
    if (array[i] > current_min && (array[i] – current_min > current_max_difference)) {
      current_max_difference = array[i] – current_min;
    } else if (array[i] <= current_min) {
      current_min = array[i];
    }
  }
 
  // If negative or 0, there is no largest difference
  if (current_max_difference <= 0) return -1;
 
  return current_max_difference;
}
JavaScript代码达成

 

 function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;}

In-place:占用常数内存,不占用额外内存

数组中元素乘积

给定某无序数组,需求再次来到新数组 output ,其中 output[i]
为原数组中除了下标为 i 的因素之外的因素乘积,须求以 O(n) 复杂度已毕:

JavaScript

var firstArray = [2, 2, 4, 1]; var secondArray = [0, 0, 0, 2]; var
thirdArray = [-2, -2, -3, 2]; productExceptSelf(firstArray); // [8,
8, 4, 16] productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12] function
productExceptSelf(numArray) { var product = 1; var size =
numArray.length; var output = []; // From first array: [1, 2, 4, 16]
// The last number in this case is already in the right spot (allows for
us) // to just multiply by 1 in the next step. // This step essentially
gets the product to the left of the index at index + 1 for (var x = 0; x
< size; x++) { output.push(product); product = product *
numArray[x]; } // From the back, we multiply the current output
element (which represents the product // on the left of the index, and
multiplies it by the product on the right of the element) var product =
1; for (var i = size – 1; i > -1; i–) { output[i] = output[i] *
product; product = product * numArray[i]; } return output; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var firstArray = [2, 2, 4, 1];
var secondArray = [0, 0, 0, 2];
var thirdArray = [-2, -2, -3, 2];
 
productExceptSelf(firstArray); // [8, 8, 4, 16]
productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12]
 
function productExceptSelf(numArray) {
  var product = 1;
  var size = numArray.length;
  var output = [];
 
  // From first array: [1, 2, 4, 16]
  // The last number in this case is already in the right spot (allows for us)
  // to just multiply by 1 in the next step.
  // This step essentially gets the product to the left of the index at index + 1
  for (var x = 0; x < size; x++) {
      output.push(product);
      product = product * numArray[x];
  }
 
  // From the back, we multiply the current output element (which represents the product
  // on the left of the index, and multiplies it by the product on the right of the element)
  var product = 1;
  for (var i = size – 1; i > -1; i–) {
      output[i] = output[i] * product;
      product = product * numArray[i];
  }
 
  return output;
}

希尔排序

Hill排序是插入排序的一种更高效能的兑现。它与插入排序的分歧之处在于,它会事先比较距离较远的元素。希尔排序的主干在于距离体系的设定。既可以提前设定好间隔体系,也足以动态的概念间隔连串。动态定义间隔种类的算法是《算法(第4版》的合著者罗伯特Sedgewick提议的。在此处,我就使用了那种方法。

Out-place:占用额外内存

数组交集

给定五个数组,必要求出多少个数组的混合,注意,交集中的因素应该是唯一的。

JavaScript

var firstArray = [2, 2, 4, 1]; var secondArray = [1, 2, 0, 2];
intersection(firstArray, secondArray); // [2, 1] function
intersection(firstArray, secondArray) { // The logic here is to create a
hashmap with the elements of the firstArray as the keys. // After that,
you can use the hashmap’s O(1) look up time to check if the element
exists in the hash // If it does exist, add that element to the new
array. var hashmap = {}; var intersectionArray = [];
firstArray.forEach(function(element) { hashmap[element] = 1; }); //
Since we only want to push unique elements in our case… we can
implement a counter to keep track of what we already added
secondArray.forEach(function(element) { if (hashmap[element] === 1) {
intersectionArray.push(element); hashmap[element]++; } }); return
intersectionArray; // Time complexity O(n), Space complexity O(n) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var firstArray = [2, 2, 4, 1];
var secondArray = [1, 2, 0, 2];
 
intersection(firstArray, secondArray); // [2, 1]
 
function intersection(firstArray, secondArray) {
  // The logic here is to create a hashmap with the elements of the firstArray as the keys.
  // After that, you can use the hashmap’s O(1) look up time to check if the element exists in the hash
  // If it does exist, add that element to the new array.
 
  var hashmap = {};
  var intersectionArray = [];
 
  firstArray.forEach(function(element) {
    hashmap[element] = 1;
  });
 
  // Since we only want to push unique elements in our case… we can implement a counter to keep track of what we already added
  secondArray.forEach(function(element) {
    if (hashmap[element] === 1) {
      intersectionArray.push(element);
      hashmap[element]++;
    }
  });
 
  return intersectionArray;
 
  // Time complexity O(n), Space complexity O(n)
}
JavaScript代码落成

 

 function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;}

安宁:排序后2个极度键值的次第和排序从前它们的顺序相同

字符串

归并排序

用作一种典型的分而治之思想的算法应用,归并排序的落实由三种情势:

  • 自上而下的递归(所有递归的点子都得以用迭代重写,所以就有了第2种方法)

  • 自下而上的迭代

在《数据结构与算法JavaScript描述》中,小编给出了自下而上的迭代方法。不过对于递归法,小编却觉得:

However, it is not possible to do so in JavaScript, as the recursion
goes too deep for the language to handle.

而是,在 JavaScript
中那种办法不太实用,因为那几个算法的递归深度对它来讲太深了。

说实话,我不太知道那句话。意思是JavaScript编译器内存太小,递归太深简单导致内存溢出吧?还望有大神可以指教。

和甄选排序一样,归并排序的属性不受输入数据的影响,但彰显比选择排序好的多,因为平昔都是O(n
log n)的年华复杂度。代价是索要极度的内存空间。

冒泡排序

颠倒字符串

加以某个字符串,须要将里面单词倒转之后然后输出,譬如”Welcome to this
Javascript Guide!” 应该出口为 “emocleW ot siht tpircsavaJ !ediuG”。

JavaScript

var string = “Welcome to this Javascript Guide!”; // Output becomes
!ediuG tpircsavaJ siht ot emocleW var reverseEntireSentence =
reverseBySeparator(string, “”); // Output becomes emocleW ot siht
tpircsavaJ !ediuG var reverseEachWord =
reverseBySeparator(reverseEntireSentence, ” “); function
reverseBySeparator(string, separator) { return
string.split(separator).reverse().join(separator); }

1
2
3
4
5
6
7
8
9
10
11
var string = "Welcome to this Javascript Guide!";
 
// Output becomes !ediuG tpircsavaJ siht ot emocleW
var reverseEntireSentence = reverseBySeparator(string, "");
 
// Output becomes emocleW ot siht tpircsavaJ !ediuG
var reverseEachWord = reverseBySeparator(reverseEntireSentence, " ");
 
function reverseBySeparator(string, separator) {
  return string.split(separator).reverse().join(separator);
}
归并排序动图演示

 图片 7

 

图片 8

用作最简易的排序算法之一,冒泡排序给自身的觉得就像是Abandon在单词书里涌出的痛感一样,每一回都在首先页第一位,所以最熟习。。。冒泡排序还有一种优化算法,就是立一个flag,当在一趟体系遍历中元素没有发出互换,则表明该序列已经平稳。但那种革新对于提高质量来说并没有怎么太大功能。。。

乱序同字母字符串

给定多少个字符串,判断是还是不是颠倒字母而成的字符串,譬如MaryArmy就是同字母而相继颠倒:

JavaScript

var firstWord = “Mary”; var secondWord = “Army”; isAnagram(firstWord,
secondWord); // true function isAnagram(first, second) { // For case
insensitivity, change both words to lowercase. var a =
first.toLowerCase(); var b = second.toLowerCase(); // Sort the strings,
and join the resulting array to a string. Compare the results a =
a.split(“”).sort().join(“”); b = b.split(“”).sort().join(“”); return a
=== b; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var firstWord = "Mary";
var secondWord = "Army";
 
isAnagram(firstWord, secondWord); // true
 
function isAnagram(first, second) {
  // For case insensitivity, change both words to lowercase.
  var a = first.toLowerCase();
  var b = second.toLowerCase();
 
  // Sort the strings, and join the resulting array to a string. Compare the results
  a = a.split("").sort().join("");
  b = b.split("").sort().join("");
 
  return a === b;
}
归并排序JavaScript代码达成:

 

 function mergeSort(arr) {  //采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));}function merge(left, right){
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;}

怎么时候最快

会问字符串

判定某个字符串是不是为回文字符串,譬如racecarrace car都是回文字符串:

JavaScript

isPalindrome(“racecar”); // true isPalindrome(“race Car”); // true
function isPalindrome(word) { // Replace all non-letter chars with “”
and change to lowercase var lettersOnly =
word.toLowerCase().replace(/\s/g, “”); // Compare the string with the
reversed version of the string return lettersOnly ===
lettersOnly.split(“”).reverse().join(“”); }

1
2
3
4
5
6
7
8
9
10
isPalindrome("racecar"); // true
isPalindrome("race Car"); // true
 
function isPalindrome(word) {
  // Replace all non-letter chars with "" and change to lowercase
  var lettersOnly = word.toLowerCase().replace(/\s/g, "");
 
  // Compare the string with the reversed version of the string
  return lettersOnly === lettersOnly.split("").reverse().join("");
}

敏捷排序

即刻排序又是一种分而治之思想在排序算法上的超人应用。本质上来看,火速排序应该算是在冒泡排序基础上的递归分治法。

迅猛排序的名字起的是粗略凶残,因为一听到那一个名字你就了解它存在的含义,就是快,而且功用高!
它是拍卖大数量最快的排序算法之一了。纵然Worst
Case的时光复杂度达到了O(n²),不过人家就是不错,在多数情状下都比平均时间复杂度为O(n
log n)
的排序算法表现要更好,不过那是为啥吗,我也不知晓。。。好在自家的磨牙又犯了,查了N多资料终于在《算法艺术与信息学竞技》上找到了满足的答案:

飞速排序的最坏运行景况是O(n²),比如说顺序数列的快排。但它的摊派期望时间是O(n
log n) ,且O(n log n)记号中含有的常数因子很小,比复杂度稳定等于O(n log
n)的联结排序要小很多。所以,对多数顺序性较弱的擅自数列而言,飞快排序总是优于归并排序。

当输入的数码现已是正序时(都早已是正序了,我还要你冒泡排序有什么用啊。。。。)

栈与队列

高效排序动图演示

 

图片 9

 

什么样时候最慢

应用多个栈完成入队与出队

JavaScript

var inputStack = []; // First stack var outputStack = []; // Second
stack // For enqueue, just push the item into the first stack function
enqueue(stackInput, item) { return stackInput.push(item); } function
dequeue(stackInput, stackOutput) { // Reverse the stack such that the
first element of the output stack is the // last element of the input
stack. After that, pop the top of the output to // get the first element
that was ever pushed into the input stack if (stackOutput.length <=
0) { while(stackInput.length > 0) { var elementToOutput =
stackInput.pop(); stackOutput.push(elementToOutput); } } return
stackOutput.pop(); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var inputStack = []; // First stack
var outputStack = []; // Second stack
 
// For enqueue, just push the item into the first stack
function enqueue(stackInput, item) {
  return stackInput.push(item);
}
 
function dequeue(stackInput, stackOutput) {
  // Reverse the stack such that the first element of the output stack is the
  // last element of the input stack. After that, pop the top of the output to
  // get the first element that was ever pushed into the input stack
  if (stackOutput.length <= 0) {
    while(stackInput.length > 0) {
      var elementToOutput = stackInput.pop();
      stackOutput.push(elementToOutput);
    }
  }
 
  return stackOutput.pop();
}
迅猛排序JavaScript代码达成:

 

 function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;}function partition(arr, left ,right) {     //分区操作
    var pivot = left,                      //设定基准值(pivot)
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;}function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;}

当输入的数目是反序时(写一个for循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗。。。)

认清大括号是或不是关闭

创设一个函数来判定给定的表明式中的大括号是不是关闭:

JavaScript

var expression = “{{}}{}{}” var expressionFalse = “{}{{}”;
isBalanced(expression); // true isBalanced(expressionFalse); // false
isBalanced(“”); // true function isBalanced(expression) { var
checkString = expression; var stack = []; // If empty, parentheses are
technically balanced if (checkString.length <= 0) return true; for
(var i = 0; i < checkString.length; i++) { if(checkString[i] ===
‘{‘) { stack.push(checkString[i]); } else if (checkString[i] ===
‘}’) { // Pop on an empty array is undefined if (stack.length > 0) {
stack.pop(); } else { return false; } } } // If the array is not empty,
it is not balanced if (stack.pop()) return false; return true; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var expression = "{{}}{}{}"
var expressionFalse = "{}{{}";
 
isBalanced(expression); // true
isBalanced(expressionFalse); // false
isBalanced(""); // true
 
function isBalanced(expression) {
  var checkString = expression;
  var stack = [];
 
  // If empty, parentheses are technically balanced
  if (checkString.length <= 0) return true;
 
  for (var i = 0; i < checkString.length; i++) {
    if(checkString[i] === ‘{‘) {
      stack.push(checkString[i]);
    } else if (checkString[i] === ‘}’) {
      // Pop on an empty array is undefined
      if (stack.length > 0) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
 
  // If the array is not empty, it is not balanced
  if (stack.pop()) return false;
  return true;
}

堆排序

堆排序可以说是一种接纳堆的概念来排序的取舍排序。分为二种艺术:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列

  2. 小顶堆:每个节点的值都自愧不如或等于其子节点的值,在堆排序算法中用来降序排列

冒泡排序动图演示

递归

堆排序动图演示

 

图片 10

 

图片 11

二进制转换

经过某个递归函数将输入的数字转化为二进制字符串:

JavaScript

decimalToBinary(3); // 11 decimalToBinary(8); // 1000
decimalToBinary(1000); // 1111101000 function decimalToBinary(digit) {
if(digit >= 1) { // If digit is not divisible by 2 then recursively
return proceeding // binary of the digit minus 1, 1 is added for the
leftover 1 digit if (digit % 2) { return decimalToBinary((digit – 1) /
2) + 1; } else { // Recursively return proceeding binary digits return
decimalToBinary(digit / 2) + 0; } } else { // Exit condition return ”;
} }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
decimalToBinary(3); // 11
decimalToBinary(8); // 1000
decimalToBinary(1000); // 1111101000
 
function decimalToBinary(digit) {
  if(digit >= 1) {
    // If digit is not divisible by 2 then recursively return proceeding
    // binary of the digit minus 1, 1 is added for the leftover 1 digit
    if (digit % 2) {
      return decimalToBinary((digit – 1) / 2) + 1;
    } else {
      // Recursively return proceeding binary digits
      return decimalToBinary(digit / 2) + 0;
    }
  } else {
    // Exit condition
    return ”;
  }
}
堆排序JavaScript代码达成:

 

 var len;    //因为声明的多个函数都需要数据长度,所以把len设置成为全局变量function buildMaxHeap(arr) {   //建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }}function heapify(arr, i) {     //堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }}function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;}function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;}

JavaScript代码完成

二分查找

JavaScript

function recursiveBinarySearch(array, value, leftPosition,
rightPosition) { // Value DNE if (leftPosition > rightPosition)
return -1; var middlePivot = Math.floor((leftPosition + rightPosition) /
2); if (array[middlePivot] === value) { return middlePivot; } else if
(array[middlePivot] > value) { return recursiveBinarySearch(array,
value, leftPosition, middlePivot – 1); } else { return
recursiveBinarySearch(array, value, middlePivot + 1, rightPosition); } }

1
2
3
4
5
6
7
8
9
10
11
12
13
function recursiveBinarySearch(array, value, leftPosition, rightPosition) {
  // Value DNE
  if (leftPosition > rightPosition) return -1;
 
  var middlePivot = Math.floor((leftPosition + rightPosition) / 2);
  if (array[middlePivot] === value) {
    return middlePivot;
  } else if (array[middlePivot] > value) {
    return recursiveBinarySearch(array, value, leftPosition, middlePivot – 1);
  } else {
    return recursiveBinarySearch(array, value, middlePivot + 1, rightPosition);
  }
}
计数排序

 

计数排序的中坚在于将输入的数据值转化为键存储在附加开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数量必须是有确定限制的整数。

function bubbleSort(arr) {     var len = arr.length;     for (var i = 0; i < len; i++) {         for (var j = 0; j < len - 1 - i; j++) {             if (arr[j] > arr[j+1]) {        //相邻元素两两对比                 var temp = arr[j+1];        //元素交换                 arr[j+1] = arr[j];                 arr[j] = temp;             }         }     }     return arr; } 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website