JS配列ソートメソッドの使い方

今回はJS配列ソートメソッドの使い方を紹介します。 JS配列ソートメソッドを使用する際の注意点は何ですか？以下は実際のケースですので見てみましょう。

アルゴリズム クラスでは、

バブル ソート、選択ソート、クイック ソート、ヒープ ソートなど、さまざまな種類のソート アルゴリズムを学習します。それでは、javascriptのsortメソッドはどのソートアルゴリズムを使用するのでしょうか?これを理解するには、v8 のソース コードを見てください。 v8 の Array.sort の実装は JavaScript を使用して完了します。一見するとクイック ソート アルゴリズムが使用されていますが、これは私たちが慣れ親しんでいるクイック ソートよりも明らかに複雑です。では、その複雑さとは一体何でしょうか?なぜこれほど複雑にするのでしょうか?これが今日私たちが検討する質問です。

クイックソートアルゴリズム

クイックソートアルゴリズムは、O(nlogn)の最適な平均時間計算量を達成できるため、非常に広く使用されているソートアルゴリズムです。その原理は複雑ではありません。まずベンチマーク要素 (ピボット、任意の要素を使用できます) を見つけて、すべての要素をピボット要素と比較し、それらがピボット要素より小さい場合は、それらを 1 つのセットに入れ、他の要素をその中に入れます。別のセットを入力し、次にこれら 2 つのセットに対してクイック ソートを実行し、最終的に完全にソートされたシーケンスを取得します。

つまり、クイック ソートの核心は、元の配列を小さな配列に継続的に分割し、その小さな配列に対して同じ処理を実行することです。これは、典型的な分割統治アルゴリズムの設計アイデアです。単純なクイックソート アルゴリズムの実装は難しくありません。試してみましょう:

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

これは非常に基本的な実装であり、配列の最初の項目を基本要素として選択します。

インプレースソート

上記のアルゴリズムでは、実際には計算結果として新しい配列を作成することになりますが、これはスペース使用量の観点から見て不経済であることがわかります。 JavaScript のクイック ソート アルゴリズムは、上記のコードのように新しい配列を作成するのではなく、元の配列に基づいて要素の位置を交換することによって要素を並べ替えます。したがって、push、pop、splice メソッドと同様に、sort メソッドも元の配列

オブジェクト を変更します。

クイックソートの核心は配列をカットすることであると前に言いました。では、元の配列の要素を交換するだけの場合、配列を切り取るにはどうすればよいでしょうか?これは非常に簡単で、実際に配列を切り取る必要はなく、各部分の開始インデックス番号と終了インデックス番号を覚えておくだけで済みます。たとえば、配列 [12, 4, 9, 2, 18, 25] があり、最初の項目 12 がベース要素として選択されたとします。その後、元のクイック ソート アルゴリズムに従って、配列は 2 つに分割されます。小さな配列: [4、9、2]、12、[18、25]。ただし、切り取ることもできません。最初に要素を比較および交換することによって元の配列を [4, 9, 2, 12, 18, 25] に変更します。次に、参照要素 12 の位置に基づいて、要素 0 が配置されると考えます。 ~2 はグループ、要素番号 4~5 はグループです。ここでは表現の便宜上、基準要素よりも小さい要素で構成されるパーティションを 10 進パーティションと呼び、それ以外のパーティションを大数パーティションと呼びます。これは、コンピュータのハードディスクのパーティション分割に非常に似ていますが、実際にはハードディスクを C ドライブと D ドライブに分割するのではなく、いくつかの開始位置と終了位置を記録し、論理的に複数のパーティションに分割します。同様に、クイック ソート アルゴリズムでは、このプロセス パーティションをプロセス パーティションとも呼びます。したがって、前述のステートメントを変更する必要があります。クイック ソート アルゴリズムの中核はパーティション化です。

ここまで述べたので、パーティションを使用したクイックソートを実装しましょう:

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

コードはかなり長くなっているように見えますが、それほど複雑ではありません。まず、配列要素の交換を伴うため、要素の交換を処理する swap メソッドを最初に実装します。クイック ソート アルゴリズムでは、from と to の 2 つのパラメーターが追加されます。これらのパラメーターは、配列のどの部分が現在処理されているかをそれぞれ示します。from は開始インデックス、to は終了インデックスです。これらの 2 つのパラメーターが欠落している場合は、処理中であることを意味します。配列全体。

同样的，我用最简单的方式选取基准元素，即所要处理分区的第一个元素。然后我定义了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实现

以上がJS配列ソートメソッドの使い方の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。