简要介绍一些概念：
（1）排序就是整理文件中的记录，使之按关键字递增（或递减）次序排列起来。
（2）排序按策略可以划分为五类，即插入排序、交换排序、选择排序、归并排序、分配排序。
（3）插入排序每次讲一个待排序的记录，按其关键字大小插入到前面已排好序子文件的适当位置，知道全部待排序记录插入完成为止。常用的插入排序方法有直接插入排序、折半插入排序。
（4）交换排序是将待排序记录的关键字两两比较，发现两个记录的次序相反即金星交换，直到没有反序的记录为止。交换排序的主要方法有冒泡排序和快速排序。
（5）归并排序是指将若干已排序的子文件合并成一个有序的文件，归并排序有自底向上和自顶向下两种实现方法。
（6）分配排序过程无需比较关键字，是通过“分配”和“收集”实现排序。常见的分配排序有箱排序和基数排序。
实现的代码如下：
#include "SqList.h" #define KEYNUM 3 #define RADIX 10 template<typename ElemType> class SqListSort :public SqList<ElemType> { public: //直接插入排序 void insertSort(); //折半插入排序 void binaryInsertSort(); //冒泡排序 int bubbleSort(); //快速排序 void quickSort(); //直接选择排序 void selectSort(); //堆排序 void heapSort(); ////归并排序 void mergeSort(); //希尔排序 void shellSort(); //基数排序 void radixSort(); private: //快速排序辅助函数 void quickSort_aux(int low, int high); //一趟快速排序 void quickSortPartition_aux(int low, int high); ////堆调整 void heapSortAdjust_aux(int low, int high); //归并排序辅助函数 void mergeSort_aux(int low, int high); //将前后两个有序序列归并为一个有序序列 void mergeSortOne_aux(int low, int mid, int high); //希尔排序辅助函数 void shellSort_aux(int dk); ////基数排序的收集函数(静态链表存储) void radixSortCollect_aux(int front[], int end[], int time); //基数排序的分配函数 void radixSortDistribute_aux(int i, int front[], int end[]); protected: int *index;//存储数据元素原始的位置 }; //////////////////////////////////////////////////直接插入排序////////////////////////////////////////// template<typename ElemType> void SqListSort<ElemType>::insertSort() { ElemType key;//预存放当前待排序的元素 int temp_index; //记录每个元素对应的原始位置 for (int i = 0; i < n; i++) { index[i] = i; } //从第二个结点开始直到结束，逐个做直接插入排序 for (int i = 1; i < n; i++) { key = elem[i]; //记录当前待排序元素对应的原始位置 temp_index = index[i]; //从最后一个元素开始所有大于key的元素后移一位 for (int j = i-1; j >=0&&key<elem[j]; --j) { elem[j + 1] = elem[j]; index[j + 1] = index[j];//对应记录原始位置的数组也更新 } elem[j + 1] = key; index[j + 1] = temp_index; } } //////////////////////////////////////////////////折半插入排序////////////////////////////////////////// //步骤如下： //1记录当前待排序元素 //2记录顺序表有序查找区域下界和上界 //3在顺序表有序查找区域中折半查找待排序元素的位置 //4把顺序表有序查找区域与某些元素后移一个位置，以空出位置给当前待排序元素 //5在空出的位置上填写当前待排序的元素 template<typename ElemType> void SqListSort<ElemType>::binaryInsertSort() { int low;//存放有序区的下界 int mid;//存放有序区中间位置 int high;//存放有序区的上界 ElemType key;//预存放当前待排序元素 //从顺序表的第二个元素开始，直到结束，逐个做折半插入排序 for (int i = 1; i < n; i++) { key = elem[i]; low = 0; high = i - 1; while (low<=high) { mid = (low + high) / 2; if (key<elem[mid]) { high = mid - 1; } else { low = mid + 1; } } //把第high+1个及后边的所有元素后移一个位置， for (int j = i-1; j >= high+1; --j) { elem[j + 1] = elem[j]; } elem[high+1] = key;//在high+1的下标位置填写当前待排序元素 } } /////////////////////////////////////////////冒泡排序/////////////////////////////////////////////////// // //步骤：从上往下（从前往后）依次比较两相邻气泡的质量。若发现轻者在下、重者在上，则交换二者的位置。经过一趟比较 //“最重”的沉到了最后一个单元elem[n-1]。第二趟，依旧从上往下两两比较，直到elem[2]，使得次重的气泡沉到elem[2] //依次类推。直到n-1次冒泡或者不再有元素交换为止。 template<typename ElemType> void SqListSort<ElemType>::bubbleSort() { bool flag = true;//标价某趟冒泡是否有元素交换 ElemType t;//临时变量 //从上向下依次比较两相邻气泡的重量。若发现轻者在下，重者在上，则交换二者的位置。 //直到n-1次冒泡或者不再有元素交换为止。 for (int i = 0; i < n&&flag; ++i) { flag = false; for (int j = 0; j <n-i ; ++j) { if (elem[j + 1] < elem[j]) { flag = true; t = elem[j + 1]; elem[j + 1] = elem[j]; elem[j] = t; } } } } /////////////////////////////////////////////快速排序/////////////////////////////////////////////////// //快速排序 template<typename ElemType> void SqListSort<ElemType>::quickSort() { quickSort_aux(0, n - 1); } //快速排序辅助函数 //输入待排序区的下界和上界 //步骤: //（1）以elem[low]为基准，将elem[low....high]划分为符合下面条件的左右两个区间，elem[low..keyLoc-1]<=elem[keyLoc] //<=elem[keyLoc+1...high],原来的elem[low]放到elem[keyLoc]上 //(2)将左区间elem[low....keyLoc-1]自递归完成左右区间的排序 //(3)将右区间elem[keyLoc+1....high]自递归完成左右区间的排序 template<typename ElemType> void SqListSort<ElemType>::quickSort_aux(int low,int high) { int keyLoc;//预存放elem[low]排序后的位置下标 if (low<high) {//以elem[low]为基准将elem[low...high]划分为如下两个区间 //elem[low..keyLoc-1]<=elem[keyLoc]<=elem[keyLoc+1...high] //原来的elem[low]放到elem[keyLoc]上 keyLoc = quickSortPartition_aux(low, high); //将左区间自递归完成左区间的排序 quickSort_aux(low, keyLoc - 1); //将右区间自递归完成右区间的排序 quickSort_aux(keyLoc + 1, high); } } //一趟快速排序 template<typename ElemType> void SqListSort<ElemType>::quickSortPartition_aux(int low,int high) { int i = low;//左指针初始化为下界 int j = high;//右指针初始化为下界 ElemType t;//临时变量 t = elem[i];//暂存当前记录 while (i<j) {//将右指针j从右向左扫描，直到找到第1个小于基准记录的elem[j] while (i<j&&elem[j]>=t) { --j; } elem[i] = elem[j]; //将左指针i从左向右扫描，直到找到第1个大于基准记录的elem[i] while (i<j&&elem[i]<t) { ++i; } elem[j] = elem[i]; } //此时i即为基准最终的位置，将基准位置放在此位置就完成了一次划分 elem[i] = t; return i; } //////////////////////////////////////////////////直接选择排序////////////////////////////////////////// //步骤： //初始时顺序表未排序元素为整个区域，执行以下操作，每次从未排序的元素中选择一个最小的，插入到以排序元素的后面， //重复执行，直到未排序的元素只剩下一个元素位置 //（1）在顺序表elem[i-1....n-1]未排序区域选择一个最小的元素，记录其下标 //(2)最小元素与elem[i-1]记录交换 template<typename ElemType> void SqListSort<ElemType>::selectSort() { int min;//预存放当前最小元素的下标 ElemType t;//临时变量 for (int i = 1; i < n; ++i) { min = i - 1; for (int j = i; j < n; ++j) { if (elem[j] < elem[min]) min = j;//记录最小元素的下标 } if (min!=i-1) { t = elem[min]; elem[min] = elem[i - 1]; elem[i - 1] = t; } } } //////////////////////////////////////////////////堆排序////////////////////////////////////////// //大/小根堆是完全二叉树 //步骤： //(1)把elem[0...n-1]建成初始大根堆 //(2)将当前无序区的堆顶记录elem[0]和当前未经排序的最后一个记录交换，然后将新的无序区调整为堆（即重建堆）, //依次操作，直到无序区只有一个元素为止。 template<typename ElemType> void SqListSort<ElemType>::heapSort() { int i, j = 1; ElemType t; //把elem[0....n-1]建成初始大根堆 for (int i = n/2-1; i>-1; --i) { heapSortAdjust_aux(i, n - 1); } //将当前无序区的堆顶记录elem[0]和当前未经排序的最后一个记录交换 //然后将新的无序区调整为堆（即重建堆）,一次操作，知道无序区只有一个元素为止 for ( i = n-1; i >=1; --i) { //将堆顶记录和当前未排序的最后一个记录交换 t = elem[i]; elem[i] = elem[0]; elem[0] = t; //把elem[0....i-1]重建大根堆 heapSortAdjust_aux(0, i - 1); } } //堆调整 //步骤：只有堆顶结点有可能违反堆定义，所以把堆顶结点设为当前结点，从当前结点开始，把较小的关键字逐层筛选 // 下去，而将较大的关键字逐层选上来，直到当前被调整的结点已满足堆性质，或者该结点已是叶子为止，具体如下： //（1）如果有左右子堆，选择数值较大的子堆根结点elem[max] //(2)如果当前结点的数据值大于或等于数据值较大的子堆根结点，则该区间已调整为堆。否则，将数据值较大的子堆根结点 // elem[max]上移，即与当前结点的位置“交换” //（3）交换后又可能使结点elem[max]违反堆性质，修正等待堆调整区间的下标low,重复上述调整 template<typename ElemType> void SqListSort<ElemType>::heapSortAdjust_aux(int low, int high) { ElemType t = elem[low];//暂存堆顶结点，只有此结点可能违反堆堆定义 //当前结点从堆顶结点开始，把较小的关键字筛选下去，而将较大的关键字逐层筛选上来 for (int max = 2*low+1; max <= high; ) { //如果有左右子堆，选择数值较大的子堆根结点 if (max + 1 <= high&&elem[max] < elem[max + 1]) ++max; //如果当前结点的数据值大于或等于数据值较大的子堆根结点 //说明该区间已经调整为堆，跳出循环 if (t>=elem[max]) { break; } //将数据值较大的子堆根结点上移，即与当前结点的位置“互换” elem[low] = elem[max]; //交换后又可能使结点elem[max]违反堆性质 //修正等待调整区间的 下标low，重复上述调整过程 low = max; max = 2 * low + 1; } elem[low] = t;//插入元素 } /////////////////////////////////////////////////归并排序///////////////////////////////////////////// template<typename ElemType> void SqListSort<ElemType>::mergeSort() { mergeSort_aux(0, n - 1); } //归并排序辅助函数 //步骤：如果待排序的区间不只一个元素，则将此区域分成前后两半，执行以下操作： // (1)将前半部分自递归归并为有序序列 // (2)将后半部分自递归为有序序列 // (3)将已经有序的前半部和后半部合并为有序序列 template<typename ElemType> void SqListSort<ElemType>::mergeSort_aux(int low, int high) { int mid; if (low!=high) { //将顺序表元素一分为二 mid = (low + high) / 2; //将elem[low....mid]归并为有序序列 mergeSort_aux(low, mid); //将elem[mid...high]归并为有序序列 mergeSort_aux(mid, high); //将elem[low....mid]和elem[mid...high]归并为有序序列 mergeSortOne_aux(low, mid, high); } } //将前后两个有序序列归并为一个有序序列 //步骤 //(1)从前后有序区的第一个元素开始，逐一比较，每次把数据值较小的一方赋值到暂存空间tempt中，直到其中的一个有序区 // 结束 //(2)如果前面的有序区没有结束，则把剩余部分全部赋值到暂存空间tempt中 //(3)如果后面的有序区咩有结束，则把剩余部分全部复制到暂存空间tempt中 //(4)暂存空间tempt的结果再重新转存回原来的有序区 template<typename ElemType> void SqListSort<ElemType>::mergeSortOne_aux(int low, int mid, int high) { ElemType temp[LIST_MAX_SIZE];//预存放前后有序区合并的暂存空间 int k; //预存放暂存空间的下标 //前后两个有序区中的元素逐一比较，将较小的放入temp中 for (int i = k = low, j = mid + 1; i <= mid &&j <= high;) { if (elem[i] <= elem[j]) { temp[k++] = elem[i++]; } else { temp[k++] = elem[j++]; } } //如果前段有序区元素有剩余，则将剩下的元素放入temp中 if (i<=mid) { for (; i <= mid;) { temp[k++] = elem[i++]; } } //如果后段有序区元素有剩余，则将剩下的元素放入temp中 if (j<=high) { for (; j <= high;) { temp[k++] = elem[j++]; } } //将temp中的元素放回原有序区中 for ( k = low; k < =high; ++k) { elem[k] = temp[k]; } } //////////////////////////////////////////希尔排序//////////////////////////////////////////////// //希尔排序 //步骤：从希尔增量数组第一个增量开始，每次把顺序表下标具有相同增量值的元素划分为一组，一组一组地执行插入排序， // 直到希尔增量数组最后一个增量值为1为止 template<typename ElemType> void SqListSort<ElemType>::shellSort() { int dlta[LIST_MAX_SIZE];//希尔增量数组 //计算希尔增量数组各元素的值（若该数组有值，则可省略此步） for (int d = n/2,k=0; d >=1; d=d/2) { dila[k++] = d; } //从希尔增量数组第一个增量值开始，每次把顺序表下标具有相同增量值的元素划分为一组，一组一组的执行插入排序 //直到希尔增量数组最后一个增量为1，为止。 for (int i = 0; i < k; ++i) { shellSort_aux(dlta[i]); } } //希尔排序辅助函数 //步骤：把顺序表下标具有相同增量值dk的元素划分为一组，同组的元素执行如下的插入排序： // 假设当前待排序的元素elem[i]，则在elem[0...i-1]范围内与其elem[i]同组的元素已经有序， // 所以只要从后往前，在同组有序元素中寻找elem[i]的插入位置。如果elem[i]小于同组的某个元素，则该元素 // 要在同组中做后移 template<typename ElemType> void SqListSor<ElemType>::shellSort_aux(int dk) { int j; static int time = 1;//预记录希尔排序的趟数 ElemType key;//预存放当前待排序的元素 //把顺序表下标具有相同增量值dk的元素划分为一组，同组的元素执行插入排序 for (int i = dk; i < n; ++i) { j = i - dk; if (elem[i]<elem[j]) { key = elem[i];//暂存当前待排序元素 for (; j >= 0&&key < elem[j]; j-=dk) { elem[j + dk] = elem[j]; } elem[j + dk] = key;//把当前待排序的元素填写到下标为j+dk的单元中 } } } ///////////////////////////////基数排序//////////////////////////////////////////////////////////// //步骤：(静态链表存储) //（1）静态链表指针域初始化，即每个结点的指针域都指向其下一个结点，最后一个结点的指针域为0，表示静态链表结束 //(2)从低位到高位，对十进制数按先个位，再十位，百位....顺序对各位进行分配和收集 template<typename ElemType> void SqLsitSort<ElemType>::radixSort() { int front[RADIX], end[RADIX];//预存放基数排序各队列的对头及队尾 //RADIX为基数排序基数的常量，设置为10，可根据需要修改 //静态链表指针初始化 for (int i = 0; i < n; ++i) { elem[i].next = i + 1; } //最后一个结点的支指针域置0 elem[n - 1].next = 0; //对十进制数按先个位、再十位、百位...顺序对各位进行分配和收集 //（基数排序十进制数位数的常量KEYNUM，设置为3，可以根据需要更改） for ( int i = i; i < KEYNUM; ++i) { //第i趟分配 radixSortDistribute_aux(i, front, end); //第i趟收集 radixSortCollect_aux(forn, end,i); } } //基数排序的收集函数(静态链表存储) //步骤： //（1）寻找第一个非空的队列链表 //（2）第一个非空队列链表的第一个结点即为此趟排序的第一个结点 //(3)记录第一个非空队列链表最后一个结点的下标 //(4)按下面的方法依次收集其余的非空队列链表 // 1寻找下一个非空队列链表 // 2如果下一个非空队列链表存在，则把下一个非空队列链表链接到先前链表的尾部 // 3记录最后一个结点的下标 //(5)全部链表收集完毕，最后一个结点的指针域next置空 template<typename ElemType> void SqListSort<ElemType>::radixSortCollect_aux(int front[], int end[], int time) { int rear; //寻找第一个非空队列链表 for (int j = 0; !front[j];++j) { } //第一个非空队列的第一个结点即为此趟排序的第一个结点 elem[0].next = front[j]; rear = end[j]; //依次收集其余非空的队列链表 while (j<RADIX) { for (; j<RADIX-1&&!front[j]; ++j) { if (j<RADIX&&front[j]) { elem[rear].next = front[j]; rear = end[j]; } } } elem[rear].next = 0;//全部链表收集完毕，最后一个结点的指针域next置空 } //基数排序的分配函数 //根据指定的位数，执行如下步骤把静态链表所有的结点进行分配 //（1）取静态链表当前结点的数据域 //(2)取当前结点数据域的指定位 //(3)如果当前结点的数据域指定位的队列链表为空，则当前结点成为该队列的第一个结点，否则，把当前结点链接到该队列 // 尾部 template<typename ElemType> void SqListSort<ElemType>::radixSortDistribute_aux(int i, int front[], int end[]) { int p;//预存放静态链表的指针 int pos;//预存放此次排序分配基于的位数 int t;//预存放当前待排序分配的元素 for (int j = 0; j < RADIX; ++j) { front[j] = 0; } //根据指定的位数，把静态链表的所有结点进行排序分配 for (p = elem[0].next; p;p=elem[p].next) { t = elem[p].data;//取静态链表当前结点的数据域 //取当前结点数据域的指定位 pos = i; while (pos>1) { t /= 10; --pos; } j = t % 10; if (!front[j])//如果当前结点数据域指定位的队列链表为空，则 { front[j] = p;//当前结点称为该队列的第一个结点 } else { //如果当前结点数据域指定位的队列不为空，则当前结点链接到该队列的尾部 elem[end[j]].next = p; } }
end[j] = p; }