js实现二分法查找、快速排序算法

二分查找法

function binary_search(source_arr, target){

    var len = source_arr.length,

        start = 0,

        end = len-1,

        middle,middle_val;

    while(start <= end){

        middle = parseInt((start + end) / 2);

        middle_val = source_arr[middle];

        if(middle_val == target){

            return middle;

        }else if(middle_val > target){

            end = middle - 1;

        }else{

            start = middle + 1;

        }

    }

    return -1;

}

时间复杂度： 2^x = n 所以时间复杂度为log2n,空间复杂度为n；

哈希表查找(none)

快速排序

function quick_sort(source_arr, left, right){

    if(left < right){

        var key = source_arr[left],

            start = left,

            end = right;

        while(start < end){

            while(start < end && source_arr[end] > key){

                end --;

            }

            source_arr[start] = source_arr[end];

            while(start < end && source_arr[start] < key){

                start ++;

            }

            source_arr[end] = source_arr[start];

        }

        source_arr[start] = key;

        quick_sort(source_arr, left, start -1);

        quick_sort(source_arr, start+1, right);

    }    

}

时间复杂度log2n~ n*n （n + n/2 + n/2 + n/4 + n/4 + n/4 + n/4.....）

B树、二叉树遍历

js实现二分法查找、快速排序算法

原文：http://mounting.blog.51cto.com/6316625/1636552