Tại sao việc triển khai Javascript của Bubble sắp xếp nhanh hơn nhiều so với các thuật toán sắp xếp khác?

Question

Tôi đã thực hiện một số research về các thuật toán sắp xếp hiệu suất Javascript so sánh hiệu suất và tìm thấy kết quả không mong muốn. Sắp xếp bong bóng cung cấp hiệu suất tốt hơn nhiều so với các loại khác như Sắp xếp vỏ, Sắp xếp nhanh và chức năng Javascript gốc. Lý do tại sao điều này xảy ra? Có lẽ tôi sai trong phương pháp thử nghiệm hiệu suất của tôi?

Bạn có thể tìm thấy kết quả nghiên cứu của mình here.

Dưới đây là một số ví dụ thực hiện thuật toán:

/** 
    * Bubble sort(optimized) 
    */ 
    Array.prototype.bubbleSort = function() 
    { 
    var n = this.length; 
    do { 
     var swapped = false; 
     for (var i = 1; i < n; i++) { 
      if (this[i - 1] > this[i]) { 
       var tmp = this[i-1]; 
       this[i-1] = this[i]; 
       this[i] = tmp; 
       swapped = true; 
      } 
     } 
    } while (swapped); 
    } 

    /** 
    * Quick sort 
    */ 
    Array.prototype.quickSort = function() 
    { 
     if (this.length <= 1) 
      return this; 

     var pivot = this[Math.round(this.length/2)]; 

     return this.filter(function (x) { return x < pivot }).quickSort().concat(
      this.filter(function (x) { return x == pivot })).concat(
      this.filter(function (x) { return x > pivot }).quickSort()); 
    } 

Answer 1

Đó là bởi vì bong bóng sắp xếp là nhanh hơn khi bạn đang sắp xếp một mảng đã được sắp xếp.

Khi bạn sắp xếp cùng một mảng lặp đi lặp lại, nó sẽ được sắp xếp trong lần lặp đầu tiên trong bài kiểm tra đầu tiên, sau đó bạn sắp xếp một mảng đã được sắp xếp.

Để kiểm tra hiệu suất thực tế của sắp xếp một mảng chưa được sắp xếp, bạn phải tạo một mảng mới cho mỗi lần sắp xếp sắp xếp.