Sắp xếp một phần trong JavaScript

Question

Có chức năng JavaScript tích hợp nào để thực hiện partial sort không? Nếu không, cách tốt nhất để thực hiện nó là gì?

Với một mảng không được phân loại của N yếu tố, tôi muốn tìm K yếu tố đó là tối thiểu đối với một số chức năng trọng với. K nhỏ hơn nhiều so với N, vì vậy sẽ không hiệu quả để sắp xếp toàn bộ mảng và lấy các phần tử K đầu tiên.

Tôi sẽ rất vui ngay cả khi có điều gì đó không chuẩn, phụ thuộc vào trình duyệt. Tôi vẫn có thể dự phòng triển khai JavaScript tùy chỉnh.

PS: Đây là thực hiện tùy chỉnh hiện tại của tôi (mà không cần dùng một hàm trọng số vào tài khoản, chỉ cần sắp xếp các yếu tố như họ đang có vì đơn giản):

function bisect(items, x, lo, hi) { 
    var mid; 
    if (typeof(lo) == 'undefined') lo = 0; 
    if (typeof(hi) == 'undefined') hi = items.length; 
    while (lo < hi) { 
    mid = Math.floor((lo + hi)/2); 
    if (x < items[mid]) hi = mid; 
    else lo = mid + 1; 
    } 
    return lo; 
} 

function insort(items, x) { 
    items.splice(bisect(items, x), 0, x); 
} 

function partialSort(items, k) { 
    var smallest = []; 
    for (var i = 0, len = items.length; i < len; ++i) { 
    var item = items[i]; 
    if (smallest.length < k || item < smallest[smallest.length - 1]) { 
     insort(smallest, item); 
     if (smallest.length > k) 
     smallest.splice(k, 1); 
    } 
    } 
    return smallest; 
} 

console.log(partialSort([5, 4, 3, 2, 1, 6, 7, 8, 1, 9], 3)); 

Thuật toán đi qua các mảng cho một lần duy nhất, theo dõi danh sách được sắp xếp của k các mục nhỏ nhất cho đến nay, bằng cách sử dụng tìm kiếm nhị phân để chèn các phần tử mới.

Vui lòng đăng các giải pháp thay thế nếu bạn nghĩ rằng chúng có thể nhanh hơn hoặc thanh lịch hơn. Thời gian rất được hoan nghênh.

Answer 1

Không. Chỉ có full array sort, vì vậy bạn sẽ cần phải sử dụng triển khai của riêng bạn.

nhỏ cải thiện trên mã của bạn (tôi đã nghĩ đến việc giống hệt nhau :-) thuật toán):

function partialSort(items, k) { 
    var smallest = items.slice(0, k).sort(), 
     max = smallest[k-1]; 
    for (var i = k, len = items.length; i < len; ++i) { 
     var item = items[i]; 
     if (item < max) { 
      insort(smallest, item); 
      smallest.length = k; 
      max = smallest[k-1]; 
     } 
    } 
    return smallest; 
} 

(Thậm chí seems to be a little faster, tôi đoán do bộ nhớ đệm max biến)

Answer 2

Không có mẹ đẻ chức năng sắp xếp từng phần. Điều gần nhất với những gì bạn muốn là Array.filter.

function isSmallEnough(element, index, array) { 
    return (element <= 10); 
} 
var filtered = [12, 5, 8, 130, 44].filter(isSmallEnough); 
// filtered is [5, 8] 

Ví dụ được mượn (và hơi sửa đổi) từ liên kết ở trên.