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++的模板功能，就不會分成整數和實數兩個類來區別對待啦。:-)
觸類旁通，其它排序方法的使用都是類似的。可以結合數據結構與算法書中的排序內容來對排序算法進行深入理解。