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++的模板功能，就不会分成整数和实数两个类来区别对待啦。:-)
触类旁通，其它排序方法的使用都是类似的。可以结合数据结构与算法书中的排序内容来对排序算法进行深入理解。