算法

1. 线性搜索

输入一个数组和一个元素，查找该元素是否在这个数组中，如果找到了，返回第一个匹配的元素在数组中的索引，否则返回"not-found"。
（1）第一种常见的写法：

function linearSearch(array, n, x){
    var answer = 'not-found';
    for( var i = 0; i < array.length; i ++){
        if( array[i] == x){
            answer = i;
            break;
        }
    }
    return answer;
}
    ```
（2）第一种写法先对数组中的每一个元素先判断是否越界，再判断是否相等。还可以更高效，即不用判断数组是否越界，给数组最后一项设置一个**信号量**，即我们要查找的数 `x`，
* 第一步，将数组最后一项的值 `array[n]`保存再一个变量 `temp`里，将目标值`x`赋给 `array[n]`；
* 第二步，设置一个变量 `i`， 值为 `0`； 
* 第三步，只要 `array[n] != x`，执行以下操作：  
  A. 将 `i` 自增 `1`.     
  因为第一步的时候将目标值`x`已经赋给了 `array[n]`，所以如果`x`在`array`的范围内一直没有找到，`i` 一直自增，直到 `i == n `，`array [i] == x ` 必定成立，循环结束。
* 第四步，`array[n]` 的值重新赋为 `temp`，目的是检查 `array[n]` 是否真的等于 `x`；
* 第五步，如果 `i < n` 或者 `array [n] = x` ，返回 i 的值作为输出。

function sentinelLinearSearch(array, x){
var n = array.length - 1;
var last = array[n];
array[n] = x;
var i = 0;
var answer = "not-found";
while( array[i] != x ){
i ++ ;
}
array [n] = last;
if ( i < n || array[n] == x){
answer = i;
}
return answer;
}


### 2. 递归

function factorial(n){
if( n==0 ) {
return 1;
} else {
return n * factorial(n-1)
}
}

function recursiveLinearSearch( array, i, x){
var n = array.length - 1;
if ( i > n ) {
return 'not-found';
} else if ( i <= n && array[i] == x) {
return i;
} else {
return recursiveLinearSearch(array, i+1, x);
}
}

#### 3. 二分查找
优点：从包含 n 个元素的数组中执行查找操作仅需 `O(lgn)` 时间。
（1）找到有序数组`array` 中的 `x` ，在任意情况下，我们仅考虑某个子数组，也就是说，介于索引之间的部分数组，将这两个索引记为` p` 和 `r`，
初始时，`p = 0`，`r = n`，即子数组为整个完整数组。

function binarySearch(array, x){
var p = 0, r = array.length - 1;
while ( p <= r ) {
var q = Math.ceil((p + r) / 2);
if( array[q] == x) {
return q;
} else if( array[q] > x) {
r = q - 1;
} else {
p = q + 1;
}
}
return 'not-found';
}

function recursiveBinarySearch(array, p, r, x){
if( p > r ) {
return 'not found';
} else {
var q = Math.ceil(( p + r ) / 2);
if( array[q] == x) {
return q;
} else if ( array[q] > x) {
return recursiveBinarySearch(array, p, q - 1, x);
} else {
return recursiveBinarySearch(array, q + 1, r, x);
}
}
}

### 4. 排序
####（1）选择排序
通过对整体的选择，找到当前数和最小数交换。在一次排序中把最小的元素放在前面。时间复杂度 `O(n^2)`。

交换函数：

function swap (array, a, b){
var temp = array[a];
array[a] = array[b];
array[b] = temp;
}

选择排序：

function selectionSort( array ){
var smallest = 0;
for (var i = 0; i < array.length - 1; i ++) {
smallest = i;
for (var j = i + 1; j < array.length; j ++) {
if (array[j] < array[smallest]) {
smallest = j;
}
}
if (smallest != i){
swap (array, i, smallest);
}
}
return array;
}

对于外层循环的每次迭代，内层循环会执行它的循环体内的所有循环，当 i 等于 0 时，内层循环中 j 从 1 变化到 n - 1，共执行 n - 1 次， 当 i 等于 1 时，内层循环中 j 从 2 变化到 n - 1，共执行 n - 2 次，……，总结可得，内层循环每次执行 n - i 次。内层循环迭代的总数是：
> (n - 1) + (n - 2) + (n -3) + ... + 2 + 1 = n * (n - 1) / 2 = (n^2 - n) / 2
> (n 为数组长度)

省略低阶项 ( -n ) 和常数因子 1/2，我们可以称内层循环的总次数是 `O( n^2 )`。

####（2）插入排序：
不是通过交换位置，而是通过比较找到合适的位置插入元素来达到排序的目的。

function insertionSort( array ){
for (var i = 1; i < array.length; i++){
var target = array[i];
var j = i;
while (j > 0 && target < array[j - 1]){
array[j] = array[j - 1];
j-- ;
}
array[j] = target;
}
return array;
}

因为内部循环的第一次迭代会覆盖 `array[i]`，所以内部迭代开始前先将 `array[i]` 的值保存在 `target` 中。
* 在最好的情况下，即数组一开始就是有序的，内层循环每次迭代 0 次，外层循环迭代 n - 1 次，花费常量时间 `O(n)` 。
* 在最坏的情况下，即数组是逆序的，内层循环每次执行最大次数。外层每迭代 1 次，内层迭代 i 次，外层 i 值从 1 变化到 n - 1，内层的迭代次数构成一个等差数列：
> 1 + 2 + 3 + ... + (n - 2) + (n - 1)  = n * (n -1) / 2        
> (n 为数组长度)

 所以，最坏情况的时间复杂度是 `O(n^2)`。

插入排序和选择排序相比，当数组基本有序时，使用插入排序更好一些。

####（3）归并排序
对于所有情况，它仅有一个 `O(nlgn)` 的时间复杂度。   
  写法一： 

function sort(array, first, last) {
    first = (first === undefined) ? 0 : first
    last = (last === undefined) ? array.length - 1 : last
    if (first >= last) {
        return;
    }
    var middle = Math.floor((first + last) / 2);
    sort(array, first, middle);
    sort(array, middle + 1, last);
    var f = first,
        m = middle,
        i,
        temp;
    while (f <= m && m + 1 <= last) {
        if (array[f] >= array[m + 1]) { // 这里使用了插入排序的思想
            temp = array[m + 1];
            for (i = m; i >= f; i--) {
                array[i + 1] = array[i];
            }
            array[f] = temp;
            m++;
        } else {
            f++;
        }
   }
   return array
}

写法二：

function mergeSort( arr ){
var len = arr.length;
if( len < 2) {
return arr;
} else {
var middle = Math.floor(len / 2);
var left = arr.slice(0, middle);
var 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());
}
}
if(left.length){
result.push(left.shift());
} else if (right.length) {
result.push(right.shift());
}
return result;
}

/* function merge(array){
var p = 0, r = array.length - 1 ;
var q = Math.ceil((p + r) / 2);
var n1 = q - p, n2 = r - q;
var array1 = array.slice(p, q),
array2 = array.slice(q, r + 1);
array1[n1] = Math.max(...array1) + 100;
array2[n2 + 1] = Math.max(...array2) + 100;
var i = j = 0;
for(var k = p; k <= r; k++){
if(array1[i] <= array2[j]){
array[k] = array1[i];
i++;
} else {
array[k] = array2[j];
j++;
}
}
return array;
} */


####（4）快速排序
快速排序也采用分治模式，与归并排序的区别在于：
* 快速排序按照原址工作；
* 快排的最坏运行时间是 `O(n^2)`，平均运行时间是 `O(nlgn) `。

function quickSort(array) {
if (arr.length <= 1) {
return arr;
}
　var pivotIndex = Math.floor(arr.length / 2);
　var pivot = arr.splice(pivotIndex, 1)[0];
　var left = [];
　var right = [];
　for (var i = 0; i < arr.length; i++){
　　　if (arr[i] < pivot) {
　　　　　left.push(arr[i]);
　　　} else {
　　　　　right.push(arr[i]);
　　　}
　}
　return quickSort(left).concat([pivot], quickSort(right));
}


####（5）堆排序
堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

function heapAdjust(array, start, end){
var temp = array[start];
for(var i = 2 * start + 1; i <= end; i = 2){
//左右孩子的节点分别为2i+1,2*i+2
//选择出左右孩子较小的下标
if(i < end && array[i] < array[i + 1]){
i++;
}
if(temp >= array[i]){
break;
}
array[start] = array[i]; //将子节点上移
start = i; //下一轮筛选
}
array[start] = temp; //插入正确的位置
}

function heapSort(array){
for(var i=array.length/2; i>=0; i--) {
heapAdjust(array, i, array.length-1);
}
for(var i=array.length-1; i>=0; i--) {
swap(array, 0, i);
heapAdjust(array, 0, i-1);
}
return array;
}

function swap (array, a, b){
var temp = array[a];
array[a] = array[b];
array[b] = temp;
}


####（6）希尔排序
希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

/**
* 希尔排序的一趟插入
* @param array 待排数组
* @param d 增量
*/
function shellInsert(array, d){
for(var i = d; i < array.length; i++) {
var temp = array[i];
for(var j = i; j >=d; j -= d){
if (array[j] < array[j - d]) {
array[j] = array[j - d];
} else {
break;
}
}
array[j] = temp;
}
}

function sellSort(array){
var d = Math.floor(array.length / 2);
if (array.length <= 1) {
return array;
}
while(d >= 1) {
shellInsert(array, d);
d =Math.floor(d / 2);
}
return array;
}

---
参考资料：
[bubkoo 的博客](http://bubkoo.com/2014/01/15/sort-algorithm/merge-sort/)
[MERGE SORT 动画演示](http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html)
[快速排序](http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html)
[面试中的 10 大排序算法总结](http://www.codeceo.com/article/10-sort-algorithm-interview.html)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,793评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,567评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,342评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,825评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,814评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,680评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,033评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,687评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,175评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,668评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,775评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,419评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,020评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,978评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,206评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,092评论 2赞 351
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,510评论 2赞 343

推荐阅读更多精彩内容

  • （转）八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    蚁前阅读 5,164评论 0赞 52
  • 八大排序算法 (转载)
    概述：排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    每天刷两次牙阅读 3,727评论 0赞 15
  • 常见的排序算法
    总结一下常见的排序算法。 排序分内排序和外排序。内排序:指在排序期间数据对象全部存放在内存的排序。外排序:指在排序...
    jiangliang阅读 1,323评论 0赞 1
  • 诗|十万光年之外
    假设 时光搁浅在十万光年之外 // 那里的星辰 是在永恒地转动还是永恒地静止 到达那里的光 是永堕黑暗还是分解为原...
    独我见青山阅读 1,032评论 22赞 15
  • 道光二十四年十月廿一日
    忌傲气 余平生科名极为顺遂，惟小考七次始售。然每次不进，未尝敢出一怨言，但深愧自己试场之诗文太丑而已。至今思之，如...
    读小字阅读 486评论 0赞 2