学习js数据结构与算法8—排序与搜索算法

排序和搜索算法

排序算法

    // 排序
    function ArrayList() {
        var arr = [];

        this.insert = function(item) {
            arr.push(item);
        };

        this.toString = function() {
            return arr.join();
        };

        // 冒泡排序
        // 从运行时间的角度来看，冒泡排序是最差的一个，复杂度O(n^2)
        this.bubbleSort = function() {
            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]) {
                        swap(j, j + 1);
                    }
                }
            }
        };
        function swap(m, n) {
            var tmp = arr[m];
            arr[m] = arr[n];
            arr[n] = tmp;
        }
        
        // 选择排序
        // 思路：找到数据中的最小值并将其放在第一位，接着找到第二小的放在第二位，以此类推
        // 时间复杂度也是O(n^2)
        this.selectionSort = function() {
            var len = arr.length,
                indexMin;

            for (var i = 0; i < len - 1; i++) {
                indexMin = i;
                for (var j = i; j < len; j++) {
                    if (arr[indexMin] > arr[j]) {
                        indexMin = j;
                    }
                }
                if (i !== indexMin) {
                    swap(i, indexMin);
                }
            }
        }

        // 插入排序
        // 排序小型数组时，比冒泡和选择排序性能要好
        this.insertionSort = function() {
            var len = arr.length,
                j, tmp;

            for (var i = 1; i < len; i++) {
                j = i;
                tmp = arr[i];
                while (j > 0 && arr[j - 1] > tmp) {
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[j] = tmp;
            }
        }

        // 归并排序
        // 是第一个可以被实际使用的排序算法，性能比前三个算法好，复杂度为O(nlog^n)
        // 归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，
        // 接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组
        this.mergeSort = function() {
            arr = mergeSortRec(arr);
        };
        var mergeSortRec = function(arr) {
            var len = arr.length;
            if (len === 1) {
                return arr;
            }

            var mid = Math.floor(len / 2),
                left = arr.slice(0, mid),
                right = arr.slice(mid, len);

            return merge(mergeSortRec(left), mergeSortRec(right));
        };
        var merge = function(left, right) {
            var res = [],
                l = 0,
                r = 0;

            while (l < left.length && r < right.length) {
                if (left[l] < right[r]) {
                    res.push(left[l++]);
                } else {
                    res.push(right[r++]);
                }
            }

            while (l < left.length) {
                res.push(left[l++]);
            }

            while (r < right.length) {
                res.push(right[r++]);
            }
            return res;
        };
        
        // 快速排序
        // 快排是最常用的排序算法，复杂度为O(nlog^n),且它的性能通常比其他的复杂度为O(nlog^n)的要好
        // 也使用分治的方法，将原始数组分成较小的数组
        this.quickSort = function() {
            quick(arr, 0, arr.length - 1);
        };
        var quick = function(arr, left, right) {
            var index;

            if (arr.length > 1) {
                index = partition(arr, left, right);

                if (left < index - 1) {
                    quick(arr, left, index - 1);
                }

                if (index < right) {
                    quick(arr, index, right);
                }
            }
        };
        var partition = function(arr, left, right) {
            var pivot = arr[Math.floor((left + right) / 2)],
                i = left,
                j = right;

            while (i <= j) {
                while (arr[i] < pivot) {
                    i++;
                }
                while (arr[j] > pivot) {
                    j--;
                }
                if (i <= j) {
                    swapQuick(arr, i, j);
                    i++;
                    j--;
                }
            }
            return i;
        };

        function swapQuick(arr, m, n) {
            var tmp = arr[m];
            arr[m] = arr[n];
            arr[n] = tmp;
        }
        
        
        // 搜索算法
        // 1.顺序搜索
        // 将每一个数据结构中的元素和我们要找的元素作比较。顺序搜索是最低效的一种搜索算法
        this.lowSearch = function(item) {
            for (var i = 0; i < arr.length; i++) {
                if (item === arr[i]) {
                    return i;
                }
            }
            return -1;
        };


        //2.二分搜索
        /* 
            这个算法要求被搜索的数据结构已排序
            步骤：
                1.选择数组的中间值
                2.如果选中的值是待搜索值，那么算法是执行完毕
                3.如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找
                4.如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找
        */
        this.binarySearch = function(item) {
            this.quickSort();
            
            var low = 0,
                high = arr.length - 1,
                mid, ele;
                
            while (low <= high) {
                mid = Math.floor((low + high) / 2);
                ele = arr[mid];
                
                if (ele < item) {
                    low = mid + 1;
                } else if (ele > item) {
                    high = mid - 1;
                } else {
                    return mid;
                }
            }
            
            return -1;
        };
    }

    // 创建未排序的数组
    function createNonSortedArray(size) {
        var arr = new ArrayList();
        for (var i = size; i > 0; i--) {
            arr.insert(i);
        }
        return arr;
    }

    var arr = createNonSortedArray(5);
    console.log(arr.toString());
    // arr.bubbleSort();
    // arr.selectionSort();
    // arr.insertionSort();
    // arr.mergeSort();
    arr.quickSort();
    console.log(arr.toString());