Array.sort()相关
2017-08-04 本文已影响38人
清水龙虾
问题描述
用Array.sort()在不传入自定义比较函数的情况下，排序结果是按位比较的结果，而不是预期的按数字大小排列的结果
var a = [1,2,11].sort()
//a = [1, 11, 2]
问题原因
The sort() method sorts the elements of an array in place and returns the array. The sort is not necessarily stable. The default sort order is according to string Unicode code points.
arr.sort([compareFunction]) compareFunction Optional. Specifies a function that defines the sort order. If omitted, the array is sorted according to each character's Unicode code point value, according to the string conversion of each element.
sort方法如果不提供compareFunction比较函数，那么就把数组中的元素转成字符串后按字符的Unicode码点进行比较。
More
于是，去翻了v8的源码，发现果不其然，另外还发现，v8的数组排序用了两个算法：
当需排序的数组长度<=10时，使用插入排序；
当需排序的数组长度>10时，使用快速排序。
插入排序：
插入排序是将一个记录插入到已经排好序的数组中，从而获得一个新的排好序的、数组长度加1的有序列表。
- step1: 从第一个元素开始，该元素可认为已被排完序；
- step2: 取出下一个元素(a)，并从已排完的有序数列中从前向后扫描(b)；
- step3: 若遍历到的已排序数列的当前元素(b)大于有序数列的下个元素(a)，则将b向后移动一位；
- step4: 重复step3，直至a>=b；
- step5:将新元素a放置到b元素后；
- step6: 重复step2-step5;
算法分析：
- 最佳情况：输入数组按升序排列， T(n) = O(n)
- 最差情况：输入数组按降序排列， T(n) = O(n2)
- 平均情况：T(n) = O(n2)
function insertSort(arr){
var len = arr.length
for(var i = 1; i < length; i++){
var element = arr[i];
for(var j = i - 1; j >= 0; j--){
var temp = arr[j]
var isGreater = temp > element
if(isGreater){
arr[ j+1 ] = temp
}else{
break
}
}
arr[ j+1 ] = element
}
return arr
}
快速排序：
- step1: 在数据集中，选择一个元素作为'基准'(pivot )；
- step2: 所有小于pivot元素都移至pivot左侧，所有大于pivot元素都移至pivot右侧；
- step3: 对pivot左右两侧子集都不断重复step1、step2，直至子集只剩一个元素为止。
附录
v8数组排序相关代码：
function InnerArraySort(array, length, comparefn) {
// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
if (!IS_CALLABLE(comparefn)) {
comparefn = function (x, y) {
if (x === y) return 0;
if (%_IsSmi(x) && %_IsSmi(y)) {
return %SmiLexicographicCompare(x, y);
}
x = TO_STRING(x);
y = TO_STRING(y);
if (x == y) return 0;
else return x < y ? -1 : 1;
};
}
function InsertionSort(a, from, to) {
for (var i = from + 1; i < to; i++) {
var element = a[i];
for (var j = i - 1; j >= from; j--) {
var tmp = a[j];
var order = comparefn(tmp, element);
if (order > 0) {
a[j + 1] = tmp;
} else {
break;
}
}
a[j + 1] = element;
}
};
function GetThirdIndex(a, from, to) {
var t_array = new InternalArray();
// Use both 'from' and 'to' to determine the pivot candidates.
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {
t_array[j] = [i, a[i]];
j++;
}
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}
function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
// >> 右移运算符； value >> num 表明将value向右移动num位； value >> 1 = value / 2
third_index = from + ((to - from) >> 1);
}
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
} // v0 <= v1.
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0) {
// v0 <= v2 < v1
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
// From low_end to i are elements equal to pivot.
// From i to high_start are elements that haven't been compared yet.
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
var order = comparefn(element, pivot);
if (order < 0) {
a[i] = a[low_end];
a[low_end] = element;
low_end++;
} else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0) {
element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
}
}
if (to - high_start < low_end - from) {
QuickSort(a, high_start, to);
to = low_end;
} else {
QuickSort(a, from, low_end);
from = high_start;
}
}
};
// Copy elements in the range 0..length from obj's prototype chain
// to obj itself, if obj has holes. Return one more than the maximal index
// of a prototype property.
function CopyFromPrototype(obj, length) {
var max = 0;
for (var proto = %object_get_prototype_of(obj); proto;
proto = %object_get_prototype_of(proto)) {
var indices = IS_PROXY(proto) ? length : %GetArrayKeys(proto, length);
if (IS_NUMBER(indices)) {
// It's an interval.
var proto_length = indices;
for (var i = 0; i < proto_length; i++) {
if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
obj[i] = proto[i];
if (i >= max) { max = i + 1; }
}
}
} else {
for (var i = 0; i < indices.length; i++) {
var index = indices[i];
if (!HAS_OWN_PROPERTY(obj, index) && HAS_OWN_PROPERTY(proto, index)) {
obj[index] = proto[index];
if (index >= max) { max = index + 1; }
}
}
}
}
return max;
};
// Set a value of "undefined" on all indices in the range from..to
// where a prototype of obj has an element. I.e., shadow all prototype
// elements in that range.
function ShadowPrototypeElements(obj, from, to) {
for (var proto = %object_get_prototype_of(obj); proto;
proto = %object_get_prototype_of(proto)) {
var indices = IS_PROXY(proto) ? to : %GetArrayKeys(proto, to);
if (IS_NUMBER(indices)) {
// It's an interval.
var proto_length = indices;
for (var i = from; i < proto_length; i++) {
if (HAS_OWN_PROPERTY(proto, i)) {
obj[i] = UNDEFINED;
}
}
} else {
for (var i = 0; i < indices.length; i++) {
var index = indices[i];
if (from <= index && HAS_OWN_PROPERTY(proto, index)) {
obj[index] = UNDEFINED;
}
}
}
}
};
function SafeRemoveArrayHoles(obj) {
// Copy defined elements from the end to fill in all holes and undefineds
// in the beginning of the array. Write undefineds and holes at the end
// after loop is finished.
var first_undefined = 0;
var last_defined = length - 1;
var num_holes = 0;
while (first_undefined < last_defined) {
// Find first undefined element.
while (first_undefined < last_defined &&
!IS_UNDEFINED(obj[first_undefined])) {
first_undefined++;
}
// Maintain the invariant num_holes = the number of holes in the original
// array with indices <= first_undefined or > last_defined.
if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
num_holes++;
}
// Find last defined element.
while (first_undefined < last_defined &&
IS_UNDEFINED(obj[last_defined])) {
if (!HAS_OWN_PROPERTY(obj, last_defined)) {
num_holes++;
}
last_defined--;
}
if (first_undefined < last_defined) {
// Fill in hole or undefined.
obj[first_undefined] = obj[last_defined];
obj[last_defined] = UNDEFINED;
}
}
// If there were any undefineds in the entire array, first_undefined
// points to one past the last defined element. Make this true if
// there were no undefineds, as well, so that first_undefined == number
// of defined elements.
if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
// Fill in the undefineds and the holes. There may be a hole where
// an undefined should be and vice versa.
var i;
for (i = first_undefined; i < length - num_holes; i++) {
obj[i] = UNDEFINED;
}
for (i = length - num_holes; i < length; i++) {
// For compatibility with Webkit, do not expose elements in the prototype.
if (i in %object_get_prototype_of(obj)) {
obj[i] = UNDEFINED;
} else {
delete obj[i];
}
}
// Return the number of defined elements.
return first_undefined;
};
if (length < 2) return array;
var is_array = IS_ARRAY(array);
var max_prototype_element;
if (!is_array) {
// For compatibility with JSC, we also sort elements inherited from
// the prototype chain on non-Array objects.
// We do this by copying them to this object and sorting only
// own elements. This is not very efficient, but sorting with
// inherited elements happens very, very rarely, if at all.
// The specification allows "implementation dependent" behavior
// if an element on the prototype chain has an element that
// might interact with sorting.
max_prototype_element = CopyFromPrototype(array, length);
}
// %RemoveArrayHoles returns -1 if fast removal is not supported.
var num_non_undefined = %RemoveArrayHoles(array, length);
if (num_non_undefined == -1) {
// There were indexed accessors in the array.
// Move array holes and undefineds to the end using a Javascript function
// that is safe in the presence of accessors.
num_non_undefined = SafeRemoveArrayHoles(array);
}
QuickSort(array, 0, num_non_undefined);
if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
// For compatibility with JSC, we shadow any elements in the prototype
// chain that has become exposed by sort moving a hole to its position.
ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
}
return array;
}
