JavaScript 排序

常见排序算法比如:

  • 冒泡排序(属于交换排序)
  • 快速排序(属于交换排序)
  • 直接插入排序(属于插入排序)
  • 希尔排序(属于插入排序)
  • 简单选择排序(属于选择排序)
  • 堆排序(属于选择排序)
  • 归并排序
  • 基数排序

下面通过 JavaScript 实现各个排序算法。

冒泡排序

冒泡排序应该是印象中接触最早的排序算法。冒泡算法核心是顺序比较相邻的两个元素,在升序排列下,如果元素 i 大于 元素 i + 1,则交换两者,第一轮比较到最后一个元素,第二轮比较到倒数第二个元素。直到只剩下第一个元素,比较完毕。

中间有一个优化是,如果某轮比较没有进行交换,则认为数组已经有序,不需要进行下一轮比较。

另一个“改进”版本——双向冒泡,为了减少来回的次数。但实际并没有减少比较次数,反而申请了更多的内存空间。

function sortBubble(array) {
	var i, j = array.length - 1, tmp, no_change;
	while (j > 0) {
		no_change = true;
		for (i = 0; i < j; i++) {
			if (array[i] > array[i + 1]) {
				tmp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = tmp;
				no_change = false;
			}
		}
		if (no_change) {
			break;
		}
	}
}
var ar_score = [10, 9, 8, 7, 6];
sortBubble(ar_score);

快速排序

快速排序通过设置哨兵,把小于和大于哨兵的数组元素分别组织为数组,再通过递归对两个数组进行快速排序,直到每个数组不能分解(只有一个数组元素)。

<script type="text/javascript">
function sortQuick(array) {
	var i = 0, j = array.length - 1, index = 0, guard = array[index];
	var ar_left, ar_right;
	while (j > i) {
		while (j > index) {
			if (array[j] < guard) {
				array[index] = array[j];
				array[j] = guard;
				index = j;
				break;
			}
			j--;
		}
		while (i < index) {
			if (array[i] > guard) {
				array[index] = array[i];
				array[i] = guard;
				index = i;
				break;
			}
			i++;
		}
	}

	if (i > 0) {
		ar_left = array.slice(0, i);
		sortQuick(ar_left);
		array.splice.apply(array, [0, i].concat(ar_left));
	}

	if (j < array.length - 1) {
		j++;
		ar_right = array.slice(j);
		sortQuick(ar_right);
		array.splice.apply(array, [j, array.length - j].concat(ar_right));
	}
}

var ar_score = [10, 9, 8, 7, 6];
sortQuick(ar_score);
</script>

[10, 9, 8, 7, 6] 交换步骤

  • 第一次排序 [6, 9, 8, 7, 10]
  • 分拆为 [6, 9, 8, 7]、[10], 左侧数组在进行快速排序、右侧数组不需要进行排序
  • 第二次排序 [6, 9, 8, 7] 、[10], 分拆为 [6]、[9, 8, 7]、[10]
  • 第三次排序 [6]、[7, 8, 9]、[10]
  • 第四次排序 [6]、[7, 8], [9], [10]
  • 第五次排序 [6]、[7], [8], [9]、[10]
  • 拼装返回的数组列表得到 [6, 7, 8, 9, 10]

直接插入排序

插入排序是在实际生活中使用得比较早的排序,比如试卷评分,把试卷按照分数高低排序。

插入排序通过设置有序数组,从后续元素中依次比较元素与有序数组中元素的顺序,从而插入到指定位置,最终形成有序数组。

  1. 设置 a[0] 是一个有序数组,无序数组从 a[1…length-1]。length 为数组长度,假定 i = 1
  2. 将 a[i] 插入到有序数组 a[0…i-1]
  3. 将 i++,如果 i 小于 length 则重复第二步
  4. 排序结束
<script type="text/javascript">
function sortInsert(array) {
	var i = 1, j, k, length = array.length, tmp;

	if (!(length > 1)) {
		return;
	}

	do {
		for (j = i - 1; j > -1; j--) {
			if (array[j] < array[i]) {
				break;
			}
		}
		if (j != i - 1) {
			tmp = array[i];
			for (k = i - 1; k > j; k--) {
				array[k + 1] = array[k];
			}
			array[k + 1] = tmp;
		}
		i++;
	} while (i < length);
}
var ar_score = [10, 9, 8, 7, 6];
sortInsert(ar_score);
</script>

[10, 9, 8, 7, 6] 插入步骤

  • 第1次排序,设置有序数组 [10],插入数组元素 9,得到 [9, 10]、[8, 7, 6]
  • 第2次排序,有序数组 [9, 10],插入数组元素 8,得到 [8, 9, 10]、[7, 6]
  • 第3次排序,有序数组 [8, 9, 10],插入数组元素 7,得到 [7, 8, 9, 10]、[6]
  • 第4次排序,有序数组 [7, 8, 9, 10],插入数组元素 6,得到 [6, 7, 8, 9, 10]

直接插入排序在第二步插入时,需要用到查询,上述代码的一个改进点是使用二分查找,降低时间复杂度。

希尔排序

希尔排序

简单选择排序

简单选择排序

堆排序

堆排序

归并排序

归并排序

基数排序

基数排序

JavaScript 数组

JavaScript 数组成员方法

  • concat
  • entries
  • every
  • filter
  • forEach
  • indexOf
  • join
  • keys
  • lastIndexOf
  • map
  • pop
  • push
  • reduce
  • reduceRight
  • reverse
  • shift
  • slice
  • some
  • sort
  • splice
  • toLocaleString
  • toString
  • unshift

concat

var a = [1];
a.concat(2); // [1, 2]
a.concat([2]); // [1, 2]
a.concat([[2]]); // [1, [2]]
// a is [1]

entries

var a = ['a', 'b', 'c'];
var iterator = a.entries(); // iterator is an ArrayIterator
var row;
do {
	row = iterator.next();
	if (row.done) break;

	console.log(row.value, row.done); // row.value = [index, value]
	// [0, 'a'], false
	// [0, 'b'], false
	// [0, 'c'], false
} while (true);

every、some、forEach

var a = [1, 2, 3, 4];
var callback_context = this;
a.every(function(element, index, array) {
	// return false to break the iterate and return false
	return element > 2;
}, callback_context); // false

var a = [1, 2, 3, 4];
var callback_context = this;
a.some(function(element, index, array) {
	// return true to break the iterate and return true
	return element > 2;
}, callback_context); // true

var a = [1, 2, , 4];
var callback_context = this;
a.forEach(function(element, index, array) {
	// called once for every not undefined element
}, callback_context); // true
var b = [];
a.forEach(function(element) {
	b.push(element);
});
// a is [1, 2, undefined, 4]
// b is [1, 2, 4]

filter

var a = [1, 2, 3, 4];
var callback_context = this;
a.filter(function(element, index, array) {
	if (element % 2) {
		return true;
	}
	return false;
}, callback_context); // [1, 3]
// a is [1, 2, 3, 4]

keys

var a = ['a', 'b', 'c'];
var iterator = a.keys();
var row;
do {
	row = iterator.next();
	if (row.done) break;

	console.log(row.value, row.done); // row.value = index
	// 0, false
	// 1, false
	// 2, false
} while (true);

map

var a = [1, 2, 3, 4];
var callback_context = this;
a.map(function(element, index, array) {
	return element * 2;
}, callback_context); // [2, 4, 6, 8]
// a is [1, 2, 3, 4]

push

var a = ['a'];
a.push('b'); // 2
// a is ['a', 'b']
a.push(['c']); // 3
// a is ['a', 'b', ['c']]

reduce、reduceRight

var a = [1, 2, 3, 4];
a.reduce(function(precious_value, current_value, current_index) {
	return precious_value + current_value;
}); // 10
// precious_value = 1, current_value = 2 precious_value + current_value = 3
// precious_value = 3, current_value = 3 precious_value + current_value = 6
// precious_value = 6, current_value = 4 precious_value + current_value = 10
// 10

var a = [1, 2, 3, 4];
a.reduce(function(precious_value, current_value, current_index) {
	return precious_value + current_value;
}, 5); // 5 is initial value
// precious_value = 5, current_value = 1 precious_value + current_value = 6
// precious_value = 6, current_value = 2 precious_value + current_value = 8
// precious_value = 8, current_value = 3 precious_value + current_value = 11
// precious_value = 11, current_value = 4 precious_value + current_value = 15
// 15

// reduceRight performs same as reduce
var a = [1, 2, 3, 4];
a.reduce(function(precious_value, current_value, current_index) {
	return precious_value + current_value;
}); // 10
// precious_value = 4, current_value = 3 precious_value + current_value = 7
// precious_value = 7, current_value = 2 precious_value + current_value = 9
// precious_value = 9, current_value = 1 precious_value + current_value = 10
// 10

sort

var a = [4, 3, 2, 1];
a.sort(); // [1, 2, 3, 4]
// a is [1, 2, 3, 4]

var a = ['d', 'c', 'b', 'a'];
a.sort(function(item1, item2) {
	if (item1 == item2) {
		return 0;
	}
	if (item1.charCodeAt(0) > item2.charCodeAt(0)) {
		return 1;
	}
	// item1 less than item2
	return -1;
	// JavaScript 采取的算法应该是冒泡排序
});

splice

var a = ['a', 'b', 'c'];
a.splice(0, 1); // ['a'] splice(start, delete_count)
// a is ['b', 'c']

var a = ['a', 'b', 'c'];
a.splice(0, 1, '1'); // ['a'] splice(start, delete_count, replace_element)
// a is ['1', 'b', 'c']

var a = ['a', 'b', 'c'];
a.splice(0, 2, '1', '2'); // ['a', 'b'] splice(start, delete_count, replace_element_1, replace_element_2)
// a is ['1', '2', 'c']

var a = ['a', 'b', 'c'];
a.splice(0, 1, '1', '2'); // ['a'] splice(start, delete_count, replace_element_1, replace_element_2)
// a is ['1', '2', 'b', 'c']

JavaScript Array 还有一些方法,但由于浏览器兼容性,即使如 entries 也较少使用。

JavaScript 加号运算符

JavaScript 加号运算符的作用

作用 示例 结果
1, 相加数值 7 + 7 数值 14
2, 连接字符串 ‘7’ + ‘7’ 字符串 ’77’
3, 转换操作数为数值 + ‘7’ 数值 7

1, 两个操作数

有两个操作数 a + b 时,会相加数值或者连接字符串。

在 JavaScript 中对两个操作数进行 + 运算时,可能会触发将其转换为原始值(ToPrimitive)、转换为数字(ToNumber)、转换为字符串(ToString)。

ToPrimitive 转换顺序:

  1. 若操作数是原始值,则返回它;
  2. 若它的 valueOf() 的返回值是原始值,则返回 valueOf() 的返回值;
  3. 若它的 toString() 的返回值是原始值,则返回 toString() 的返回值;
  4. 抛出 TypeError 错误。

ToPrimitive 的转换顺序并不是完全绝对的,其中第 2 步和第 3 步可以调换,目前只有 Date 对象是在转换为原始值时是先调用 toString,再调用 toValueOf,其余均符合上面的转换顺序。

JavaScript 的原始值包括:undefined、null、布尔值、数字、字符串。

a + b

把操作数 a、b 转换为原始值还不能马上进行 + 运算,还需要再进行 ToNumber 或者 ToString 转换为相同类型。

ToNumber 转换顺序:

  • undefined => NaN
  • null => 0
  • true => 1
  • false => 0
  • 数字 => 自身
  • 字符串 => 转换为数字,例如 “2.2” 转换为 2.2、”2.2a” 转换为 NaN

字符串转换为数字可以参考(实际中不是像下面这样做的,但结果一致):

"2.2" / 1 // 2.2
"2.a" / 1 // NaN

ToString 转换书序:

  • undefined => “undefined”
  • null => “null”
  • true => “true”
  • false => “false”
  • 数字 => 转换为字符串,例如 1 转换为 “1”、NaN 转换为 “NaN”
  • 字符串 => 自身

ToString 很好理解,简单地看就是在原来非字符串的两侧加上引号。

当 a + b 时,先将 a、b 转换为原始值,如果其中有一个是字符串,则将另外一个也转换为字符串,连接两个字符串并返回;将两个操作数转换为数字,相加并返回。

var a = true;
var b = false;
a + b // ? a 原始值是 true, b 原始值是 false, 均不是字符串, 因此是 1

var a = 1;
var b = [2];
a + b // ? a 原始值是 1, b 原始值是 "2", 因此是 "12"

var a = 1;
var b = new Date;
a + b // ?

2, 一个操作数

只有一个操作数时,会转换操作数为数值。这个比较好理解,可以按照上面提到的除以 1,结果其实就是操作数除以 1 或者乘以 1。

3, 看似两个操作数

var a = {};
var b = [];
a + b // 根据转换为原始值的规则, 结果是 "[object Object]"

{} + [] // 结果是 0, 为什么呢

因为 JavaScript 解释器(一般浏览器环境)会将第一行的 {} 代码块忽略掉,因此如下的代码看似两个操作数,实际在浏览器中是一个,即只有 + []

在 NodeJS 里面就不会将第一行的 {} 代码块忽略掉,其执行结果是 “[object Object]”。

另外,关于转换为原始值中出现 TypeError,可以进行简单的重现:

var a = {
    toString: function() {
        return [];
    },
    valueOf: function() {
        return [];
    }
};
var b = null;
a + b // 将会看到 TypeError: Cannot convert object to primitive value

JavaScript 弱类判断速查表

JavaScript 弱类 == 判断速查表

JavaScript 弱类判断

通过此表可以快速查询弱类判断结果。

JavaScript == 判断遵循规则如下:

  1. null == undefined => true
  2. 字符串 == 数字 => 先将字符串转换为数字,再比较两者的值
  3. 布尔值 == 非布尔值 => 将 true 转换为 1,false 转换为 0,再进行比较
  4. 对象 == 原始值 => 先将对象转换为原始值,再进行比较。JavaScript 内置类转换为原始值,先尝试调用 valueOf 方法,取得结果不是原始值再调用 toString 方法。日期类 Date 对象特殊,Date 对象只使用 toString 转换为原始值。
  5. 其他比较不相等。

原始值转换还体现在操作符 +,它可以对两个数值相加,也可以连接两个字符串,更可以转换操作数为数值。当参与 + 运算的操作数只有一个时,得到的结果与 parseFloat 非常相似。区别在于 + 右侧的操作数必须是合法的数值形式,parseFloat 从左到右尽可能地识别数字。

  • + ‘5.2’ => 5.2
  • parseFloat(‘5.2’) => 5.2
  • + ‘5.2.5’ => NaN
  • parseFloat(‘5.2.5’) => 5.2
  • + ‘5.2a’ => NaN
  • parseFloat(‘5.2a’) => 5.2

+ 的趣味更体现在原始值转换中,此处 Date 对象转换原始值只是一个引子。