快速排序（Quick Sort）是一种改进的排序算法，其平均性能在各种排序算法中最优而被广泛使用。STL中的sort就是对快速排序的一种非递归实现。在嵌入式平台，特别是部分基于DOS的低端嵌入式系统而言，由于编译器年代久远，对C++标准支持都相去甚远，更不可能有STL了，特别是在实模式，并且CPU速度较低，系统的内存和存储空间都紧缺情况下。另外，DBMS在嵌入式上是一种奢侈，即使有嵌入式DB，但在低端系统上也很难得以应用，所以大部分低端嵌入式设备都采用的简单文本方式来存取数据。下面我会自行实现2个CLASS用以在一个数据规则格式文本文件中进行快速排序算法（递归方式）并输出排序后的文件。
代码如下（在Borland C++ 5.02中编译通过）：#include <string.h>#include <iostream.h>#include <conio.h>#include <stdio.h>#include <sys/types.h> #include <sys/stat.h> //#include <unistd.h>//类名：MsgPair
//作用：储存一个键值对（int,char*）class MsgPair{ public: ~MsgPair(); MsgPair(); MsgPair(int i, const char* pc); void SetPair(int i, const char* pc); int No() const{return _no;}; void No(int i) {_no = i;}; const char* Msg() const{return _msg;}; void Msg(const char* pc); MsgPair& operator=(MsgPair& mp); private: int _no; char *_msg; };/* public function */
MsgPair::~MsgPair()
{ delete[] _msg; _msg = NULL; _no = 0;}MsgPair::MsgPair()
{ _no = 0; _msg = NULL;}MsgPair::MsgPair(int i, const char* pc)
{ SetPair(i, pc);}//重载=操作符，赋值给this对象（深拷贝）
MsgPair& MsgPair::operator=(MsgPair& mp){ if(&mp == NULL) { delete[] _msg; _msg = NULL; _no = 0; } else { _no = mp._no; delete[] _msg; _msg = new char[strlen(mp._msg) + 1]; strcpy(_msg, mp._msg); } return *this;}//重新给该键值对复制（深拷贝）
void MsgPair::SetPair(int i, const char* pc){ _no = i; _msg = NULL; Msg(pc);}//设置_msg私有字段（深拷贝）
void MsgPair::Msg(const char* pc){ if(_msg != NULL) delete[] _msg; if(strlen(pc) > 0) { _msg = new char[strlen(pc)+1]; strcpy(_msg, pc); }}/* End of Class MsgPair */ //类名：MsgQuickSort//作用：用快速排序算法对一个规则数据文本文件进行排序，把排序后的数据输出到指定文件class MsgQuickSort{ public: ~MsgQuickSort(); MsgQuickSort(const char* filename, int lineLength, int msgOffset, int msgLength); void SetMsgFormat(const char*filename, int lineLength, int msgOffset, int msgLength); int LoadMsgFromFile(); int ParseMsg(FILE* fp); long GetFileSize(FILE *fp); int Sort(); void DisplayAll(); int SaveToFile(const char* filename); private: int Partition(MsgPair *(&mp), int low, int high); void QSort(MsgPair *(&mp), int low, int high); unsigned int _msgPairNum; MsgPair* _pMsgPair; const char* _filename; int _lineLength, _msgOffset, _msgLength;};/* public function */
MsgQuickSort::~MsgQuickSort()
{ delete[] _filename; _filename = NULL; delete[] _pMsgPair; _pMsgPair = NULL; }MsgQuickSort::MsgQuickSort(const char* filename, int lineLength, int msgOffset, int msgLength){ _pMsgPair = NULL; _filename = NULL; _msgPairNum = 0; SetMsgFormat(filename, lineLength, msgOffset, msgLength);}//设置数据规则（filename=文件名； lineLength=行长度（注意行结束符）； msgOffset=关键字偏移量； msgLength=关键字长度）
void MsgQuickSort::SetMsgFormat(const char*filename, int lineLength, int msgOffset, int msgLength){ _lineLength = lineLength; _msgOffset = msgOffset; _msgLength = msgLength; if(_filename != NULL) { delete[] _filename; _filename = NULL; } _filename = new char[strlen(filename) + 1]; strcpy((char*)_filename, filename); }//从文件中加载关键字段数据到内存中
int MsgQuickSort::LoadMsgFromFile(){ FILE *fp; int ret = 0; fp = fopen(_filename, "rb"); if(fp != NULL) { ret = ParseMsg(fp); fclose(fp); } return ret;}//获得文件大小
long MsgQuickSort::GetFileSize(FILE *fp){ struct stat buf; fstat(fileno(fp), &buf); return buf.st_size;}//提取关键字，保存到内存
int MsgQuickSort::ParseMsg(FILE* fp){ long fileSize = 0; char *msg = NULL;if(fp == NULL)
return -1;msg = new char[_msgLength + 1];
fileSize = GetFileSize(fp); _msgPairNum = (fileSize / _lineLength); //一共多少行 _pMsgPair = new MsgPair[_msgPairNum]; for(unsigned int i = 0; i < _msgPairNum; i++) { memset(msg, 0, _msgLength + 1); fseek(fp, long((i * _lineLength) + _msgOffset), SEEK_SET); fread(msg, 1, _msgLength, fp); _pMsgPair[i].SetPair(i, msg); //MsgPair从第0开始，到uiMaxItem - 1结束 } delete[] msg; return 1;}//显示当前内存中的关键数据，以及它对应加载文件的行号（从第0行开始）
void MsgQuickSort::DisplayAll(){ for(unsigned int i = 0; i < _msgPairNum; i++) { printf("[%05d]:[%s]\r\n", _pMsgPair[i].No(), _pMsgPair[i].Msg()); }}// 保存当前的顺序到文件（未执行排序函数将保持原顺序）
int MsgQuickSort::SaveToFile(const char* saveFilename){ char *msg = NULL; FILE *fp_save; FILE *fp_from; unlink(saveFilename); fp_save = fopen(saveFilename, "ab"); fp_from = fopen(_filename, "rb"); if(fp_save == NULL) return -1; else if(fp_from == NULL) { fclose(fp_save); return -1; } msg = new char[_lineLength + 1]; for(unsigned int i = 0; i < _msgPairNum; i++) { memset(msg, 0, _msgLength + 1); fseek(fp_from, long(_pMsgPair[i].No() * _lineLength), SEEK_SET); fread(msg, 1, _lineLength, fp_from); fwrite(msg, 1, _lineLength, fp_save); } delete[] msg; fclose(fp_save); fclose(fp_from); return 1;}//数据排序
int MsgQuickSort::Sort(){ QSort(_pMsgPair, 0, _msgPairNum-1);}/* private function */
//快速排序法一趟排序int MsgQuickSort::Partition(MsgPair *(&mp), int low, int high){ MsgPair pivotkey; pivotkey = mp[low];while(low<high)
{ while(low<high && strcmp(mp[high].Msg(), pivotkey.Msg()) >= 0) { --high; } mp[low] = mp[high]; while(low<high && strcmp(mp[low].Msg(), pivotkey.Msg()) <= 0) { ++low; } mp[high] = mp[low]; } mp[low] = pivotkey; return low;}//快速排序递归函数
void MsgQuickSort::QSort(MsgPair *(&mp), int low, int high){ if(low < high) { int pivotloc = Partition(mp, low, high); QSort(mp, low, pivotloc-1); QSort(mp, pivotloc+1, high); }}/* End Of Class MsgQuickSort */
/* Test */
int main(){ MsgQuickSort mqs("msg.txt", 41, 0, 10); //待排文件msg.txt；每行41个字节；关键字行中偏移0，长度10字节 mqs.LoadMsgFromFile(); //加载文件中的关键字到内存 mqs.Sort(); //快速排序(这里是按关键字的ASCII码进行排序) mqs.DisplayAll(); //显示目前的关键字顺序（排序后） mqs.SaveToFile("sortmsg.txt"); //把根据关键字进行排序后的数据保存到sortmsg.txt文件 getch(); return 0;}msg.txt示例：7905C5AEFC061207205033120181622367399997903FADFF1061207205040120181622367399997F7F56E230061207205052120181622367399997A9686FB51061207205054120181622367399997A4C7B723F0612072050551201816223673999979093698CA061207205056120181622367399997A9686FB51061207205054120181622367399997A4C7B723F0612072050551201816223673999979093698CA061207205056120181622367399997A9686FB51061207205054120181622367399997A4C7B723F06120720505512018162236739999sortmsg.txt输出：7903FADFF1061207205040120181622367399997905C5AEFC0612072050331201816223673999979093698CA0612072050561201816223673999979093698CA061207205056120181622367399997A4C7B723F061207205055120181622367399997A4C7B723F061207205055120181622367399997A4C7B723F061207205055120181622367399997A9686FB51061207205054120181622367399997A9686FB51061207205054120181622367399997A9686FB51061207205054120181622367399997F7F56E23006120720505212018162236739999实现过程分析：1、快速排序（Quick Sort）在各种排序方案中的平均时间效率最高。2、因为嵌入式系统中多用FLASH（主要是NOR和NAND）进行存取，尽可能应该减少FLASH读写，在内存中处理效率高且磨损率低。所以采用对应原文件行号+关键字方式读取到内存中进行排序处理，然后根据排序后的顺序，通过对应原文件行号，进行查找输出后保存。一般来说，即使低端嵌入式，上DOS系统后，总内存空间也应该在512KB左右，FLASH也至少应该采用1MB（保证正常操作系统以及主程序存放），按照本例子，关键字10字节，假设有1W行数据，进行上述运算时候占内存约=10*10K=100KB。3、另外，在老编译器下，没有简单且现成的可用方案来避免内存碎片（主要指外部碎片）的分配工具，基于这种情况，在MsgQuickSort的生存周期内，尽可能不要插入其他涉及动态分配内存语句，以此也可以减少在这过程中产生的内存碎片（外部碎片）的几率。