Use the Sort Function in the Package SortTools of the Toolkit TKernel
eryar@163.com China
在OpenCASCADE的Toolkit TKernel中有個排序包(Package SortTools)，可以對整數和實數進行排序。排序方法有四種：堆排序、快速排序、希爾排序、直接插入排序。這幾種排序方法都是靜態方法，因此，可以用對象名調用，這時，將靜態方法看作是某個名空間的一個函數。排序包中對應幾種排序方法的幾個類如下：
- SortTools_HeapSortOfInteger ——》 整數的堆排序；
- SortTools_HeapSortOfReal ——》實數的堆排序；
- SortTools_QuickSortOfInteger ——》整數的快速排序；
- SortTools_QuickSortOfReal ——》實數的快速排序；
- SortTools_ShellSortOfInteger ——》整數的希爾排序；
- SortTools_ShellSortOfReal ——》實數的希爾排序；
- SortTools_StraightInsertionSortOfInteger ——》整數的直接插入排序；
- SortTools_StraightInsertionSortOfReal ——》實數的直接插入排序；
以整數的快速排序為例，講解排序工具包的用法。在SortTools_QuickSortOfInteger Class Reference中看到類SortTools_QuickSortOfInteger的排序函數為一個靜態函數Sort，其聲明為：
1: static void Sort (TColStd_Array1OfInteger &TheArray, const TCollection_CompareOfInteger &Comp)
參數TheArray為等排序的數組；
參數Comp為用來比較數據中元素的類；
快速排序算法主要源代碼如下：（若需要對算法進行理解，請參考數據結構與算法的相關書籍。）
inline void Exchange(Item& Left, Item& Right)
{ Item Temp = Left;
Left = Right;
Right = Temp;
}
static void SortRecursive(Array& TheArray,
const Comparator& Comp,
const Standard_Integer Left,
const Standard_Integer Right)
{ Item Pivot;
Standard_Integer Front, Back, Middle;
if(Left < Right) { Middle = (Left + Right) / 2;
if(Comp.IsLower(TheArray(Middle), TheArray(Left))) { Exchange(TheArray(Middle), TheArray(Left));
}
if(Comp.IsLower(TheArray(Right), TheArray(Left))) { Exchange(TheArray(Right), TheArray(Left));
}
if(Comp.IsLower(TheArray(Right), TheArray(Middle))) { Exchange(TheArray(Right), TheArray(Middle));
}
Pivot = TheArray(Middle);
Exchange(TheArray(Middle), TheArray(Right - 1));
Front = Left + 1;
Back = Right - 1;
if(Back != TheArray.Lower()) { Back = Back - 1;
}
for(;;) { while (Comp.IsLower(TheArray(Front), Pivot)) { Front = Front + 1;
}
while (Comp.IsLower(Pivot, TheArray(Back))) { Back = Back - 1;
}
if(Front <= Back) { if(Front == TheArray.Upper()) return;
if(Back == TheArray.Lower()) return;
Exchange(TheArray(Front), TheArray(Back));
Front = Front + 1;
Back = Back - 1;
}
if(Front > Back) break;
}
SortRecursive(TheArray, Comp, Left, Back);
SortRecursive(TheArray, Comp, Front, Right);
}
}
void SortTools_QuickSort::Sort(Array& TheArray,
const Comparator& Comp)
{ SortRecursive(TheArray, Comp, TheArray.Lower(), TheArray.Upper());
}
使用快速排序方法的簡單代碼示例如下：
//------------------------------------------------------------------------------
// Copyright (c) 2012 eryar All Rights Reserved.
//
// File : Main.cpp
// Author : eryar@163.com
// Date : 2012-6-23 8:32
// Version : 1.0v
//
// Description : Test SortTools Package in the OpenCASCADE.
//
//==============================================================================
#include <TColStd_Array1OfInteger.hxx>
#include <TCollection_CompareOfInteger.hxx>
#include <SortTools_QuickSortOfInteger.hxx>
void DumpArray(const TColStd_Array1OfInteger& a);
int main(int argc, char* argv[])
{ TColStd_Array1OfInteger quickSortArray(1, 6);
TCollection_CompareOfInteger aComp;
// Use zero to initialize the array.
quickSortArray.Init(0);
// Set value of the array.
quickSortArray.SetValue(1, 2);
quickSortArray.SetValue(2, 50);
quickSortArray.SetValue(3, 3);
quickSortArray.SetValue(4, 60);
quickSortArray.SetValue(5, 100);
quickSortArray.SetValue(6, 70);
// Before sort, dump the array.
DumpArray(quickSortArray);
// Sort the array.
// Because the Sort method is static, so can call it directly.
SortTools_QuickSortOfInteger::Sort(quickSortArray, aComp);
// Dump information.
DumpArray(quickSortArray);
return 0;
}
void DumpArray( const TColStd_Array1OfInteger& a )
{ // Dump information.
cout<<"Array items start:"<<endl;
for (Standard_Integer i = a.Lower(); i <= a.Upper(); i++)
{ cout<<a.Value(i)<<endl;
}
cout<<"Array items end..."<<endl;
}
輸出結果如下：
1: Array items start:
2: 2
3: 50
4: 3
5: 60
6: 100
7: 70
8: Array items end...
9: Array items start:
10: 2
11: 3
12: 50
13: 60
14: 70
15: 100
16: Array items end...
17: Press any key to continue . . .
若使用C++的模板功能，就不會分成整數和實數兩個類來區別對待啦。:-)
觸類旁通，其它排序方法的使用都是類似的?？梢越Y合數據結構與算法書中的排序內容來對排序算法進行深入理解。