返回

Javascript 中的数组排序算法总结

javascript 中的数组排序算法主要有：冒泡排序、插入排序、快速排序、递归排序。

下满的这些例子都是各个排序算法的具体实现。

1. 冒泡排序

最简单的排序算法了，没什么可说的。
时间复杂度：O(N^2)

具体代码如下：

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

2. 插入排序

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertionSort(arr) {
    var tmp;
    for (var i = 1; i < arr.length; i++) {
        tmp = arr[i];
        for (var j = i - 1; j >= 0; j--) {
            if (arr[j] > tmp) {
                arr[j + 1] = arr[j];
            }else {
                break;
            }
        } 
        arr[j + 1] = tmp;
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertIntoArray(arr, elem) {
    var l = 0, 
        r = arr.length - 1,
        m;
    while (l <= r) {
        m = Math.floor((r - l + 1) / 2) + l;
        if (arr[m] > elem) {
            r = m - 1;
        } else if (arr[m] < elem) {
            l = m + 1;
        } else {
            l = m;
            break;
        }
    }

    arr.splice(l, 0, elem);
    return arr;
}

3. 快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quickSort (arr) {
     if (arr. length <= 1) {
          return arr;
     }
     var middleIndex = Math.floor(arr.length / 2);
     var middle = arr.splice(middleIndex, 1)[0];
     var left = [], right = [];
     for (var i = 0; i < arr.length; i++) {
          if (arr[i] < middle) {
               left.push(arr[i]);
          } else {
               right.push(arr[i]);
          }
     }
     return arguments.callee(left).concat([middle], arguments.callee(right));
}

4. 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function mergeSort(items) {
    if (items.length === 1) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left = items.slice(0, middle),
        right = items.slice(middle);
    return merge(mergeSort(left), mergeSort(right));

    function merge(left, right) {
        var result = [],
            il = 0,
            ir = 0;
        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
        return result.concat(left.slice(il)).concat(right.slice(ir));
    }
}