pgm15_07.txt

来自「c#版本 算法大全 几乎所有常见的算法 This file contain」· 文本 代码 · 共 39 行

//
//   This file contains the C# code from Program 15.7 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C#"
//   by Bruno R. Preiss.
//
//   Copyright (c) 2001--2002 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.brpreiss.com/books/opus6/programs/pgm15_07.txt
//
public abstract class AbstractQuickSorter : AbstractSorter
{
    protected void Sort(int left, int right)
    {
	if (right - left + 1 > CUTOFF)
	{
	    int p = SelectPivot(left, right);
	    Swap(p, right);
	    ComparableObject pivot = array[right];
	    int i = left;
	    int j = right - 1;
	    for (;;)
	    {
		while (i < j && array[i] < pivot) ++i;
		while (i < j && array[j] > pivot) --j;
		if (i >= j) break;
		Swap(i++, j--);
	    }
	    if (array[i] > pivot)
		Swap(i, right);
	    if (left < i)
		Sort(left, i - 1);
	    if (right > i)
		Sort(i + 1, right);
	}
    }
    // ...
}