JS 배열 정렬 방법을 사용하는 방법
- php中世界最好的语言원래의
- 2018-06-04 09:39:211614검색
이번에는 JS 배열 정렬 방법을 사용하는 방법을 보여드리겠습니다. JS 배열 정렬 방법을 사용할 때 주의 사항은 무엇입니까? 다음은 실제 사례입니다.
알고리즘 수업에서는 버블 정렬, 선택 정렬, 퀵 정렬, 힙 정렬 등 다양한 종류의 정렬 알고리즘을 접하게 됩니다. 그렇다면 javascript의 정렬 방법은 어떤 정렬 알고리즘을 사용합니까? 이것을 알아내려면, 어, v8 소스 코드를 보세요. v8에서 Array.sort의 구현은 JavaScript를 사용하여 완료됩니다. 얼핏 보면 퀵 정렬 알고리즘을 사용하지만 우리에게 익숙한 퀵 정렬보다 확실히 더 복잡합니다. 그렇다면 복잡성은 정확히 무엇입니까? 왜 그렇게 복잡하게 만들까요? 이것이 오늘 우리가 탐구할 질문입니다.
퀵 정렬 알고리즘
퀵 정렬 알고리즘은 O(nlogn)의 최적 및 평균 시간 복잡도를 달성할 수 있기 때문에 매우 널리 사용되는 정렬 알고리즘입니다. 그 원리는 복잡하지 않습니다. 먼저 벤치마크 요소(피벗, 모든 요소 사용 가능)를 찾은 다음 모든 요소를 피벗 요소보다 작으면 한 세트에 넣고 다른 요소를 넣습니다. 그런 다음 이 두 세트에 대해 빠른 정렬을 수행하고 마지막으로 완전히 정렬된 시퀀스를 얻습니다.
그래서 퀵 정렬의 핵심은 원래 배열을 작은 배열로 계속 잘라낸 다음 작은 배열에 대해 동일한 처리를 수행하는 것입니다. 이는 전형적인 분할 정복 알고리즘 설계 아이디어입니다. 간단한 퀵정렬 알고리즘을 구현하는 것은 어렵지 않습니다. 시도해 봅시다:
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));
}이것은 배열의 첫 번째 항목을 기본 요소로 선택하는 매우 기본적인 구현입니다.
내부 정렬
위 알고리즘에서는 계산 결과로 실제로 새로운 배열을 생성한다는 것을 알 수 있는데 이는 공간 활용 측면에서 비경제적입니다. 자바스크립트 퀵 정렬 알고리즘은 위의 코드처럼 새로운 배열을 생성하는 것이 아니라, 원래 배열을 기준으로 요소의 위치를 교환하여 요소를 정렬합니다. 따라서 push, pop 및 splice 메소드와 유사하게 sort 메소드도 원래 배열 객체 를 수정합니다!
앞서 퀵 정렬의 핵심은 배열을 자르는 것이라고 말했습니다. 그렇다면 원래 배열의 요소를 교환하는 경우 배열을 자르는 방법은 무엇입니까? 매우 간단합니다. 실제로 배열을 잘라낼 필요가 없으며 각 부분의 시작 및 끝 인덱스 번호만 기억하면 됩니다. 예를 들어 배열 [12, 4, 9, 2, 18, 25]이 있고 첫 번째 항목 12가 기본 요소로 선택되었다고 가정하면 원래의 빠른 정렬 알고리즘에 따라 배열이 두 개로 잘립니다. 작은 배열: [4, 9, 2], 12, [18, 25]. 하지만 잘라낼 수도 없습니다. 먼저 요소를 비교하고 교환하여 원본 배열을 [4, 9, 2, 12, 18, 25]로 수정한 다음 참조 요소 12의 위치를 기준으로 요소 0을 생각합니다. ~2는 그룹, 4~5번 요소는 표현의 편의를 위해 참조 요소보다 작은 요소로 구성된 파티션을 십진 파티션, 다른 파티션을 대수 파티션이라고 합니다. 이는 컴퓨터 하드 디스크의 파티션 나누기와 매우 유사합니다. 실제로 하드 디스크를 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가 추가되는데, 이는 각각 배열의 어느 부분이 현재 처리되고 있는지를 나타냅니다. from은 시작 인덱스이고 to는 종료 인덱스입니다. 이 두 매개변수가 없으면 처리를 의미합니다. 전체 배열.
同样的，我用最简单的方式选取基准元素，即所要处理分区的第一个元素。然后我定义了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中文网其它相关文章！
推荐阅读：
위 내용은 JS 배열 정렬 방법을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!