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

小鱼儿 2021-09-28 14:54 553阅读 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日 补上对象数组排序 ####