C＃中shell排序（comb /遞減排序的排序）最優雅的方法是什麼？

Question

有沒有更好的方法來使用C＃進行shell排序？

// array of integers to hold values 
private int[] a = new int[100]; 

// number of elements in array 
private int count; 

// Shell Sort Algorithm 
public void sortArray() 
{ 
    int i, j, increment, temp; 

    increment = 3; 

    while(increment > 0) 
    { 
    for(i=0; i < count; i++) 
    { 
     j = i; 
     temp = a[i]; 

     while((j >= increment) && (a[j-increment] > temp)) 
     { 
     a[j] = a[j - increment]; 
     j = j - increment; 
     } 

     a[j] = temp; 
    } 

    if(increment/2 != 0) 
    { 
     increment = increment/2; 
    } 
    else if(increment == 1) 
    { 
     increment = 0; 
    } 
    else 
    { 
     increment = 1; 
    } 
    } 
} 

順便說一句，我不知道，因爲我有不同語言的「優雅」各種不同的一些例子（如泡沫C#和F#排序），而且我對它們進行比較。在現實生活中，我可能會使用以下的大部分時間在C＃：

Array.Sort(object[]) 

我不在乎這些都是「學術」和非務實模式。如果你想:)

KA

Answer 1

的改進，你可以很容易使：

• 不要讓狀態的對象。這應該很容易用局部變量來完成。
• 使用常規C＃的名字，如ShellSort而非shellSort
• 使用等count代替x

• 使用條件運算符，例如有意義的名稱

  // This replaces your last 12 lines 
  int halfIncrement = increment/2; 
  increment = halfIncrement != 0 ? halfIncrement : 1 - increment; 
  

• 使代碼通用 - 爲什麼限制自己整數？

• 讓你的方法把數據問題，並使其成爲IList<T>
• 使排序順序任意通過IComparer<T>，提供其使用默認的過載。
• 聲明變量儘可能晚地降低其範圍和提高可讀性

很少的這實際上是某種相關的 - 我還沒有驗證您的代碼是否實際上是一個合法的希爾排序或不..

Answer 2

在我的測試，這是75％至90％，比數組排序與同System.Func比較器你可以更快的降-MOD我遺忘。我用它來排序一個自定義結構。您可以輕鬆修改它以對課程進行排序。

public class DualQuickSort<T> where T : struct 
    { 
     private readonly System.Func<T, T, int> comparer; 
     public DualQuickSort(System.Func<T, T, int> comparer) 
     { 
      this.comparer = comparer; 
     } 

    public DualQuickSort(IComparer<T> comparer) 
     : this(comparer.Compare) 
    { 

    } 

    public void Sort(T[] a) 
    { 
     Sort(a, 0, a.Length); 
    } 
    public void Sort(T[] a, int fromIndex, int toIndex) 
    { 
     RangeCheck(a.Length, fromIndex, toIndex); 

     DualPivotQuicksort(a, fromIndex, toIndex - 1, 3); 
    } 
    private static void RangeCheck(int length, int fromIndex, int toIndex) 
    { 
     if (fromIndex > toIndex) 
     { 
      throw new ArgumentException("fromIndex > toIndex"); 
     } 
     if (fromIndex < 0) 
     { 
      throw new IndexOutOfRangeException(fromIndex + " is less than 0"); 
     } 
     if (toIndex > length) 
     { 
      throw new IndexOutOfRangeException(toIndex + " is greater than " + fromIndex); 
     } 
    } 

    private static void Swap(T[] a, int i, int j) 
    { 
     var temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 
    private void DualPivotQuicksort(T[] a, int left, int right, int div) 
    { 
     var len = right - left; 

     if (len < 27) 
     { // insertion sort for tiny array 
      for (var i = left + 1; i <= right; i++) 
      { 
       for (var j = i; j > left && comparer(a[j] , a[j - 1])==-1; j--) 

       { 
        Swap(a, j, j - 1); 
       } 
      } 
      return; 
     } 
     var third = len/div; 
     // "medians" 
     var m1 = left + third; 
     var m2 = right - third; 
     if (m1 <= left) 
     { 
      m1 = left + 1; 
     } 
     if (m2 >= right) 
     { 
      m2 = right - 1; 
     } 
     if (comparer(a[m1] , a[m2])==-1) 
     { 
      Swap(a, m1, left); 
      Swap(a, m2, right); 
     } 
     else 
     { 
      Swap(a, m1, right); 
      Swap(a, m2, left); 
     } 
     // pivots 
     var pivot1 = a[left]; 
     var pivot2 = a[right]; 
     // pointers 
     var less = left + 1; 
     var great = right - 1; 
     // sorting 
     for (var k = less; k <= great; k++) 
     { 
      if (comparer(a[k] , pivot1)==-1) 
      { 
       Swap(a, k, less++); 
      } 
      else if (comparer(a[k], pivot2) == 1) 
      { 
       while (k < great && comparer(a[great] , pivot2)==1) 
       { 
        great--; 
       } 
       Swap(a, k, great--); 
       if (comparer(a[k], pivot1) == -1) 
       { 
        Swap(a, k, less++); 
       } 
      } 
     } 
     // Swaps 
     var dist = great - less; 
     if (dist < 13) 
     { 
      div++; 
     } 
     Swap(a, less - 1, left); 
     Swap(a, great + 1, right); 
     // subarrays 
     DualPivotQuicksort(a, left, less - 2, div); 
     DualPivotQuicksort(a, great + 2, right, div); 

     // equal elements 
     if (dist > len - 13 && comparer(pivot1,pivot2)!=0) 
     { 
      for (int k = less; k <= great; k++) 
      { 
       if (comparer(a[k] , pivot1)==0) 
       { 
        Swap(a, k, less++); 
       } 
       else if (comparer(a[k], pivot2) == 0) 
       { 
        Swap(a, k, great--); 
        if (comparer(a[k], pivot1) == 0) 
        { 
         Swap(a, k, less++); 
        } 
       } 
      } 
     } 
     // subarray 
     if (comparer(pivot1 , pivot2)==-1) 
     { 
      DualPivotQuicksort(a, less, great, div); 
     } 
    } 
}