偶然间翻出了大学时的课本数据结构，毕业那会，好多书都丢掉了，唯有c语言和数据结构，我放进了行李箱。这是我程序生涯的开始，我想，我将会一直珍藏它们。

好了，不再自我感动了。作为前端工程师，技能一直被低估，但又有着全栈的要求。看似矛盾的话语，或多或少透露着一丝无奈。既然如此，那么F2E们，奔跑起来吧，也许你需要的只是一本数据结构！

咳～咳（多么生硬的过渡😏），那么咱们就从排序算法说起吧！

一、js中sort排序

首先，我们不得不提一下js中的sort排序：

1
2
3
4
5
6
7
function systemSort(array) {
    return array.sort(function(a, b) {
        return a - b;
    });
}

systemSort([4,2,6,9,1,11,3,3]);

应用了数组的sort方法，很简单，这里就不啰嗦了，继续往下走～

二、插入排序

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的文件中的适当位置，直到全部记录插入完成为止。

1.直接插入排序；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var a = [2,4,5,49,63,4,5,55,2,4,43];
function insertSort(arr) {
  for(var i = 1, j; i < arr.length; i++) {
    j = i;
    v= arr[j];
    while(arr[j-1] > v) {
        arr[j] = arr[j-1];
        j--;
        if(j === 0) {
            break;
        }
    }
    arr[j] = v;
  }
  return arr;
}
insertSort(a)//[2,2,4,4,4,5,5,43,49,55,63]

2.希尔排序：缩小增量排序；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function shellSort(arr) {
    var N = arr.length;
    var h = 1;
    var i, j, v;
    while (h < N / 3) {
        h = 3 * h + 1; // ①
    }
    while (h >= 1) {
        for (i = 1; i < arr.length; i++) {
            j = i;
            v = arr[j];
            while (j > 0 && arr[j - 1] > v) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = v;
        }
        h = (h - 1) / 3; // 从①可以保证，肯定能除尽的
    }
    return arr;
}

三、交换排序

两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

1.起泡排序；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort(arr) {
    var n = arr.length,
        i = 0,
        temp;
    while(--n) {
        while (i < n) {
            if(arr[i] > arr[i+1]) {
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
            i++;
        }
        i = 0;
    }
    return arr;
}

2.快速排序；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function quickSort(arr){
    //如果数组<=1,则直接返回
    if(arr.length<=1){return arr;}
    var pivotIndex=Math.floor(arr.length/2);
    //找基准，并把基准从原数组删除
    var pivot=arr.splice(pivotIndex,1)[0];
    //定义左右数组
    var left=[];
    var right=[];

    //比基准小的放在left，比基准大的放在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));
}

偶然间看到了这一例（参考地址），也挺不错：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var a = [2,4,5,49,63,4,5,55,2,4,43];
function quicksort(arr)
{
    if (arr.length == 0)
        return [];
    var left = new Array();
    var right = new Array();
    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 quicksort(left).concat(pivot, quicksort(right));
}
console.log(quicksort(a));

四、选择排序

每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

1.直接选择排序

1
2
3
4
5
6
7
8
9
10
11
function selectionSort(arr) {
    var ret = [],
        min,
        i;
    while(arr.length) {
        min  = Math.min.apply(null, arr);
        ret.push(min);
        arr.splice(arr.indexOf(min), 1);
    }
    return ret;
}

2.归并排序

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
34
35
36
function mergetSort(arr) {
    if(arr.length === 1) {
        return arr;
    }
    var leftArr = arr.slice(0, Math.floor(arr.length / 2));
    var rightArr = arr.slice(leftArr.length);
    // 递归
    return merge(mergetSort(leftArr), mergetSort(rightArr));
    // 合并有序序列
    function merge(arrLeft, arrRight) {
        var indexLeft = 0,
            indexRight = 0,
            sl = arrLeft.length,
            sr = arrRight.length,
            ret = [];
        while(true) {
            if(indexLeft < sl && indexRight < sr) {
                if(arrLeft[indexLeft] < arrRight[indexRight]) {
                    ret.push(arrLeft[indexLeft]);
                    indexLeft++;
                     } else {
                    ret.push(arrRight[indexRight]);
                    indexRight++;
                }
            } else {
                if(indexLeft < indexRight) {
                    ret = ret.concat(arrLeft.slice(indexLeft));
                } else {
                    ret = ret.concat(arrRight.slice(indexRight));
                }
                break;
            }
        }
        return ret;
    }
}

说了这么多，最后送大伙一个排序动画，体验一下这些排序算法的迷人魅力。
排序动画演示，猛戳这里！！！。
sort

参考文章：
http://www.2cto.com/kf/201412/364945.html
http://www.stoimen.com/blog/2010/06/11/friday-algorithms-quicksort-difference-between-php-and-javascript/
http://www.cnblogs.com/idche/archive/2011/02/16/1956397.html