quicksorter.cs

5种.net写的排序的方法

using System;
using System.Collections.Generic;
using System.Text;

namespace IAXK.Sys
{
    /// <summary>
    /// 快速排序器
    /// </summary>
    /// <typeparam name="T"></typeparam>
    [Serializable]
    public class QuickSorter<T>:Sorter<T> where T:IComparable,IComparable<T>
    {
        /// <summary>
        /// 因子
        /// </summary>
        private int M = 7;

        /// <summary>
        /// 因子。调整它可以影响在不同机器上的排序速度。按照《数值分析方法库》第三版上说，Factor设置为7不会错得太远
        /// </summary>
        public int Factor
        {
            get { return M; }
            set
            {
                if (value <= 0)
                    M = 1;
                else
                    M = value;
            }
        }

        /// <summary>
        /// 附加存贮器长度。
        /// </summary>
        private int NSTACK = 64;

        /// <summary>
        /// 附加堆栈的大小，默认为64。如果将要进行排序的数组长度非常大，可做适当增加。
        /// </summary>
        public int StackSize
        {
            get { return NSTACK; }
            set
            {
                if (value < 32)
                    NSTACK = 32;
                else
                    NSTACK = value;
            }
        }
        

        /// <summary>
        /// 算法实现
        /// </summary>
        /// <param name="v"></param>
        /// <param name="ot"></param>
        /// <param name="count">如果count>0，则只对数组前count个元素进行排序</param>
        private  void QuickSort(T[] v, OrderType ot,int count)
        {
            int i, ir, j, k, jstack = -1, l = 0;
            int n = v.Length;
            if (count > 0)
            {
                if (count < n)
                    n = count;
            }

            ir = n - 1;
            T a;
            int[] istack = new int[NSTACK];
            for (; ; )
            {
                if ((ir - l) < M)
                {
                    for (j = l + 1; j <= ir; j++)
                    {
                        a = v[j];
                        for (i = j - 1; i >= l; i--)
                        {
                            if (CompareValue(v[i], a, ot) <= 0) break;
                            v[i + 1] = v[i];
                        }
                        v[i + 1] = a;
                    }
                    if (jstack < 0) break;
                    ir = istack[jstack--];
                    l = istack[jstack--];
                }
                else
                {
                    k = (l + ir) >> 1;
                    Swap(ref v[k], ref v[l + 1]);
                    if (CompareValue(v[l], v[ir], ot) > 0)
                        Swap(ref v[l], ref v[ir]);
                    if (CompareValue(v[l+1], v[ir], ot) > 0)
                        Swap(ref v[l+1], ref v[ir]);
                    if (CompareValue(v[l], v[l+1], ot) > 0)
                        Swap(ref v[l], ref v[l+1]);
                    i = l + 1;
                    j = ir;
                    a = v[l + 1];
                    for (; ; )
                    {
                        do
                            i++;
                        while (CompareValue(v[i], a, ot) < 0);
                        do
                            j--;
                        while (CompareValue(v[j], a, ot) > 0);
                        if (j < i) break;
                        Swap(ref v[i],ref v[j]);
                    }
                    v[l + 1] = v[j];
                    v[j] = a;
                    jstack += 2;
                    if (jstack >= NSTACK) throw new Exception("堆栈设置太小！");
                    if ((ir - i + 1) >= (j - 1))
                    {
                        istack[jstack] = ir;
                        istack[jstack - 1] = i;
                        ir = j - 1;
                    }
                    else
                    {
                        istack[jstack] = j - 1;
                        istack[jstack - 1] = l;
                        l = i;
                    }
                }
            }//end of for(;;)
        }


        /// <summary>
        /// 对数组中的所有元素排序
        /// </summary>
        /// <param name="v"></param>
        /// <param name="ot">排序顺序</param>
        protected override void Algorithm(T[] v, OrderType ot)
        {
            QuickSort(v, ot, -1);            
        }


        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="v">要排序的数组</param>
        /// <param name="ot">排序顺序</param>
        /// <param name="count">如果count>0，则只对数组前count个元素进行排序</param>
        public void Sort(T[] v, OrderType ot, int count)
        {
            QuickSort(v, ot, count);      
        }
    }
}