3

有没有更好的方法来使用 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[] )

我不在乎这些是否是“学术​​”和非实用模式。如果你愿意，你可以把我改成遗忘:)

K A

4

3 回答 3

2

您可以很容易地做出改进：

  • 不要在对象中保留状态。仅使用局部变量应该很容易做到这一点。
  • 使用传统的 C# 名称，例如ShellSort，而不是shellSort
  • 使用有意义的名称，例如count，而不是x

  • 使用条件运算符，例如

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

  • 使代码通用 - 为什么要限制自己使用整数？

  • 让你的方法获取有问题的数据，并使其成为IList<T>
  • 通过 a 使排序顺序任意IComparer<T>，提供使用默认值的重载。
  • 尽可能晚地声明变量以缩小其范围并提高可读性

这实际上很少与排序相关 - 我尚未验证您的代码是否实际上是合法的 shell 排序......

于 2009-10-20T18:19:49.420 回答
0

在我的测试中，这比使用相同 System.Func 比较器的数组排序快 75% 到 %90。我用它来对自定义结构进行排序。您可以轻松地对其进行修改以对类进行排序。

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);
        }
    }
}
于 2009-10-20T18:17:50.063 回答
0

请参考下面的代码。它将自动计算距离，并且距离将根据最多生成三个列表来计算。

using System;

namespace ShellSortExample
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] num = { 70, 30, 40, 10, 80, 20, 90, 110, 75, 60, 45, 199, 35, 2, 31, 22, 1, 11, 211, 100, 23, 55, 50 };
            WriteList("Unsorted List", num);
            int distance = 0;
            // Generate the distance as per the length of the list
            //It will consider maximum 3 list should generate
            for (int i = 1; i < num.Length; i++)
            {
                var div = num.Length / i;
                // Maximum 3 list should be generate
                if (div <= 3)
                {
                    distance = i;
                    break;
                }
            }
            // Do the grouping and Apply insertion sort
            for (int i = distance; i > 0; i--)
            {
                int tmpListVal = 0;
                for (int j = i; j < num.Length;)
                {
                    int tmpVal = num[j];
                    //Applying insertion sort with each shell/group element
                    for (int k = j - i; k >= 0; k -= i)
                    {
                        if (k <= num.Length - 1 && tmpVal < num[k])
                        {
                            num[k + i] = num[k];
                            num[k] = tmpVal;
                        }
                    }
                    if (j + i >= num.Length)
                    {
                        j = tmpListVal + 1;
                        tmpListVal = j;
                        if (j == i)
                        {
                            break;
                        }
                    }
                    else
                    {
                        j += i;
                    }
                }
            }
            WriteList("After applied shell sort",num);
        }
        static void WriteList(string msg, int[] list)
        {
            Console.WriteLine($"{msg} : ");
            for (int i = 0; i < list.Length; i++)
            {
                Console.Write($" {list[i]}");
            }
            Console.Write("\r\n");
        }
    }
}
于 2020-04-01T14:43:38.053 回答