javascript常用数组排序及二分查找

1. 冒泡排序 基本思路：依次比较相邻的两个数的大小，若大数在前、小数在后，则交换两个数的位置，依次比较直至全部数据从小到大排好序

    function sort_bubble(arr) {
        var len = arr.length;
        for (var i = 0; i < len; i++) {
            for (var j = 0; j < len - (i + 1); j++) {
                if (arr[j] > arr[j + 1]) {
                    var temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
    var arr = [9,3,5,7,2,8];
    console.log(sort_bubble(arr));    // [2, 3, 5, 7, 8, 9]

2. 选择排序 基本思路：通过比较首先选出最小的数放在第一个位置上，然后在其余的数中选出次小数放在第二个位置上，以此类推，直到所有的数成为有序数列。

 　　function sort_select(arr) {
        var len = arr.length, minIndex, temp;
        for (var i = 0; i < len - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }
    var arr = [9,3,5,7,2,8];
    console.log(sort_select(arr));   // [2, 3, 5, 7, 8, 9]

3. 快速排序 基本思路：将序列分成2部分，左边放小数，右边放大数，最后将左边、中间、右边连接起来。

　　　function sort_quick(arr) {
        if (arr.length <= 1) {
            return arr;
        }
        var mid = Math.floor(arr.length/2),
            midNum = arr[mid],
            left = [],
            right = [],
            midArr = [];
        for (var i = 0; i < arr.length; i ++) {
            if (arr[i] < midNum) {
                left.push(arr[i]);
            } else if (arr[i] > midNum) {
                right.push(arr[i]);
            } else {
                midArr.push(arr[i]);
            }
        }
        return sort_quick(left).concat(midArr,sort_quick(right));
    }
     var arr = [9,3,5,7,2,8];
    console.log(sort_quick(arr));   // [2, 3, 5, 7, 8, 9]

4. 二分查找（折半查找）,在从小到大排列的有序数列中查找指定值的位置 基本思路：找到一个中间值，通过与中间值比较，大的放右边，小的放在左边。再在两边中寻找中间值，持续以上操作，直到找到所在位置为止。

    function find_fold(arr,target) {
        var low = 0,high = arr.length - 1;
        while (low <= high) {
            var mid = Math.floor((low + high) / 2);
            if (arr[mid] === target) {
                return mid;
            }
            if (target > arr[mid]) {
                low = mid + 1;
            } else {
                high = mid -1;
            }
        }
        return false;
    }

    var arr = [2,3,4,5,6];
    console.log(find_fold(arr,5));   // 3