abstractquicksorter.cs

来自「Data Structures and Algorithms with Obj」· CS 代码 · 共 64 行

namespace Opus6
{
    using System;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: AbstractQuickSorter.cs,v 1.3 2001/09/11 12:04:04 brpreiss Exp $")]
    public abstract class AbstractQuickSorter : AbstractSorter
    {
        protected AbstractQuickSorter()
        {
        }

        protected abstract int SelectPivot(int left, int right);
        protected override void Sort()
        {
            this.Sort(0, base.n - 1);
            new StraightInsertionSorter().Sort(base.array);
        }

        protected void Sort(int left, int right)
        {
            if (((right - left) + 1) > 2)
            {
                int num1 = this.SelectPivot(left, right);
                this.Swap(num1, right);
                ComparableObject obj1 = base.array[right];
                int num2 = left;
                int num3 = right - 1;
                while (true)
                {
                    while ((num2 < num3) && (base.array[num2] < obj1))
                    {
                        num2++;
                    }
                    while ((num2 < num3) && (base.array[num3] > obj1))
                    {
                        num3--;
                    }
                    if (num2 >= num3)
                    {
                        break;
                    }
                    this.Swap(num2++, num3--);
                }
                if (base.array[num2] > obj1)
                {
                    this.Swap(num2, right);
                }
                if (left < num2)
                {
                    this.Sort(left, num2 - 1);
                }
                if (right > num2)
                {
                    this.Sort(num2 + 1, right);
                }
            }
        }


        protected const int CUTOFF = 2;
    }
}