Đây có phải là cách triển khai nhanh chóng đúng không?

Question

Tôi muốn kiểm tra xem đây có phải là việc triển khai chính xác QuickSort hay không, có vẻ như đang thực hiện công việc, nhưng tôi có bỏ sót điều gì không?

public class QuickSort implements Sorter { 

public void sort(Comparable[] items) { 
    QuickSort(items, 0, items.length - 1); 
} 

static void QuickSort(Comparable[] items, int a, int b) { 
    int lo = a; 
    int hi = b; 
    if (lo >= hi) { 
     return; 
    } 
    Comparable mid = items[(lo + hi)/2]; 
    Comparable T; 

    while (lo < hi) { 
     while (items[lo].compareTo(mid)<0) { 
      lo++; 
     } 
     while (mid.compareTo(items[hi])<0) { 
      hi--; 
     } 
     if (lo < hi) { 
      T = items[lo]; 
      items[lo] = items[hi]; 
      items[hi] = T; 
     } 
    } 

    QuickSort(items, a, lo); 
    QuickSort(items, lo == a ? lo + 1 : lo, b); 

} 

}

cố định:

private static void quickSort(Comparable[] items, int a, int b) { 
    int i = a; 
    int j = b; 

    Comparable x = items[(a+ b)/2]; 
    Comparable h; 

    do { 
     while (items[i].compareTo(x) < 0) { 
      i++; 
     } 
     while (items[j].compareTo(x) > 0) { 
      j--; 
     } 
     if (i <= j) { 
      h = items[i]; 
      items[i] = items[j]; 
      items[j] = h; 
      i++; 
      j--; 
     } 
    } while (i <= j); 

    if (a < j) { 
     quickSort(items, a, j); 
    } 
    if (i < b) { 
     quickSort(items, i, b); 
    } 
} 

Answer 1

public static void quicksort(Comparable [ ] a) { 

quicksort(a, 0, a.length - 1); 
} 
private static final int CUTOFF = 10; 
private static void quicksort(Comparable [ ] a, int low, int high) { 
if(low + CUTOFF > high) 
insertionSort(a, low, high); 
else { 
int middle = (low + high)/2; 
if(a[ middle ].compareTo(a[ low ]) < 0) 
swapReferences(a, low, middle); 
if(a[ high ].compareTo(a[ low ]) < 0) 
swapReferences(a, low, high); 
if(a[ high ].compareTo(a[ middle ]) < 0) 
swapReferences(a, middle, high); 
swapReferences(a, middle, high - 1); 
Comparable pivot = a[ high - 1 ]; 
int i, j; 
for(i = low, j = high - 1; ;) { 
while(a[ ++i ].compareTo(pivot) < 0) 
; 
while(pivot.compareTo(a[ --j ]) < 0) 
; 
if(i >= j) 
break; 
swapReferences(a, i, j); 
} 
swapReferences(a, i, high - 1 
quicksort(a, low, i - 1); // Sort small elements 
quicksort(a, i + 1, high); // Sort large elements 
} 
} 
public static final void swapReferences(Object [ ] a, int index1, int index2) 
{ 
Object tmp = a[ index1 ]; 
a[ index1 ] = a[ index2 ]; 
a[ index2 ] = tmp; 
} 
private static void insertionSort(Comparable [ ] a, int low, int high) { 
for(int p = low + 1; p <= high; p++) { 
Comparable tmp = a[ p ]; 
int j; 
for(j = p; j > low && tmp.compareTo(a[ j - 1 ]) < 0; j--) 
a[ j ] = a[ j - 1 ]; 
a[ j ] = tmp; 
} 
} 

Từ http://java-blackberry.blogspot.com/2007/12/quick-sort-implementation-with-median.html

Answer 2

1 point- nhỏ có một int tràn tiềm năng ở đây:

(lo + hi)/2

Answer 3

EDIT: xấu của tôi cho thiếu thẻ java, xin lỗi ... Dưới đây là C# generic quickSort ... Tôi sẽ để nó ở đây cho người đọc .net ...

Dường như nhìn thoáng qua, nhưng làm thế nào về điều này chung chung một?

public class QuickSort<T> where T : IComparable<T> 
{ 
    #region private variable to sort inplace 
    readonly private IList<T> itms; 
    #endregion private variable to sort inplace 

    #region ctor 
    private QuickSort() { } // Hide parameterless constructor 
    /// <summary> 
    /// Constructor requires IList<T> T must implement CompareTo() method.../> 
    /// </summary> 
    /// <param name="Lst">List<T> of elements to sort</param> 
    public QuickSort(IList<T> Lst):this)() { itms = Lst; } 
    #endregion ctor 

    #region public sort method 
    public void Sort() { Sort(0, itms.Count - 1); } 
    /// <summary> 
    /// Executes QuickSort algorithm 
    /// </summary> 
    /// <param name="L">Index of left-hand boundary of partition to sort</param> 
    /// <param name="R">Index of right-hand boundary of partition to sort</param> 
    private void Sort(long L, long R) 
    { 
     // Calls iSort (insertion-sort) for partitions smaller than 5 elements 
     if (R - L < 4) iSort(L, R); 
     else 
     { 
      long i = (L + R)/2, j = R - 1; 
      // Next three lines to set upper and lower bounds 
      if (itms[L].CompareTo(itms[i]) > 0) Swap(L, i); 
      if (itms[L].CompareTo(itms[R]) > 0) Swap(L, R); 
      if (itms[i].CompareTo(itms[R]) > 0) Swap(i, R); 
      Swap(i, j); 
      // -------------------------------- 
      T p = itms[j]; // p = itms[j] is pivot element 
      i = L; 
      while (true) 
      { 
       while (itms[++i].CompareTo(p) < 0) {} 
       while (itms[--j].CompareTo(p) > 0) {} 
       if (j < i) break; 
       Swap(i, j); 
      } 
      Swap(i, R - 1); 
      Sort(L, i);  // Sort Left partition -- HERE WAS TYPO BUG 
      Sort(i + 1, R); // Sort Right partition 
     } 
    } 
    #endregion public sort method 

    #region private Helper methods 
    private void Swap(long L, long R) 
    { 
     T t = itms[L]; 
     itms[L] = itms[R]; 
     itms[R] = t; 
    } 
    private void iSort(long L, long R) 
    { 
     for (long i = L; i <= R; i++) 
     { 
      T t = itms[i]; 
      long j = i; 
      while ((j > L) && (itms[j - 1].CompareTo(t) > 0)) 
      { 
       itms[j] = itms[j - 1]; 
       j--; 
      } 
      itms[j] = t; 
     } 
    } 
    #endregion private Helper methods 
} 

Answer 4

Nhân cơ hội này để tìm hiểu cách viết đơn vị kiểm tra. (Google trên "junit", ví dụ). Tạo các mảng lớn và đảm bảo rằng chúng được sắp xếp đúng cách, ví dụ: các mảng chứa đầy các số ngẫu nhiên, các mảng được điền bằng 0, 1, Integer.MAX_INT. Cố gắng kích động những thứ như tràn số nguyên và các góc khác lạ.

Answer 5

Và đây là một phiên bản javascript ... Sắp xếp nhanh (a, comp, desc)

• một là tất nhiên mảng được sắp xếp.
• comp là hàm so sánh phải lấy hai giá trị và trả về -1, 0 hoặc +1 tùy thuộc vào cách 2 đối số nên sắp xếp.

• desc là boolean để đảo ngược thứ tự sắp xếp.

  function QuickSort(a, comp, desc) { 
      function defComp(L, R) {return((L>R)? 1: (L<R)? -1: 0);} 
      var cmp = (comp)? comp: defComp; 
      var siz = a.length; 
      qSort(0, siz-1); 
      if (desc) reverse(); 
      // ------------------ 
      function qSort(L, R) { 
       if (R - L < 4) {iSort(L, R);} // insertion-sort-- 
       else { 
        var i = parseInt((L+R) /2), j=R-1; 
        if (cmp(a[L], a[i]) > 0) swap(L,i); 
        if (cmp(a[L], a[R]) > 0) swap(L,R); 
        if (cmp(a[i], a[R]) > 0) swap(i,R); 
        swap(i,j); 
        // ------------------------------------------ 
        var p=a[j]; // p=a[j] is pivot 
        i=L; 
        while (true) { 
         while(cmp(a[++i], p) < 0); 
         while(cmp(a[--j], p) > 0);  
         if (j < i) break; 
         swap(i,j); 
        } 
        swap(i,R-1); 
        qSort(L,i); // Left Partition 
        qSort(i+1,R); // Right Partition 
       } 
      } 
      function swap(L,R) {var t=a[L]; a[L]=a[R]; a[R]=t;} 
      function reverse() 
       {for(var i=0; i<parseInt(siz/2); i++) swap(i,(siz-i-1));} 
      // insertion-sort 
      function iSort(L,R) { 
       var j,t; 
       for(var i=L; i<=R; i++) { 
        t = a[i], j = i; 
        while ((j>L) && (cmp(a[j-1], t) > 0)) 
         {a[j] = a[j-1]; j--;} 
        a[j] = t; 
       } 
      } 
  }