品一品编程 --- 5

问题描述：

实现基于数组的 sort 排序函数

var sort = function(arr) {
    // your code
}

sort([5, 100, 6, 3, -12]) //[-12, 3, 5, 6, 100]

程序如下：

//冒泡排序 O(n^2)

var sort = function(arr) {
    var len = arr.length
    for(var i = 0; i < len-1; i++) {
        for(var j = i+1; j < len; j++) {
            if(arr[i] > arr[j]) {
                var tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp
            }
        }
    }
    return arr
}

//快速排序---优势：原地排序O(n*log2n)

var quickSort = function(arr) {
    function sort(left,right) {
        var high = right;
        var pivot = arr[left];
        if(right > left){
            while(left < right) {
                while(left < right && arr[right] > pivot) {
                    right--;
                };
                arr[left] = arr[right];
                while(left < right && arr[left] < pivot) {
                    left++;
                }
                arr[right] = arr[left];
            }
            arr[left] = pivot;
            sort(0, left);
            sort(left+1, high);
        }
    }
    sort(0,arr.length-1);
    return arr;
}