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

大家好，又见面了，我是你们的朋友全栈君。

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);