数据结构与算法

Javascript的数据结构与算法(四)

Posted by 黄成都 on 2016-12-19
Words 1.6k and Reading Time 8 Minutes
Viewed Times

1 排序和搜索算法

1.1 排序算法

1.1.1 冒泡排序

冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。冒泡排序的时间复杂度为O(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//冒泡排序
bubbleSort: function() {
    var self = this;
    function swap(index1, index2) {
        var aux = self.array[index2];
        self.array[index2] = self.array[index1];
        self.array[index1] = aux;
    }
    var length = this.array.length;
    for (var i = 0; i < length; i++) {
        for (var j = 0; j < length - 1 - i; j++) {
            if (this.array[j] > this.array[j + 1]) {
                swap(j, j + 1);
            }
        }
    }
}

1.1.2 选择排序

选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。选择排序的时间复杂度为O(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//选择排序
selectionSort:function(){
    var length = this.array.length;
    var indexMin;
    for(var i = 0; i < length - 1; i++){
        indexMin = i;
        for(var j = i; j < length; j++){
            if (this.array[indexMin] > this.array[j]) {
                indexMin = j;
            }
        }
        if (indexMin !== i) {
            this.swap(indexMin,i);
        } 
    }
}

1.1.3 插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
insertionSort:function(){
    var length = this.array.length;
    var j;
    var temp;
    for(var i = 1; i < length; i++){
        temp = this.array[i];
        j = i;
        while(j > 0 && this.array[j - 1] > temp){
            this.array[j] = this.array[j - 1];
            j--;
        }
        this.array[j] = temp;
    }
}

1.1.4 归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。时间复杂度为O(nlogn)，空间复杂度为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
30
31
32
33
//归并排序
mergeSort:function(){
    function mergeSortRec(array){
        var length = array.length;
        if (length === 1) {
            return array;
        }
        var mid = Math.floor(length/2);
        var left = array.slice(0,mid);
        var right = array.slice(mid,length);
        return merge(mergeSortRec(left),mergeSortRec(right));
    }
    function merge(left,right){
        var result = [];
        var il = 0;
        var ir = 0;
        while(il < left.length && ir < right.length){
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            }else{
                result.push(right[ir++]);
            }
        }
        while(il < left.length){
            result.push(left[il++]);
        }
        while(ir < right.length){
            result.push(right[ir++]);
        }
        return result;
    }
    this.array = mergeSortRec(this.array);
}

1.1.5 快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间负责度为O(n^2)，并且比其他负责度为O(n^2)的排序算法要好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//快速排序，参考http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
quickSort:function(){
    function sort(array){
        if (array.length <= 1) {
            return array;
        }
        var pivotIndex = Math.floor(array.length/2);
        var pivot = array.splice(pivotIndex,1)[0];
        var left = [];
        var right = [];
        for(var i = 0; i < array.length; i++){
            if (array[i] < pivot) {
                left.push(array[i]);
            }else{
                right.push(array[i]);
            }
        }
        return sort(left).concat([pivot],sort(right));
    }

    this.array = sort(this.array);
}

1.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
function ArrayList() {
    this.array = [];
}
ArrayList.prototype = {
    constructor: ArrayList,
    insert: function(item) {
        this.array.push(item);
    },
    toString: function() {
        return this.array.join();
    },
    swap: function(index1, index2) {
        var aux = this.array[index2];
        this.array[index2] = this.array[index1];
        this.array[index1] = aux;
    },
    //冒泡排序
    bubbleSort: function() {
        var length = this.array.length;
        for (var i = 0; i < length; i++) {
            for (var j = 0; j < length - 1 - i; j++) {
                if (this.array[j] > this.array[j + 1]) {
                    this.swap(j, j + 1);
                }
            }
        }
    },
    //选择排序
    selectionSort: function() {
        var length = this.array.length;
        var indexMin;
        for (var i = 0; i < length - 1; i++) {
            indexMin = i;
            for (var j = i; j < length; j++) {
                if (this.array[indexMin] > this.array[j]) {
                    indexMin = j;
                }
            }
            if (indexMin !== i) {
                this.swap(indexMin, i);
            }
        }
    },
    //插入排序
    insertionSort: function() {
        var length = this.array.length;
        var j;
        var temp;
        for (var i = 1; i < length; i++) {
            temp = this.array[i];
            j = i;
            while (j > 0 && this.array[j - 1] > temp) {
                this.array[j] = this.array[j - 1];
                j--;
            }
            this.array[j] = temp;
        }
    },
    //归并排序
    mergeSort: function() {
        function mergeSortRec(array) {
            var length = array.length;
            if (length === 1) {
                return array;
            }
            var mid = Math.floor(length / 2);
            var left = array.slice(0, mid);
            var right = array.slice(mid, length);
            return merge(mergeSortRec(left), mergeSortRec(right));
        }

        function merge(left, right) {
            var result = [];
            var il = 0;
            var ir = 0;
            while (il < left.length && ir < right.length) {
                if (left[il] < right[ir]) {
                    result.push(left[il++]);
                } else {
                    result.push(right[ir++]);
                }
            }
            while (il < left.length) {
                result.push(left[il++]);
            }
            while (ir < right.length) {
                result.push(right[ir++]);
            }
            return result;
        }
        this.array = mergeSortRec(this.array);
    },
    //快速排序，参考http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
    quickSort:function(){
        function sort(array){
            if (array.length <= 1) {
                return array;
            }
            var pivotIndex = Math.floor(array.length/2);
            var pivot = array.splice(pivotIndex,1)[0];
            var left = [];
            var right = [];
            for(var i = 0; i < array.length; i++){
                if (array[i] < pivot) {
                    left.push(array[i]);
                }else{
                    right.push(array[i]);
                }
            }
            return sort(left).concat([pivot],sort(right));
        }

        this.array = sort(this.array);
    }
};

排序方法验证：

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
function createNonSortedArray(size) {
    var array = new ArrayList();
    for (var i = size; i > 0; i--) {
        //(function(i) {
        array.insert(i);
        //})(i);
    }
    return array;
}
//冒泡排序
var array = createNonSortedArray(5);
console.log(array.toString());
array.bubbleSort();
console.log(array.toString());
//选择排序
console.log(array.toString());
array.selectionSort();
console.log(array.toString());
//插入排序
console.log(array.toString());
array.insertionSort();
console.log(array.toString());
//归并排序
console.log(array.toString());
array.mergeSort();
console.log(array.toString());
//快速排序
console.log(array.toString());
array.quickSort();
console.log(array.toString());

源码地址

Javascript的数据结构与算法(三)源码

...

...

00:00
00:00
FEATURED TAGS
数据结构与算法