大多数情况下，2层循环的冒泡排序对于一般用户已经足够，但是如果对于速度有要求，那就需要考虑效率更高的排序算法了。最近偶然看到 MdeModulePkg\Include\Library\SortLib.h 提供的排序功能，研究之后编写如下的例子。
这个库的核心是PerformQuickSort() 函数，调用者给出需要排序的 buffer，然后给出其中每一个元素的大小和数量，然后这个函数还会调用作为参数指定的CompareFunction函数。通过这个函数，不但可以比较数字或者字符串，还可以比较自动定义的规则，比方说设定书记>厂长>科长之类的……
示例代码如下：
/**
Function to perform a Quick Sort on a buffer of comparable elements.
Each element must be equally sized.
If BufferToSort is NULL, then ASSERT.
If CompareFunction is NULL, then ASSERT.
If Count is < 2 , then perform no action.
If Size is < 1 , then perform no action.
@param[in, out] BufferToSort On call, a Buffer of (possibly sorted) elements;
on return, a buffer of sorted elements.
@param[in] Count The number of elements in the buffer to sort.
@param[in] ElementSize The size of an element in bytes.
@param[in] CompareFunction The function to call to perform the comparison
of any two elements.
**/
VOID
EFIAPI
PerformQuickSort (
IN OUT VOID *BufferToSort,
IN CONST UINTN Count,
IN CONST UINTN ElementSize,
IN SORT_COMPARE CompareFunction
);
代码如下：
#include <stdlib.h>
#include <stdio.h>
#include <Uefi.h>
#include <Library/UefiLib.h>
#include <Library/ShellCEntryLib.h>
#include <Library/MemoryAllocationLib.h>
#include <Library/BaseMemoryLib.h>
#include <Library/SortLib.h>
#define TOTAL 100
#define NAMELENGTH 4
/** Expands to an integer constant expression that is the maximum value
returned by the rand function.
**/
#define RAND_MAX 0x7fffffff
static UINT32 next = 1;
typedef struct {
char Name[NAMELENGTH+1];
int Score;
} TScoreRecord;
/** Compute a pseudo-random number.
*
* Compute x = (7^5 * x) mod (2^31 - 1)
* without overflowing 31 bits:
* (2^31 - 1) = 127773 * (7^5) + 2836
* From "Random number generators: good ones are hard to find",
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195.
**/
int
rand()
{
INT32 hi, lo, x;
/* Can't be initialized with 0, so use another value. */
if (next == 0)
next = 123459876;
hi = next / 127773;
lo = next % 127773;
x = 16807 * lo - 2836 * hi;
if (x < 0)
x += 0x7fffffff;
return ((next = x) % ((UINT32)RAND_MAX + 1));
}
/**
Test comparator.
@param[in] b1 The first INTN
@param[in] b2 The other INTN
@retval 0 They are the same.
@retval -1 b1 is less than b2
@retval 1 b1 is greater then b2
**/
INTN
EFIAPI
Compare (CONST TScoreRecord *b1, CONST TScoreRecord *b2)
{
if ((b1->Score)<(b2->Score)) {
return -1;
}
if ((b1->Score)>(b2->Score)) {
return 1;
}
return (0);
}
int main()
{
TScoreRecord *SR;
int Index,NameIndex;
SR = AllocatePool (sizeof(TScoreRecord)*TOTAL);
for (Index=0;Index<TOTAL;Index++) {
//Generate a name
for (NameIndex=0;NameIndex<NAMELENGTH;NameIndex++) {
SR[Index].Name[NameIndex]=(rand()%26)+'A';
}
SR[Index].Name[NAMELENGTH]=0;
//Generate a score
SR[Index].Score=rand()%150;
//Output
printf("[%d] %s %d\n",Index,SR[Index].Name,SR[Index].Score);
}
//Sort
PerformQuickSort (SR,TOTAL,sizeof(TScoreRecord),Compare);
//Show the sort result
for (Index=0;Index<TOTAL;Index++) {
printf("[%d] %s %d\n",Index,SR[Index].Name,SR[Index].Score);
}
FreePool(SR);
return 0;
}
运行结果：
完整代码和EFI 下载：
此外，还有一个有意思的问题：如果Compare (CONST TScoreRecord *b1, CONST TScoreRecord *b2) 这里定义为Compare (TScoreRecord *b1, TScoreRecord *b2)，那么在编译时，会在PerformQuickSort (SR,TOTAL,sizeof(TScoreRecord),Compare); 报告C4090错误。因为编译器报告错误位置和实际位置着实不同，为了找到原因着实让我花费了不少时间。
