js数组排序---自定义快速排序-蒲公英云

js数组排序---自定义快速排序

小鱼儿 2021-09-28 14:54 653阅读 0赞

文章目录

- - js数组自带的sort方法
  - 快速排序
  - - 测试一下效率
    - 2020年04月26日补上对象数组排序

js数组自带的sort方法

var arr = [3, 4, 2, 1];
        arr.sort();
        console.log(arr);

默认进行递增排序

(4) [1, 2, 3, 4]

sort方法可以接收一个参数，用来自定义排序规则

arr.sort(function(val1, val2){ 
            //return val1 - val2; 默认
            return val2 - val1;//倒序。根据结果大于0、小于0、等于零做判断
        });

如果数组元素为非数字类型，必须要手动指定排序规则，否则可能会产生诡异的结果。
比如，两个字符串相减结果为NaN，这回导致排序不生效。

当元素为对象时，例

var arr = [{ "a":1},{ "a":311},{ "a":2}];
        arr.sort(function(val1, val2){ 
            return val2.a - val1.a;
        });
        console.log(arr);

经查询资料得知，sort方法竟然是用的冒泡排序。。。换一个效率高些的吧。

快速排序

Array.prototype.sortq = function(_compare){ 
    var _this = this;
    if(this.length == 0)
        return;            
    var compare = _compare || function(val1, val2){ 
        return val1 - val2 > 0 ? false : true;
    };
    function quickSort(src){ 
        _quickSort(src, 0, src.length - 1);
    }
    function _quickSort(src, left, right){ 
        var key = src[left];
        var keyIndex = left;
        var i = left;
        var j = right;
        while(i < j){ 
            while(i < j){ 
                if(compare(_this[j], _this[keyIndex])){ 
                    src[keyIndex] = src[j];
                    src[j] = key;
                    keyIndex = j;
                    break;
                }
                j--;
            }
            while(i < j){ 
                if(compare(_this[keyIndex], _this[i])){ 
                    src[keyIndex] = src[i];
                    src[i] = key;
                    keyIndex = i;
                    break;
                }
                i++;
            }
        }
        if(left != right){ 
            if(keyIndex != left)
                _quickSort(src, left, keyIndex - 1);
            if(keyIndex != right)
                _quickSort(src, keyIndex + 1, right);
        }    
    }
    quickSort(this);
}

测试一下效率

var arr1 = new Array();
        for(var i = 0; i < 1000000; i++)
            arr1.push(Math.random());
        var dat1 = new Date();
        arr1.sort();
        var dat2 = new Date();
        console.log(dat2.getTime() - dat1.getTime());
        var arr2 = new Array();
        for(var i = 0; i < 1000000; i++)
            arr2.push(Math.random());
        var dat3 = new Date();
        arr2.sortq();
        var dat4 = new Date();
        console.log(dat4.getTime() - dat3.getTime());

输出

7237
292

效率提升了20多倍。虽然还有更高效率的算法，不过这个也够用了。

2020年04月26日补上对象数组排序

var arr3 = new Array();
        for(var i = 0; i < 40; i++){ 
            arr3.push(
                { 
                    aa: Math.random()
                }
            );
        }
        arr3.sortq(function(val1, val2){ 
            return val1.aa - val2.aa > 0 ? false : true;
        });
        console.log(arr3);