How to use JS array sort method

This time I will show you how to use the JS array sort method. What are the precautions when using the JS array sort method. The following is a practical case, let's take a look.

In the algorithm class, we will be exposed to many kinds of sorting algorithms, such as bubble sort, selection sort, quick sort, heap sort, etc. So which sorting algorithm does javascript's sort method use? To figure this out, uh, just look at the v8 source code. The implementation of Array.sort in v8 is completed using JavaScript. At a glance, it uses the quick sort algorithm, but it is obviously more complicated than the quick sort we are familiar with. So what exactly is the complexity? Why make it so complicated? This is the question we are going to explore today.

Quick Sorting Algorithm

The quick sort algorithm is called a quick sort algorithm because it can achieve both the optimal and average time complexity of O(nlogn ), is a very widely used sorting algorithm. Its principle is not complicated. First find a benchmark element (pivot, any element can be used), and then compare all elements with the pivot element. If they are smaller than the pivot element, put them in one set, and put the others in another set. in; then perform quick sort on these two sets, and finally get a completely sorted sequence.

So the core of quick sort is to continuously cut the original array into small arrays and then perform the same processing on the small arrays. This is a typical divide-and-conquer algorithm design idea. Implementing a simple quicksort algorithm is not difficult. We might as well try it:

function QuickSort(arr, func) {
	if (!arr || !arr.length) return [];
	if (arr.length === 1) return arr;
	var pivot = arr[0];
	var smallSet = [];
	var bigSet = [];
	for (var i = 1; i < arr.length; i++) {
		if (func(arr[i], pivot) < 0) {
			smallSet.push(arr[i]);
		} else {
			bigSet.push(arr[i]);
		}
	}
	return QuickSort(smallSet, func).concat([pivot]).concat(QuickSort(bigSet, func));
}

This is a very basic implementation, selecting the first item of the array as the base element.

In-place sorting

We can notice that in the above algorithm, we actually create a new array as the calculation result, from It is uneconomical from a space usage perspective. The JavaScript quick sort algorithm does not create a new array like the above code, but sorts the elements by exchanging the positions of the elements based on the original array. Therefore, similar to the push, pop, and splice methods, the sort method will also modify the original arrayobject!

We said before that the core of quick sort is to cut the array. So if you just exchange elements on the original array, how to cut the array? It's very simple, we don't need to actually cut the array, we just need to remember the starting and ending index numbers of each part. For example, suppose there is an array [12, 4, 9, 2, 18, 25], and the first item 12 is selected as the base element. Then according to the original quick sort algorithm, the array will be cut into two small arrays: [4, 9, 2], 12, [18, 25]. But we can also not cut, first modify the original array to [4, 9, 2, 12, 18, 25] by comparing and exchanging elements, and then based on the position of the reference element 12, we think that the elements 0~2 are a group , elements No. 4~5 are a group. For the convenience of expression, here I call the partition composed of elements smaller than the reference element the decimal partition, and the other partition is called the large number partition. This is very similar to the partitioning of a computer hard disk. It does not really divide the hard disk into C drive and D drive, but records some starting and ending positions and logically divides it into several partitions. Similarly, in the quick sort algorithm, we also call this process partition. So accordingly, I have to modify my previous statement. The core of the quick sort algorithm is partitioning.

Having said so much, let’s implement a quick sort with partitions:

function swap(arr, from, to) {
	if (from == to) return;
	var temp = arr[from];
	arr[from] = arr[to];
	arr[to] = temp;
}
 
function QuickSortWithPartition(arr, func, from, to) {
	if (!arr || !arr.length) return [];
	if (arr.length === 1) return arr;
	from = from || 0;
	to = to || arr.length - 1;
	var pivot = arr[from];
	var smallIndex = from;
	var bigIndex = from + 1;
	for (; bigIndex <= to; bigIndex++) {
		if (func(arr[bigIndex], pivot) < 0) {
			smallIndex++;
			swap(arr, smallIndex, bigIndex);
		}
	}
	swap(arr, smallIndex, from);
	QuickSortWithPartition(arr, func, from, smallIndex - 1);
	QuickSortWithPartition(arr, func, smallIndex + 1, to);
	return arr;
}

It seems that the code is a lot longer, but it is not too complicated. First of all, since it involves the exchange of array elements, we first implement a swap method to handle element exchange. In the quick sort algorithm, two parameters are added, from and to, which respectively indicate which part of the array is currently being processed. from is the starting index and to is the ending index; if these two parameters are missing, it means processing the entire array.

同样的，我用最简单的方式选取基准元素，即所要处理分区的第一个元素。然后我定义了smallIndex和bigIndex两个变量，分别表示的是左侧小数分区的终止索引和右侧大数分区的终止索引。什么意思？就是说从第一个元素（基准元素）到第smallIndex个元素间的所有元素都比基准元素小，从第smallIndex + 1到第bigIndex个元素都比基准元素大。一开始没有比较时，很显然这两部分分区都是空的，而比较的过程很简单，直接是bigIndex向右移，一直移到分区尾部。每当bigIndex增加1，我们会进行一次判断，看看这个位置上的元素是不是比基准元素大，如果大的话，不用做处理，它已经处于大数分区了；但如果比基准元素小，就需要进行一次交换。怎么交换呢？首先将smallIndex增加1，意味着小数分区增加了一个元素，但此时smallIndex位置的元素很明显是一个大数（这个说法其实不对，如果之前大数分区里面没有元素，此时smallIndex和bigIndex相等，但对交换没有影响），而在bigIndex位置的元素是一个小数，所以只要把这两个位置的元素交换一下就好了。

最后可别忘了一开始的起始元素，它的位置并不正确，不过只要将它和smallIndex位置的元素交换位置就可以了。同时我们得到了对应的小数分区[from...smallIndex - 1]和大数分区[smallIndex + 1...to]。再对这两个分区递归排序即可。

分区过程的优化

上面的分区过程（仅仅）还是有一定的优化空间的，因为上面的分区过程中，大数分区和小数分区都是从左向右增长，其实我们可以考虑从两侧向中间遍历，这样能有效地减少交换元素的次数。举个例子，例如我们有一个数组[2, 1, 3, 1, 3, 1, 3]，采用上面的分区算法，一共碰到三次比基准元素小的情况，所以会发生三次交换；而如果我们换个思路，把从右往左找到小于基准和元素，和从左往右找到大于基准的元素交换，这个数组只需要交换一次就可以了，即把第一个3和最后一个1交换。

我们也来尝试写一下实现：

function QuickSortWithPartitionOp(arr, func, from, to) {
	if (!arr || !arr.length) return [];
	from = from || 0;
	to = to || arr.length - 1;
	if (from >= to - 1) return arr;
	var pivot = arr[from];
	var smallEnd = from + 1;
	var bigBegin = to;
	while (smallEnd < bigBegin) {
		while (func(arr[bigBegin], pivot) > 0 && smallEnd < bigBegin) {
			bigBegin--;
		}
		while (func(arr[smallEnd], pivot) < 0 && smallEnd < bigBegin) {
			smallEnd++;
		}
		if (smallEnd < bigBegin) {
			swap(arr, smallEnd, bigBegin);
		}
	}
	swap(arr, smallEnd, from);
	QuickSortWithPartitionOp(arr, func, from, smallEnd - 1);
	QuickSortWithPartitionOp(arr, func, smallEnd + 1, to);
	return arr;
}

分区与性能

前面我们说过，快速排序算法平均时间复杂度是O(nlogn)，但它的最差情况下时间复杂度会衰弱到O(n2)。而性能好坏的关键就在于分区是否合理。如果每次都能平均分成相等的两个分区，那么只需要logn层迭代；而如果每次分区都不合理，总有一个分区是空的，那么需要n层迭代，这是性能最差的场景。

那么性能最差的场景会出现吗？对于一个内容随机的数组而言，不太可能出现最差情况。但我们平时在编程时，处理的数组往往并不是内容随机的，而是很可能预先有一定顺序。设想一下，如果一个数组已经排好序了，由于之前的算法中，我们都是采用第一个元素作为基准元素，那么必然会出现每次分区都会有一个分区为空。这种情况当然需要避免。

一种很容易的解决方法是不要选取固定位置的元素作为基准元素，而是随机从数组里挑出一个元素作为基准元素。这个方法很有效，极大概率地避免了最差情况。这种处理思想很简单，我就不另外写代码了。

然而极大概率地避免最差情况并不等于避免最差情况，特别是对于数组很大的时候，更要求我们在选取基准元素的时候要更谨慎些。

三数取中（median-of-three）

基准元素应当精心挑选，而挑选基准元素的一种方法为三数取中，即挑选基准元素时，先把第一个元素、最后一个元素和中间一个元素挑出来，这三个元素中大小在中间的那个元素就被认为是基准元素。

简单实现一下获取基准元素的方法：

function getPivot(arr, func, from, to) {
	var middle = (from + to) >> 1;
	var i0 = arr[from];
	var i1 = arr[to];
	var i2 = arr[middle];
	var temp;
	if (func(i0, i1) > 0) {
		temp = i0;
		i0 = i1;
		i1 = temp;
	}
	if (func(i0, i2) > 0) {
		arr[middle] = i0;
		arr[from] = i2;
		arr[to] = i1;
		return i0;
	} else {
		arr[from] = i0;
		if (func(i1, i2) > 0) {
			arr[middle] = i1;
			arr[to] = i2;
			return i1;
		} else {
			arr[middle] = i2;
			arr[to] = i1;
			return i2;
		}
	}
}

这个例子里我完全没管基准元素的位置，一是降低复杂度，另一个原因是下面讨论重复元素处理时，基准元素的位置没什么意义。不过我把最小的值赋给了第一个元素，最大的值赋给了第二个元素，后面处理重复元素时会有帮助。

当然，仅仅是三数取中获得的基准元素，也不见得是可靠的。于是有一些其他的取中值的方法出现。有几种比较典型的手段，一种是平均间隔取一个元素，多个元素取中位数（即多取几个，增加可靠性）；一种是对三数取中进行递归运算，先把大数组平均分成三块，对每一块进行三数取中，会得到三个中值，再对这三个中值取中位数。

不过查阅v8的源代码，发现v8的基准元素选取更为复杂。如果数组长度不超过1000，则进行基本的三数取中；如果数组长度超过1000，那么v8的处理是除去首尾的元素，对剩下的元素每隔200左右（200~215，并不固定）挑出一个元素。对这些元素排序，找出中间的那个，并用这个元素跟原数组首尾两个元素一起进行三数取中。这段代码我就不写了。

针对重复元素的处理

到目前为止，我们在处理元素比较的时候比较随意，并没有太多地考虑元素相等的问题。但实际上我们做了这么多性能优化，对于重复元素引起的性能问题并没有涉及到。重复元素会带来什么问题呢？设想一下，一个数组里如果所有元素都相等，基准元素不管怎么选都是一样的。那么在分区的时候，必然出现除基准元素外的其他元素都被分到一起去了，进入最差性能的case。

那么对于重复元素应该怎么处理呢？从性能的角度，如果发现一个元素与基准元素相同，那么它应该被记录下来，避免后续再进行不必要的比较。所以还是得改分区的代码。

function QuickSortWithPartitionDump(arr, func, from, to) {
	if (!arr || !arr.length) return [];
	from = from || 0;
	to = to || arr.length - 1;
	if (from >= to - 1) return arr;
	var pivot = getPivot(arr, func, from, to);
	var smallEnd = from;
	var bigBegin = to;
	for (var i = smallEnd + 1; i < bigBegin; i++) {
		var order = func(arr[i], pivot);
		if (order < 0) {
			smallEnd++;
			swap(arr, i, smallEnd);
		} else if (order > 0) {
			while (bigBegin > i && order > 0) {
				bigBegin--;
				order = func(arr[bigBegin], pivot);
			}
			if (bigBegin == i) break;
			swap(arr, i, bigBegin);
			if (order < 0) {
				swap(arr, i, smallEnd);
				smallEnd++;
			}
		}
	}
	QuickSortWithPartitionDump(arr, func, from, smallEnd);
	QuickSortWithPartitionDump(arr, func, bigBegin, to);
	return arr;
}

简单解释一下这段代码，上文已经说过，在getPivot方法中，我将比基准小的元素放到第一位，把比基准大的元素放到最后一位。定义三个变量smallEnd、bigBegin、i，从from到smallEnd之间的元素都比基准元素小，从smallEnd到i之间的元素都和基准元素一样大，从i到bigBegin之间的元素都是还没有比较的，从bigBegin到to之间的元素都比基准元素大。了解这个关系就好理解这段代码了。遍历从smallEnd + 1到bigBegin之间的元素：
* 如果这个元素小于基准，那么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;
    }
  }
}

不得不说是一个很巧妙的实现。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

推荐阅读：

如何操作Vue去除路径中的＃号

如何使用vue中实现点击空白处隐藏div实现

The above is the detailed content of How to use JS array sort method. For more information, please follow other related articles on the PHP Chinese website!