Truy cập vô hạn trong JavaScript quicksort?

Question

Đây là mã số quicksort tôi đã viết. Hàm này không hoạt động vì nó không thể đạt được trường hợp cơ sở. Nếu tôi đăng nhập trục, r và l vào bảng điều khiển, chúng vẫn giữ nguyên cho dù chức năng sắp xếp được gọi bao nhiêu lần. Vì vậy, tôi tự hỏi, nếu đối số l, r không thực sự được chuyển vào hàm làm dữ liệu. Tại sao nó lại xảy ra?

function sort(data){ 
    if(data.length < 2){ 
     return data; 
    } 
    else{ 
     var l = []; 
     var r = []; 
     var pivot = parseInt(data.length/2); 
     for(i=0; i<data.length; i++){ 
      if(data[i] > data[pivot]){ 
       r.push(data[i]); 
      } 
      else{ 
       l.push(data[i]); 
      } 
     } 
     return sort(l).concat(sort(r)); 
    } 
} 

Answer 1

Tôi nghĩ rằng vấn đề ở đây là bước phân đoạn của bạn không nhất thiết phải thu hẹp mảng đầu vào. Ví dụ, chúng ta hãy theo dõi những gì sẽ xảy ra nếu bạn cố gắng phân loại [1, 2]. Trong trường hợp này, phần tử trục của bạn sẽ là phần tử 2. Vì 1> 2 là sai, 1 được thêm vào danh sách l. Vì 2> 2 là sai, 2 được thêm vào danh sách l. Kết quả là, cuộc gọi đệ quy của bạn trên danh sách l sẽ có chính xác các đối số giống như cuộc gọi ban đầu của bạn, gây ra đệ quy vô hạn.

Để khắc phục điều này, hãy thử tách đầu vào thành ba danh sách - một trong các giá trị nhỏ hơn, một giá trị bằng nhau và một trong các giá trị lớn hơn. Mã này được hiển thị ở đây:

function sort(data){ 
    if (data.length < 2){ 
    return data; 
    } else { 
    var l = []; 
    var r = []; 
    var e = []; 
    var i = 0; 
    var pivot = (data.length/2) | 0; 

    for(i = 0; i < data.length; i++) { 
     if (data[i] > data[pivot]) { 
     r.push(data[i]); 
     } else if (data[i] < data[pivot]) { 
     l.push(data[i]); 
     } else { 
     e.push(data[i]); 
     } 
    } 
    return sort(l).concat(e, sort(r)); 
    } 
} 

Phiên bản mới này một cách rõ ràng nhóm các yếu tố bình đẳng vào danh sách riêng của họ, vì vậy họ không đệ quy được sắp xếp theo một trong hai cuộc gọi đệ quy. Nó cũng xử lý các phần tử trùng lặp một cách duyên dáng.

Hy vọng điều này sẽ hữu ích!

Answer 2

JavaScript chuyển đối tượng theo tham chiếu (mảng cũng là đối tượng). Nếu bạn muốn chuyển chúng theo giá trị, bạn cần sử dụng chức năng ghép nối như được giải thích here.

Lưu ý rằng thao tác này sẽ tạo nhiều bản sao dữ liệu của bạn. Bạn có thể muốn sử dụng hàm sort() gốc.

Answer 3

Nếu bạn chọn giá trị lớn nhất của mảng làm phần tử trục, thì tất cả các giá trị của data sẽ kết thúc trong mảng l và không có trong r. Do đó sẽ làm cho đệ quy không bao giờ dừng lại (và giữ l, r và pivot với cùng giá trị). Trừ khi đây là một bài tập về não, sử dụng data.sort() nên làm một công việc tốt hơn. ;)