四十三、希尔排序
示例：
#include <iostream>
using namespace std;
// 对希尔排序中的单个组进行排序。
// arr-待排序的数组，len-数组总的长度，num-小组的编号（从 0 开始），step-分组的步长（增量）。
void groupsort(int arr[], int len, int num, int step)
{
int itmp; // 当前需要排序的元素的值。
for (int ii = num + step; ii < len; ii = ii + step) // 每个小组的第一个元素不需要排序，就像
拿到第一张牌一样。
{
itmp = arr[ii]; // 待排序元素
// 从已排序的最右边开始，把大于当前排序的元素后移。
int jj; // 需要后移元素的计数器。
for (jj = ii - step; jj >= 0; jj = jj - step)
{
if (arr[jj] <= itmp) break;
arr[jj + step] = arr[jj]; // 逐个元素后移。
}
arr[jj + step] = itmp; // 插入当前排序元素。
}
}
// 希尔排序，arr 是待排序数组的首地址，len 是数组的大小。
void shellsort(int arr[], unsigned int len)
{
// step 为步长，每次减为原来的一半取整数，最后一次必定为 1。
for (int step = len / 2; step > 0; step = step / 2)
{
// 共 step 个组，对每一组都执行插入排序。
for (int ii = 0; ii < step; ii++)
{
groupsort(arr, len, ii, step);
}
}
}
int main(int argc, char* argv[])
{
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
shellsort(arr, len); // 希尔排序。
// 如果第三个参数填 0，第四个参数填 1，效果等同普通插入排序。
// groupsort(arr, len,0,1);
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}
四十四、快速排序
示例：
#include <iostream>
using namespace std;
void quicksort(int arr[], int len)
{
if (len < 2) return; // 数组的元素小于 2 个就不用排序了。
int mid = arr[0]; // 选取最左边的元素作为中心轴（基准数）。
int left = 0; // 左下标。
int right = len - 1; // 右下标。
int moving = 2; // 当前应该移动的下标，1-左下标；2-右下标，缺省取值 2。
while (left < right)
{
if (moving == 1) // 移动左下标的情况。
{
// 如果左下标位置元素的值小等于中心轴，继续移动左下标。
if (arr[left] <= mid) { left++; continue; }
arr[right] = arr[left]; // 如果左下标位置元素的值大于中心轴，把它填到右下标
的坑中。
right--; // 右下标向左移动。
moving = 2; // 下次循环将移动右下标。
}
else // 移动右下标的情况。
{
// 如果右下标位置元素的值大于等于中心轴，继续移动右下标。
if (arr[right] >= mid) { right--; continue; }
arr[left] = arr[right]; // 如果右下标位置元素的值小于中心轴，把它填到左下标
的坑中。
left++; // 左下标向右移动。
moving = 1; // 下次循环将移动左下标。
}
}
// 如果循环结束，左右下标重合，把中心轴的值填进去。
arr[left] = mid;
quicksort(arr, left); // 对中心轴左边的序列进行排序。
quicksort(arr + left + 1, len - left - 1); // 对中心轴右边的序列进行排序。
}
int main(int argc, char* argv[])
{
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
quicksort(arr, len);
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}
四十五、计数排序
示例：
#include <iostream>
using namespace std;
// 获取待排序数组元素中的最小和最大值。
void arrminmax(int arr[], int len, int& minvalue, int& maxvalue)
{
int ii = 0;
minvalue = maxvalue = arr[0];
for (ii = 0; ii < len; ii++)
{
if (maxvalue < arr[ii]) maxvalue = arr[ii];
if (minvalue > arr[ii]) minvalue = arr[ii];
}
}
// 计数排序主函数，arr-待排序数组的地址，len-数组的长度。
void countsort(int arr[], int len)
{
if (len < 2) return;
// 获取待排序数组元素中的最小和最大值。
int minvalue, maxvalue;
arrminmax(arr, len, minvalue, maxvalue);
// 分配并初始化临时数组。
int* arrtmp = new int[maxvalue - minvalue + 1];
memset(arrtmp, 0, sizeof(int)*(maxvalue - minvalue + 1));
// 临时数组计数。
for (int ii = 0; ii < len; ii++) arrtmp[arr[ii] - minvalue]++;
// 把临时数组计数的内容恢复到到 arr 数组中。
for (int ii=0,jj = 0; jj < maxvalue - minvalue + 1; jj++)
{
for (int kk = 0; kk < arrtmp[jj]; kk++) arr[ii++] = jj + minvalue;
}
delete[] arrtmp; // 释放临时数组。
}
int main(int argc, char* argv[])
{
int arr[] = { 2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
countsort(arr, len);
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}
四十六、桶排序
示例（不用 InitList()分配头结点）：
#include <iostream>
using namespace std;
typedef int ElemType; // 自定义链表的数据元素为整数。
struct LNode // 单链表的结点。
{
ElemType data; // 存放结点的数据元素。
struct LNode* next; // 指向下一个结点的指针。
};
// 初始化链表，返回值：失败返回 nullptr，成功返回头结点的地址。
LNode* InitList()
{
LNode* head = new (std::nothrow) LNode; // 分配头结点。
if (head == nullptr) return nullptr; // 内存不足，返回失败。
head->next = nullptr; // 头结点的下一结点暂时不存在，置空。
return head; // 返回头结点。
}
// 销毁链表。
void DestroyList(LNode* head)
{
// 销毁链表是指释放链表全部的结点，包括头结点。
LNode* tmp;
while (head != nullptr)
{
tmp = head->next; // tmp 保存下一结点的地址。
delete head; // 释放当前结点。
head = tmp; // 指针移动到下一结点。
}
}
// 在链表的头部插入元素（头插法），返回值：false-失败；true-成功。
bool PushFront(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = head->next;
head->next = tmp;
return true;
}
// 显示链表中全部的元素。
void PrintList(const LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; }
LNode* pp = head->next; // 从第 1 个结点开始。
while (pp != nullptr)
{
cout << pp->data << " "; // 如果元素为结构体，这行代码要修改。
pp = pp->next; // 指针往后移动一个结点。
}
cout << endl;
}
// 在链表的尾部插入元素（尾插法），返回值：false-失败；true-成功。
bool PushBack(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到最后一个结点，pp 将指向尾结点（最后一个结点）。
while (pp->next != nullptr) pp = pp->next;
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = nullptr;
pp->next = tmp;
return true;
}
// 求链表的表长，返回值：>=0-表 LL 结点的个数。
size_t ListLength(LNode* head)
{
//if (head == nullptr) { cout << "链表不存在。\n"; return 0; }
//LNode* pp = head->next; // 头结点不算，从第 1 个结点开始。
//size_t length = 0;
//while (pp != nullptr) { pp = pp->next; length++; }
//return length;
// 不使用临时变量，如何计算链表（包括头结点）的长度？
if (head==nullptr) return 0;
return ListLength(head->next)+1;
}
// 删除链表第一个结点。
bool PopFront(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head->next; // pp 指向第一个节点。
head->next = head->next->next; // 修改头结点的 next 指针。
delete pp; // 删除第一个节点。
return true;
}
// 删除链表最后一个结点。
bool PopBack(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
// 必须加上这个判断，否则下面的循环 pp->next->next 不成立。
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到倒数第二个结点（包括头结点）。
while (pp->next->next != nullptr) pp = pp->next;
delete pp->next; // 释放最后一个结点。
pp->next = nullptr; // 倒数第二个结点成了最后一个结点。
return true;
}
// 清空链表，清空链表是指释放链表全部的结点，但是，不释放头结点。
void ClearList(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; } // 判断链表是否存在。
LNode* tmp1;
LNode* tmp2 = head->next; // 从头结点的下一个结点开始释放。
while (tmp2 != nullptr)
{
tmp1 = tmp2->next;
delete tmp2;
tmp2 = tmp1;
}
head->next = nullptr; // 这行代码一定不能少，否则会留下野指针。
}
// 查找元素 ee 在链表中的结点地址，如果没找到返回 nullptr，否则返回结点的地址。
LNode* LocateElem(const LNode* head, const ElemType& ee)
{
LNode* pp = head->next; // 从第 1 个存放数据结点开始。
while (pp != nullptr)
{
// 如果数据元素是结构体，以下代码要修改成比较关键字。
if (pp->data == ee) return pp;
pp = pp->next;
}
return pp;
}
// 获取链表中第 n 个结点，成功返回结点的地址，失败返回 nullptr。
// 注意，n 可以取值为 0，表示头结点。
LNode* LocateNode(LNode* head, unsigned int n)
{
if (head == nullptr) { cout << "链表不存在。\n"; return nullptr; }
LNode* pp = head; // 指针 pp 指向头结点，逐步往后移动，如果为空，表示后面没结
点了。
unsigned int ii = 0; // ii 指向的是第几个结点，从头结点 0 开始，pp 每向后移动一次，
ii 就加 1。
while ((pp != nullptr) && (ii < n))
{
pp = pp->next; ii++;
}
if (pp == nullptr) { cout << "位置" << n << "不合法，超过了表长。\n"; return nullptr; }
return pp;
}
// 在指定结点 pp 之后插入元素 ee。
bool InsertNextNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
LNode* tmp = new LNode;
tmp->data = ee;
tmp->next = pp->next;
pp->next = tmp;
return true;
}
// 在指定结点 pp 之前插入元素 ee。
bool InsertPriorNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
// 在指定结点 pp 之前插入采用偷梁换柱的方法：
// 1、分配一个新的结点；
// 2、把 pp 结点的数据和指针复制到新结点中。
// 3、把待插入元素的数据存入 pp 结点中。
LNode* tmp = new LNode;
// 把 pp 结点的数据和指针复制到 tmp 中。
tmp->data = pp->data;
tmp->next = pp->next;
// 把待插入的元素存入 pp 中。
pp->data = ee;
pp->next = tmp;
return true;
}
// 删除指定结点。
bool DeleteNode1(LNode* pp)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
if (pp->next != nullptr) // 如果结点 pp 后面还有结点。
{
// 删除指定结点的思想是：1）把 pp 后继结点的数据和 next 指针复制到 pp 结点；2）删
除 pp 结点的后继结点。
LNode* tmp = pp->next; // tmp 指向 pp 的后继结点。
pp->data = tmp->data; // 把后继结点的数据复制到 pp 结点中。
pp->next = tmp->next; // 把 pp 的 next 指向后继结点的 next。
delete tmp; // 释放后继结点。
return true;
}
else // 如果结点 pp 是最后一个结点。
{
return false; // 可以在函数外面调用 PopBack()函数。
}
}
// 把元素有序的插入链表中，返回值：false-失败；true-成功。
bool PushOrder(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* tail = head; // 将指向尾结点。
LNode* pp = head->next; // 从第一个结点开始。
while (pp != nullptr)
{
// 如果结点的元素大于 ee，把 ee 插入该结点前面。
if (pp->data > ee) { InsertPriorNode(pp, ee); return true; }
tail = pp;
pp = pp->next; // 指针后移一个结点。
}
// 如果在上面的循环中没能插入元素，表示 ee 应该插入到链表的尾部。
if (pp == nullptr) return InsertNextNode(tail, ee);
return true;
}
// 采用归并的方法，将两个升序的链表 La 和 Lb，合并成一个升序的链表 Lc。
// 合并后，链表 La 和 Lb 将不再拥有结点（只有头结点）。
void MergeList(LNode *La, LNode *Lb, LNode *Lc)
{
LNode* pa = La->next;
LNode* pb = Lb->next;
LNode* pp;
// 把 pa 和 pb 合并到 Lc 中。
while ((pa != nullptr) && (pb != nullptr))
{
// 取 pa 和 pb 的较小者。
if (pa->data <= pb->data)
{
pp = pa; pa = pa->next;
}
else
{
pp = pb; pb = pb->next;
}
// 把较小的结点 pp 追加到 Lc 中。
Lc->next = pp;
Lc = Lc->next;
}
// 把链表 pa 其它的元素追加到 Lc 中。
if (pa != nullptr) Lc->next = pa;
// 把链表 pb 其它的元素追加到 Lc 中。
if (pb != nullptr) Lc->next = pb;
// 链表 La 和 Lb 的结点已全部转移给了 Lc，需置空，否则 DestroyList()时会引起重复释放结点。
La->next = Lb->next = nullptr;
}
// 桶排序主函数，参数 arr 是待排序数组的首地址，len 是数组元素的个数，bucketnum 是桶的个
数。
void bucketsort(int arr[], int len, int bucketnum)
{
// 分配桶头结点的结构体数组。
LNode* buckets = new LNode[bucketnum];
// 初始化桶，把头结点的 next 指针置为空。
for (int ii = 0; ii < bucketnum; ii++)
buckets[ii].next = nullptr;
// 把数组 arr 全部的元素放入桶中。
for (int ii = 0; ii < len; ii++)
{
PushOrder(&buckets[arr[ii] % bucketnum] ,arr[ii]);
}
// 显示每个桶中的元素。
cout << "每个桶中的元素如下：\n";
for (int ii = 0; ii < bucketnum; ii++) PrintList(&buckets[ii]);
// 把全部桶中的元素归并到 LL 中。
LNode LL; LL.next = nullptr;
LNode tmp; tmp.next = nullptr;
for (int ii = 0; ii < bucketnum; ii++)
{
MergeList(&buckets[ii], &LL, &tmp); // 把桶中的链表和 LL 合并到 tmp 中。
swap(LL.next, tmp.next); // 交换 LL 和 tmp 的数据结点。
}
cout << "显示合并后的结果：\n"; PrintList(&LL);
// 把合并后的结果保存到数组 arr 中。
LNode* pp = LL.next;
for (int ii = 0; ii < len; ii++)
{
arr[ii] = pp->data; pp = pp->next;
}
DestroyList(LL.next); // 释放链表 LL 的数据结点。
delete[] buckets; // 释放桶的结构体数组（头结点们）。
}
int main()
{
// 链表语义是动态分配内存，包括头节点，也是动态分配出来的。
// 以下代码用于测试 PushOrder()函数的功能。
//LNode LL; LL.next = nullptr; // = InitList(); // 初始化链表 LL。
//cout << "有序的插入元素（5、8、7、4、1、3、9、3、6）。\n";
//PushOrder(&LL, 5);
//PushOrder(&LL, 8);
//PushOrder(&LL, 7);
//PushOrder(&LL, 4);
//PushOrder(&LL, 1);
//PushOrder(&LL, 3);
//PushOrder(&LL, 9);
//PushOrder(&LL, 3);
//PushOrder(&LL, 6);
//PrintList(&LL); // 把链表中全部的元素显示出来。
//DestroyList(LL.next); // 销毁链表 LL 的数据结点。

// 以下代码用于测试 MergeList()函数的功能。
//LNode La; La.next = nullptr;
//LNode Lb; Lb.next = nullptr;
//LNode Lc; Lc.next = nullptr;
//PushOrder(&La, 5);
//PushOrder(&La, 8);
//PushOrder(&La, 7);
//PushOrder(&La, 4);
//PushOrder(&Lb, 1);
//PushOrder(&Lb, 3);
//PushOrder(&Lb, 9);
//PushOrder(&Lb, 2);
//PushOrder(&Lb, 6);
//MergeList(&La, &Lb, &Lc); // 把链表 La 和 Lb 合并成 Lc。
//PrintList(&Lc); // 把链表 Lc 中全部的元素显示出来。
DestroyList(La.next);
DestroyList(Lb.next);
//DestroyList(Lc.next);
//
以下代码用于测试桶排序的功能。
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
bucketsort(arr, len,3);
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}
示例（用 InitList()分配头结点）：
#include <iostream>
using namespace std;
typedef int ElemType; // 自定义链表的数据元素为整数。
struct LNode // 单链表的结点。
{
ElemType data; // 存放结点的数据元素。
struct LNode* next; // 指向下一个结点的指针。
};
// 初始化链表，返回值：失败返回 nullptr，成功返回头结点的地址。
LNode* InitList()
{
LNode* head = new (std::nothrow) LNode; // 分配头结点。
if (head == nullptr) return nullptr; // 内存不足，返回失败。
head->next = nullptr; // 头结点的下一结点暂时不存在，置空。
return head; // 返回头结点。
}
// 销毁链表。
void DestroyList(LNode* head)
{
// 销毁链表是指释放链表全部的结点，包括头结点。
LNode* tmp;
while (head != nullptr)
{
tmp = head->next; // tmp 保存下一结点的地址。
delete head; // 释放当前结点。
head = tmp; // 指针移动到下一结点。
}
}
// 在链表的头部插入元素（头插法），返回值：false-失败；true-成功。
bool PushFront(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = head->next;
head->next = tmp;
return true;
}
// 显示链表中全部的元素。
void PrintList(const LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; }
LNode* pp = head->next; // 从第 1 个结点开始。
while (pp != nullptr)
{
cout << pp->data << " "; // 如果元素为结构体，这行代码要修改。
pp = pp->next; // 指针往后移动一个结点。
}
cout << endl;
}
// 在链表的尾部插入元素（尾插法），返回值：false-失败；true-成功。
bool PushBack(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到最后一个结点，pp 将指向尾结点（最后一个结点）。
while (pp->next != nullptr) pp = pp->next;
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = nullptr;
pp->next = tmp;
return true;
}
// 求链表的表长，返回值：>=0-表 LL 结点的个数。
size_t ListLength(LNode* head)
{
//if (head == nullptr) { cout << "链表不存在。\n"; return 0; }
//LNode* pp = head->next; // 头结点不算，从第 1 个结点开始。
//size_t length = 0;
//while (pp != nullptr) { pp = pp->next; length++; }
//return length;
// 不使用临时变量，如何计算链表（包括头结点）的长度？
if (head==nullptr) return 0;
return ListLength(head->next)+1;
}
// 删除链表第一个结点。
bool PopFront(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head->next; // pp 指向第一个节点。
head->next = head->next->next; // 修改头结点的 next 指针。
delete pp; // 删除第一个节点。
return true;
}
// 删除链表最后一个结点。
bool PopBack(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
// 必须加上这个判断，否则下面的循环 pp->next->next 不成立。
if (head->next == nullptr) { cout << "链表为空，没有结点。\n"; return false; }
LNode* pp = head; // 从头结点开始。
// 找到倒数第二个结点（包括头结点）。
while (pp->next->next != nullptr) pp = pp->next;
delete pp->next; // 释放最后一个结点。
pp->next = nullptr; // 倒数第二个结点成了最后一个结点。
return true;
}
// 清空链表，清空链表是指释放链表全部的结点，但是，不释放头结点。
void ClearList(LNode* head)
{
if (head == nullptr) { cout << "链表不存在。\n"; return; } // 判断链表是否存在。
LNode* tmp1;
LNode* tmp2 = head->next; // 从头结点的下一个结点开始释放。
while (tmp2 != nullptr)
{
tmp1 = tmp2->next;
delete tmp2;
tmp2 = tmp1;
}
head->next = nullptr; // 这行代码一定不能少，否则会留下野指针。
}
// 查找元素 ee 在链表中的结点地址，如果没找到返回 nullptr，否则返回结点的地址。
LNode* LocateElem(const LNode* head, const ElemType& ee)
{
LNode* pp = head->next; // 从第 1 个存放数据结点开始。
while (pp != nullptr)
{
// 如果数据元素是结构体，以下代码要修改成比较关键字。
if (pp->data == ee) return pp;
pp = pp->next;
}
return pp;
}
// 获取链表中第 n 个结点，成功返回结点的地址，失败返回 nullptr。
// 注意，n 可以取值为 0，表示头结点。
LNode* LocateNode(LNode* head, unsigned int n)
{
if (head == nullptr) { cout << "链表不存在。\n"; return nullptr; }
LNode* pp = head; // 指针 pp 指向头结点，逐步往后移动，如果为空，表示后面没结
点了。
unsigned int ii = 0; // ii 指向的是第几个结点，从头结点 0 开始，pp 每向后移动一次，
ii 就加 1。
while ((pp != nullptr) && (ii < n))
{
pp = pp->next; ii++;
}
if (pp == nullptr) { cout << "位置" << n << "不合法，超过了表长。\n"; return nullptr; }
return pp;
}
// 在指定结点 pp 之后插入元素 ee。
bool InsertNextNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
LNode* tmp = new LNode;
tmp->data = ee;
tmp->next = pp->next;
pp->next = tmp;
return true;
}
// 在指定结点 pp 之前插入元素 ee。
bool InsertPriorNode(LNode* pp, const ElemType& ee)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
// 在指定结点 pp 之前插入采用偷梁换柱的方法：
// 1、分配一个新的结点；
// 2、把 pp 结点的数据和指针复制到新结点中。
// 3、把待插入元素的数据存入 pp 结点中。
LNode* tmp = new LNode;
// 把 pp 结点的数据和指针复制到 tmp 中。
tmp->data = pp->data;
tmp->next = pp->next;
// 把待插入的元素存入 pp 中。
pp->data = ee;
pp->next = tmp;
return true;
}
// 删除指定结点。
bool DeleteNode1(LNode* pp)
{
if (pp == nullptr) { cout << "结点 pp 不存在。\n"; return false; }
if (pp->next != nullptr) // 如果结点 pp 后面还有结点。
{
// 删除指定结点的思想是：1）把 pp 后继结点的数据和 next 指针复制到 pp 结点；2）删
除 pp 结点的后继结点。
LNode* tmp = pp->next; // tmp 指向 pp 的后继结点。
pp->data = tmp->data; // 把后继结点的数据复制到 pp 结点中。
pp->next = tmp->next; // 把 pp 的 next 指向后继结点的 next。
delete tmp; // 释放后继结点。
return true;
}
else // 如果结点 pp 是最后一个结点。
{
return false; // 可以在函数外面调用 PopBack()函数。
}
}
// 把元素有序的插入链表中，返回值：false-失败；true-成功。
bool PushOrder(LNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链表不存在。\n"; return false; }
LNode* tail = head; // 将指向尾结点。
LNode* pp = head->next; // 从第一个结点开始。
while (pp != nullptr)
{
// 如果结点的元素大于 ee，把 ee 插入该结点前面。
if (pp->data > ee) { InsertPriorNode(pp, ee); return true; }
tail = pp;
pp = pp->next; // 指针后移一个结点。
}
// 如果在上面的循环中没能插入元素，表示 ee 应该插入到链表的尾部。
if (pp == nullptr) return InsertNextNode(tail, ee);
return true;
}
// 采用归并的方法，将两个升序的链表 La 和 Lb，合并成一个升序的链表 Lc。
// 合并后，链表 La 和 Lb 将不再拥有结点（只有头结点）。
void MergeList(LNode *La, LNode *Lb, LNode *Lc)
{
LNode* pa = La->next;
LNode* pb = Lb->next;
LNode* pp;
// 把 pa 和 pb 合并到 Lc 中。
while ((pa != nullptr) && (pb != nullptr))
{
// 取 pa 和 pb 的较小者。
if (pa->data <= pb->data)
{
pp = pa; pa = pa->next;
}
else
{
pp = pb; pb = pb->next;
}
// 把较小的结点 pp 追加到 Lc 中。
Lc->next = pp;
Lc = Lc->next;
}
// 把链表 pa 其它的元素追加到 Lc 中。
if (pa != nullptr) Lc->next = pa;
// 把链表 pb 其它的元素追加到 Lc 中。
if (pb != nullptr) Lc->next = pb;
// 链表 La 和 Lb 的结点已全部转移给了 Lc，需置空，否则 DestroyList()时会引起重复释放结点。
La->next = Lb->next = nullptr;
}
// 桶排序主函数，参数 arr 是待排序数组的首地址，len 是数组元素的个数，bucketnum 是桶的个
数。
void bucketsort(int* arr, int len,int bucketnum)
{
// 分配桶的指针数组。
LNode** buckets = new LNode*[bucketnum];
// 初始化桶。
for (int ii = 0; ii < bucketnum; ii++)
buckets[ii] = InitList();
// 把数组 arr 的数据放入桶中。
for (int ii = 0; ii < len; ii++)
{
PushOrder(buckets[arr[ii] % bucketnum] ,arr[ii]);
}
// 显示每个桶中的元素。
cout << "每个桶中的元素如下：\n";
for (int ii = 0; ii < bucketnum; ii++) PrintList(buckets[ii]);
// 把全部桶中的元素归并到 LL 中。
LNode* LL= InitList();
LNode* tmp = InitList();
for (int ii = 0; ii < bucketnum; ii++)
{
MergeList(buckets[ii], LL, tmp); // 把桶中的链表和 LL 合并到 tmp 中。
swap(LL->next, tmp->next); // 交换 LL 和 tmp 的数据结点。
}
cout << "显示合并后的结果：\n"; PrintList(LL);
// 把合并后的结果保存到数组 arr 中。
LNode* pp = LL->next;
for (int ii = 0; ii < len; ii++)
{
arr[ii] = pp->data; pp = pp->next;
}
DestroyList(LL);
DestroyList(tmp);
// 释放桶。
for (int ii = 0; ii < bucketnum; ii++)
{
DestroyList(buckets[ii]);
}
delete[] buckets; // 释放桶的指针数组。
}
int main()
{
// 以下代码用于测试 PushOrder()函数的功能。
//LNode* LL = InitList(); // 初始化链表 LL。
//cout << "有序的插入元素（5、8、7、4、1、3、9、3、6）。\n";
//PushOrder(LL, 5);
//PushOrder(LL, 8);
//PushOrder(LL, 7);
//PushOrder(LL, 4);
//PushOrder(LL, 1);
//PushOrder(LL, 3);
//PushOrder(LL, 9);
//PushOrder(LL, 3);
//PushOrder(LL, 6);
//PrintList(LL); // 把链表中全部的元素显示出来。
//DestroyList(LL); // 销毁链表 LL。

// 以下代码用于测试 MergeList()函数的功能。
//LNode* La = InitList();
//LNode* Lb = InitList();
//LNode* Lc = InitList();
//PushOrder(La, 5);
//PushOrder(La, 8);
//PushOrder(La, 7);
//PushOrder(La, 4);
//PushOrder(Lb, 1);
//PushOrder(Lb, 3);
//PushOrder(Lb, 9);
//PushOrder(Lb, 2);
//PushOrder(Lb, 6);
//MergeList(La, Lb, Lc); // 把链表 La 和 Lb 合并成 Lc。
//PrintList(Lc); // 把链表 Lc 中全部的元素显示出来。
//DestroyList(La);
//DestroyList(Lb);
//DestroyList(Lc);
//
// 以下代码用于测试桶排序的功能。
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
bucketsort(arr, len,3);
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}