03月12, 2017

快速排序

今天来实现一下快速排序

function quickSort(array){
    function sort(prev, numsize){
        var nonius = prev;
        var j = numsize -1;
        var flag = array[prev];
        if ((numsize - prev) > 1) {
            while(nonius < j){
                for(; nonius < j; j--){
                    if (array[j] < flag) {
                        array[nonius++] = array[j]; //a[i] = a[j]; i += 1;
                        break;
                    };
                }
                for( ; nonius < j; nonius++){
                    if (array[nonius] > flag){
                        array[j--] = array[nonius];
                        break;
                    }
                }
            }
            array[nonius] = flag;
            sort(0, nonius);
            sort(nonius + 1, numsize);
        }
    }
    sort(0, array.length);
    return array;
}
console.log(quickSort([8,10,6,4,22,1,3,4,5,55,5,99,0,22,44,77,5,7,3,3]))

那么在javascript中,一般都是 arr.sort() 这么用的,那么我们怎么把我们的代码改成这种形式呢?

Array.prototype.quicksort = function(func) {
    var array = this;
    function sort(prev, numsize){
        var nonius = prev;
        var j = numsize -1;
        var flag = array[prev];
        if ((numsize - prev) > 1) {
            while(nonius < j){
                for(; nonius < j; j--){
                    if (array[j] < flag) {
                        array[nonius++] = array[j]; //a[i] = a[j]; i += 1;
                        break;
                    };
                }
                for( ; nonius < j; nonius++){
                    if (array[nonius] > flag){
                        array[j--] = array[nonius];
                        break;
                    }
                }
            }
            array[nonius] = flag;
            sort(0, nonius);
            sort(nonius + 1, numsize);
        }
    }
    sort(0, array.length);
    return array;
}
console.log([7,5,8,9,5,4,2].quicksort())

上面我一直都预留的func 没有使用,在javascript 中func 的返回值可以决定两个交换对象是否交换,从而实现倒排和正排,那么我们又该如何实现呢?

本文链接:http://www.gyblog.cn/post/sort.html

-- EOF --

Comments