深入了解javascript 数组的sort方法(5)

日期：2020-05-11 栏目：程序人生浏览：次

* 如果这个元素小于基准，那么smallEnd增加1，这时smallEnd位置的元素是等于基准元素的（或者此时smallEnd与i相等），交换smallEnd与i处的元素就可以了。
* 如果这个元素大于基准，相对比较复杂一点。此时让bigBegin减小1，检查大数分区前面一个元素是不是大于基准，如果大于基准，重复此步骤，不断让bigBegin减小1，直到找到不比基准大的元素（如果这个过程中，发现bigBegin与i相等，则中止遍历，说明分区结束）。找到这个不比基准大小元素时需要区分是不是比基准小。如果比基准小，需要做两步交换，先将i位置的大数和bigBegin位置的小数交换，这时跟第一种case同时，smallEnd增加1，并且将i位置的小数和smallEnd位置的元素交换。如果和基准相等，则只需要将i位置的大数和bigBegin位置的小数交换。
* 如果这个元素与基准相等，什么也不用做。

小数组优化

对于小数组（小于16项或10项。v8认为10项以下的是小数组。），可能使用快速排序的速度还不如平均复杂度更高的选择排序。所以对于小数组，可以使用选择排序法要提高性能，减少递归深度。

function insertionSort(a, func, 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];
			if (func(tmp, element) > 0) {
				a[j + 1] = tmp;
			} else {
				break;
			}
		}
		a[j + 1] = element;
	}
}

v8引擎没有做的优化

由于快速排序的不稳定性（少数情况下性能差，前文已经详细描述过），David Musser于1997设计了内省排序法（Introsort）。这个算法在快速排序的基础上，监控递归的深度。一旦长度为n的数组经过了logn层递归（快速排序算法最佳情况下的递归层数）还没有结束的话，就认为这次快速排序的效率可能不理想，转而将剩余部分换用其他排序算法，通常使用堆排序算法（Heapsort，最差时间复杂度和最优时间复杂度均为nlogn）。

v8引擎额外做的优化

快速排序递归很深，如果递归太深的话，很可以出现“爆栈”，我们应该尽可能避免这种情况。上面提到的对小数组采用选择排序算法，以及采用内省排序算法都可以减少递归深度。不过v8引擎中，做了一些不太常见的优化，每次我们分区后，v8引擎会选择元素少的分区进行递归，而将元素多的分区直接通过循环处理，无疑这样的处理大大减小了递归深度。我大致把v8这种处理的过程写一下：

function quickSort(arr, from, to){
  while(true){
    // 排序分区过程省略
    // ...
    
    if (to - bigBegin < smallEnd - from) {
      quickSort(a, bigBegin, to);
      to = smallEnd;
    } else {
      quickSort(a, from, smallEnd);
      from = bigBegin;
    }
  }
}

转载注明出处：http://www.heiqu.com/81.html

深入了解javascript 数组的sort方法(5)

相关推荐