Triển khai Javascript Array.sort?

Question

Thuật toán nào sử dụng chức năng JavaScript Array#sort()? Tôi hiểu rằng nó có thể thực hiện tất cả các cách đối số và chức năng để thực hiện các loại khác nhau của các loại, tôi chỉ đơn giản quan tâm đến thuật toán mà loại vanilla sử dụng.

Answer 1

Nếu bạn nhìn vào lỗi này 224128, có vẻ như MergeSort đang được Mozilla sử dụng.

Answer 2

Tôi nghĩ điều đó sẽ phụ thuộc vào việc bạn đang thực hiện trình duyệt nào.

Mọi loại trình duyệt đều có cài đặt công cụ javascript của riêng nó, do đó, điều đó tùy thuộc. Bạn có thể kiểm tra repos mã hóa cho Mozilla và Webkit/Khtml để triển khai khác nhau.

Tuy nhiên, IE là nguồn đóng nên bạn có thể phải hỏi ai đó tại microsoft.

Answer 3

Tiêu chuẩn ECMAscript không chỉ định thuật toán sắp xếp nào sẽ được sử dụng. Thật vậy, các trình duyệt khác nhau có các thuật toán sắp xếp khác nhau. Ví dụ, sắp xếp của Mozilla/Firefox() không phải là stable (theo nghĩa phân loại của từ) khi sắp xếp một bản đồ. Sắp xếp của IE() ổn định.

Answer 4

Sau khi một số nghiên cứu khác, nó xuất hiện, cho Mozilla/Firefox, rằng Array.sort() sử dụng mergesort. Xem mã số here.

Answer 5

Tôi vừa xem xét WebKit (Chrome, Safari…) source. Tùy thuộc vào loại của mảng, các phương pháp phân loại khác nhau được sử dụng:

Numeric arrays (hoặc mảng kiểu nguyên thủy) đều được sắp xếp bằng cách sử dụng C++ chức năng thư viện chuẩn std::qsort mà thực hiện một số biến thể của quicksort (thường introsort).

Contiguous arrays of non-numeric type được xâu thành chuỗi và sắp xếp bằng cách sử dụng mergesort, nếu có (để có được phân loại ổn định) hoặc qsort nếu không có sắp xếp hợp nhất nào khả dụng.

Đối với các loại khác (mảng không tiếp giáp và có lẽ cho mảng kết hợp) WebKit sử dụng selection sort (mà chúng gọi là “min” sort) hoặc trong một số trường hợp, nó sắp xếp thông qua cây AVL. Thật không may, tài liệu ở đây khá mơ hồ nên bạn phải theo dõi các đường dẫn mã để thực sự thấy loại phương pháp sắp xếp nào được sử dụng.

Và sau đó có đá quý như this comment:

// FIXME: Since we sort by string value, a fast algorithm might be to use a 
// radix sort. That would be O(N) rather than O(N log N). 

- Hãy chỉ hy vọng rằng bất cứ ai thực sự “sửa chữa” này có một sự hiểu biết tốt hơn về thời gian chạy tiệm cận hơn tác giả của nhận xét này, và nhận ra rằng radix sort has a slightly more complex runtime description hơn chỉ đơn giản TRÊN).

(Nhờ phsource để chỉ ra các lỗi trong các câu trả lời ban đầu.)

Answer 6

Không có dự thảo yêu cầu JS sử dụng một algorthim sắp xếp cụ thể. Như nhiều người đã đề cập ở đây, Mozilla sử dụng sắp xếp hợp nhất. Tuy nhiên, trong mã nguồn của v8 của Chrome, tính đến hôm nay, nó sử dụng QuickSort và InsertionSort, cho các mảng nhỏ hơn.

https://github.com/v8/v8/blob/master/src/js/array.js

Từ dòng 807 - 891

var QuickSort = function QuickSort(a, from, to) { 
    var third_index = 0; 
    while (true) { 
     // Insertion sort is faster for short arrays. 
     if (to - from <= 10) { 
     InsertionSort(a, from, to); 
     return; 
     } 
     if (to - from > 1000) { 
     third_index = GetThirdIndex(a, from, to); 
     } else { 
     third_index = from + ((to - from) >> 1); 
     } 
     // Find a pivot as the median of first, last and middle element. 
     var v0 = a[from]; 
     var v1 = a[to - 1]; 
     var v2 = a[third_index]; 
     var c01 = comparefn(v0, v1); 
     if (c01 > 0) { 
     // v1 < v0, so swap them. 
     var tmp = v0; 
     v0 = v1; 
     v1 = tmp; 
     } // v0 <= v1. 
     var c02 = comparefn(v0, v2); 
     if (c02 >= 0) { 
     // v2 <= v0 <= v1. 
     var tmp = v0; 
     v0 = v2; 
     v2 = v1; 
     v1 = tmp; 
     } else { 
     // v0 <= v1 && v0 < v2 
     var c12 = comparefn(v1, v2); 
     if (c12 > 0) { 
      // v0 <= v2 < v1 
      var tmp = v1; 
      v1 = v2; 
      v2 = tmp; 
     } 
     } 
     // v0 <= v1 <= v2 
     a[from] = v0; 
     a[to - 1] = v2; 
     var pivot = v1; 
     var low_end = from + 1; // Upper bound of elements lower than pivot. 
     var high_start = to - 1; // Lower bound of elements greater than pivot. 
     a[third_index] = a[low_end]; 
     a[low_end] = pivot; 

     // From low_end to i are elements equal to pivot. 
     // From i to high_start are elements that haven't been compared yet. 
     partition: for (var i = low_end + 1; i < high_start; i++) { 
     var element = a[i]; 
     var order = comparefn(element, pivot); 
     if (order < 0) { 
      a[i] = a[low_end]; 
      a[low_end] = element; 
      low_end++; 
     } else if (order > 0) { 
      do { 
      high_start--; 
      if (high_start == i) break partition; 
      var top_elem = a[high_start]; 
      order = comparefn(top_elem, pivot); 
      } while (order > 0); 
      a[i] = a[high_start]; 
      a[high_start] = element; 
      if (order < 0) { 
      element = a[i]; 
      a[i] = a[low_end]; 
      a[low_end] = element; 
      low_end++; 
      } 
     } 
     } 
     if (to - high_start < low_end - from) { 
     QuickSort(a, high_start, to); 
     to = low_end; 
     } else { 
     QuickSort(a, from, low_end); 
     from = high_start; 
     } 
    } 
    };