Thuật toán "sắp xếp nhị phân" có tồn tại không?

Question

Có một thuật toán sắp xếp được đặt tên là "phân loại nhị phân" không? Giống như sắp xếp hợp nhất, sắp xếp lựa chọn hoặc các loại phân loại khác, có tồn tại một loại nhị phân không?

Answer 1

Có this và có binary insertion sort. Cả hai đều khá giống nhau. Cả hai thuật toán thời gian đều là bậc hai (O(n^2)).

Cả hai thuật toán thực hiện O(n log n) số so sánh, nhưng trong thực tế bạn cũng sẽ phải di chuyển các phần tử xung quanh, điều này sẽ làm cho toàn bộ thuật toán bậc hai.

Answer 2

Có một số loại có liên quan đến việc tách thành hai peices (sắp xếp hợp nhất) nhưng tôi không tin rằng có một loại được gọi chính xác là "phân loại nhị phân".

Answer 3

Chúng tôi không có thuật toán sắp xếp nhị phân, nhưng chúng tôi có tìm kiếm nhị phân trên một mảng được sắp xếp.

Answer 4

Không chắc chắn những gì bạn đang tìm kiếm nhưng nếu bạn đang tìm kiếm một thuật toán phân loại nhị phân phù hợp thì bạn muốn biết các yêu cầu của mình. Mỗi thuật toán đều có điểm mạnh và điểm yếu riêng.

Ví dụ: bạn đang tìm kiếm thuật toán mang lại hiệu suất trung bình nhanh nhất (ví dụ: tìm kiếm đống) hoặc hiệu suất xấu nhất (hoạt động chậm nhất) (ví dụ: cây nhị phân cân bằng). Một số là chậm nếu bạn cũng cần phải lặp lại từ một mục kế tiếp. Nếu bạn thực hiện nhiều thao tác ngẫu nhiên, bạn có thể quan tâm nhiều hơn đến hiệu năng trung bình nhưng nếu bạn cần đảm bảo rằng bất kỳ thao tác nào nhanh hơn X mili giây thì bạn có thể muốn có một thuật toán khác. Một số có thể được làm chậm nếu bạn luôn có thêm các mục vào cuối của bộ sưu tập, vv

Vì vậy, có một google cho từ khóa như:

• Red cây đen
• tìm kiếm đống
• cây cân bằng, ví dụ http://www.codeproject.com/KB/recipes/redblackcs.aspx?msg=931557

Tất cả đều dựa trên những gì bạn cần.

Answer 5

Loại nhị phân là một thuật toán rất nhanh có liên quan đến kiểm tra bit. Nó có một đường chuyền cho mỗi bit trong mục có thể sắp xếp. Đối với mỗi đèo, nếu bit được đặt thì mục có thể sắp xếp được xếp chồng lên nhau ở một đầu của bộ đệm. Nếu bit không được thiết lập thì mục được xếp chồng lên nhau ở đầu kia của bộ đệm. Bắt đầu sắp xếp ở bit ít quan trọng nhất và xử lý các bit tiếp theo theo thứ tự tăng dần sẽ dẫn đến danh sách được sắp xếp. Tôi đã viết một trong số này vào đầu năm 8086 vào năm 1983 tại Bộ Giáo dục Scotland. Steve Pitts

Answer 6

JDK sử dụng "phân loại nhị phân" cho mảng < kích thước 32 trong phương thức Arrays.sort() của nó. Đây là đoạn mã từ JDK7

private static void binarySort(Object[] a, int lo, int hi, int start) { 
    assert lo <= start && start <= hi; 
    if (start == lo) 
     start++; 
    for (; start < hi; start++) { 
     @SuppressWarnings("unchecked") 
     Comparable<Object> pivot = (Comparable) a[start]; 

     // Set left (and right) to the index where a[start] (pivot) belongs 
     int left = lo; 
     int right = start; 
     assert left <= right; 
     /* 
     * Invariants: 
     * pivot >= all in [lo, left). 
     * pivot < all in [right, start). 
     */ 
     while (left < right) { 
      int mid = (left + right) >>> 1; 
      if (pivot.compareTo(a[mid]) < 0) 
       right = mid; 
      else 
       left = mid + 1; 
     } 
     assert left == right; 

     /* 
     * The invariants still hold: pivot >= all in [lo, left) and 
     * pivot < all in [left, start), so pivot belongs at left. Note 
     * that if there are elements equal to pivot, left points to the 
     * first slot after them -- that's why this sort is stable. 
     * Slide elements over to make room for pivot. 
     */ 
     int n = start - left; // The number of elements to move 
     // Switch is just an optimization for arraycopy in default case 
     switch (n) { 
      case 2: a[left + 2] = a[left + 1]; 
      case 1: a[left + 1] = a[left]; 
        break; 
      default: System.arraycopy(a, left, a, left + 1, n); 
     } 
     a[left] = pivot; 
    } 
} 

Answer 7

Có thể có một loại nhị phân nhưng mảng thực tế được sắp xếp nên theo nghĩa ngược lại. (Ví dụ: Giả sử bạn muốn sắp xếp một mảng các số nguyên theo thứ tự tăng dần ... cho rằng , bạn phải có mảng thực tế theo thứ tự giảm dần.)

Answer 8

Loại phân loại là thuật toán phân loại bằng cách khái niệm cây nhị phân và thực hiện sàng lọc và sau đó chọn lọc trên đó. Nó có thể được thực hiện tại chỗ.