《数据结构》自学考试 课程代码02331 2012版 第07章 排序 例题集和编程练习
- OS: Mac Catalina 10.15.4
- Hardware: Intel Core i9/16G 2667MHz DDR4
- 编译器版本：Mac Xcode 11.6
目录
7.1 插入排序
7.1.1 直接插入排序
7.1.2 希尔排序
7.2 交换排序
7.2.1 冒泡排序
7.2.2 双向冒泡排序
7.2.3 快速排序
7.3 选择排序
7.3.1 直接选择排序
7.3.2 带头结点的单向链表存储结构的直接排序（升序，交换结点方法）
7.3.3 带头结点的单向链表存储结构的直接排序（升序，建立新表方法）
7.3.4 堆排序
7.4 归并排序
7.5 分配排序
7.5.1 箱排序
7.5.2 基数排序
例7.5
7.1 插入排序
7.1.1 直接插入排序
// 插入排序，直接插入排序，对顺序表R做直接插入排序
// 参数:
// SeqList R 顺序表R
// int n 顺序表长度
// 复杂度:
// 时间复杂度: O(n^2)
// 总的比较次数: n^2/4
// 总的移动次数: n^2/4
// 空间复杂度: O(1)
// 返回:
// void
void InsertSort(SeqList R, int n)
{int i, j;printf("初试关键字： [%d],[", R[1].key);for(int k = 2; k <= n; k++)if (k == 2)printf("%d", R[k].key);elseprintf(",%d", R[k].key);printf("]\n");for (i = 2; i <= n; i++){if (R[i].key < R[i - 1].key) // 若R[i].key>=有序区中所有的Key,则R[i]不动{R[0] = R[i]; // 当前记录复制为哨兵for (j = i - 1; R[0].key < R[j].key; j--) // 找插入位置{R[j + 1] = R[j]; // 记录后移}R[j + 1] = R[0]; // R[i]插入到正确位置//输出结果printf("i=%d R[0].key=%d [", i, R[0].key);for(int k = 1; k <= i; k++)if (k == 1)printf("%d", R[k].key);elseprintf(",%d", R[k].key);for(int k = i + 1; k <= n; k++)if (k == i + 1)printf("][%d", R[k].key);elseprintf(",%d", R[k].key);printf("]\n");}}
}
示例程序
#include
#include "Sort.h"int main(void)
{int n = 8;SeqList R; // R为待排序的记录文件R[1].key = 46; R[2].key = 39; R[3].key = 17;R[4].key = 23; R[5].key = 28; R[6].key = 55;R[7].key = 18; R[8].key = 46;printf("开始插入排序...\n");InsertSort(R, n);printf("排序结束.\n");return 0;
}
7.1.2 希尔排序
// 希尔排序中的一趟插入排序,dk为当前增量
// 参数:
// SeqList R 顺序列表
// int dk 当前增量
// int n 顺序表长度
// 返回:
// void
void ShellInsert(SeqList R, int dk, int n)
{int i, j;for (i = dk + 1; i <= n; i++) // 将R[dk+1...n]分别插入有序区{if (R[i].key < R[i - dk].key){R[0] = R[i]; // 暂存在R[0]中j = i - dk;while (j > 0 && R[0].key < R[j].key){R[j + dk] = R[j]; // 记录后移，查找插入位置j = j - dk;}R[j + dk] = R[0]; // 插入R[i]到正确位置}}
}// 按增量序列d[0..t-1]对顺序表R作希尔排序
// 参数:
// SeqList R 顺序列表
// int d[] 增量序列，增量最后一个必须是1，避免增量互为倍数
// int t 增量序列长度
// int n 顺序表长度
// 返回:
// void
void ShellSort(SeqList R, int d[], int t, int n)
{int k;for (k = 0; k < t; k++)ShellInsert(R, d[k], n);
}
程序示例
#include
#include "Sort.h"
#define T 3void p(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}
int main(void)
{int n = 10;SeqList R; // R为待排序的记录文件int d[T] = {5, 3, 1};R[1].key = 36; R[2].key = 25; R[3].key = 48;R[4].key = 27; R[5].key = 65; R[6].key = 25;R[7].key = 43; R[8].key = 58; R[9].key = 76; R[10].key = 32;p(R, n);printf("开始希尔排序...\n");ShellSort(R, d, T, n);printf("排序结束.\n");p(R, n);return 0;
}
7.2 交换排序
7.2.1 冒泡排序
// 采用自底向上扫描数组R[1..n]做冒泡排序
// 参数:
// SeqList R 顺序列表
// int n 顺序表长度
// 返回:
// void
void BubbleSort(SeqList R, int n)
{int i, j, flag;for (i = 1; i < n; i++) // 最多做n-1趟排序{flag = 0; // flag表示每一趟是否有交换，先置0for (j = n; j >= i + 1; j--) // 进行第i趟排序{if (R[j].key < R[j - 1].key){R[0] = R[j - 1]; // R[0]作为交换时的暂存单元R[j - 1] = R[j];R[j] = R[0];flag = 1; // 有交换,flag置1}}for(int k = 1; k <= n; k++)if (k == 1)printf("第%d趟 排序结果：%d", i, R[k].key);elseprintf(",%d", R[k].key);printf("\n");if (flag == 0) return;}
}示例程序：
#include
#include "Sort.h"void p(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 8;SeqList R;R[1].key = 36; R[2].key = 28; R[3].key = 45; R[4].key = 13; R[5].key = 67;R[6].key = 36; R[7].key = 18; R[8].key = 56;printf("初始状态: ");p(R, n);BubbleSort(R, n);printf("排序完成.\n");return 0;
}
7.2.2 双向冒泡排序
// 自底向上、自顶向下交替进行双向扫描冒泡排序
// 参数:
// SeqList R 顺序列表
// int n 顺序表长度
// 返回:
// void
void DBubbleSort(SeqList R, int n)
{int i = 1, j;RecType t; // t作为排序交换记录的中间变量int NoSwap; // 表示一趟扫描是否有交换，为假无交换NoSwap = 1; // 首先假设有交换，表示无序while (NoSwap) // 当有交换时做循环{NoSwap = 0; // 置成无交换for (j = n - i + 1; j >= i + 1; j--) // 自底向上扫描{if (R[j].key < R[j - 1].key) // 若反序（后面的小于前一个），即交换{t = R[j];R[j] = R[j - 1];R[j - 1] = t;NoSwap = 1; // 说明有交换}}for (j = i + 1; j <= n - i; j++) // 自顶向下扫描{if (R[j].key > R[j + 1].key) // 若反序（前面的大于后一个），即交换{t = R[j];R[j] = R[j + 1];R[j + 1] = t;NoSwap = 1; // 说明有交换}}for(int k = 1; k <= n; k++)if (k == 1)printf("第%d趟: %d", i, R[k].key);elseprintf(",%d", R[k].key);printf("\n");i = i + 1;}
}程序示例:
#include
#include "Sort.h"void p(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 8;SeqList R;R[1].key = 36; R[2].key = 28; R[3].key = 45; R[4].key = 13; R[5].key = 67;R[6].key = 36; R[7].key = 18; R[8].key = 56;printf("初始状态: "); p(R, n);DBubbleSort(R, n);printf("排序结果: "); p(R, n);printf("双向冒泡排序完成.\n");return 0;
}
7.2.3 快速排序
// 对R[i]...R[j]区间内的记录进行一次划分排序
// 参数:
// SeqList R 顺序列表
// int i 左端点
// int j 右端点
// 返回:
// int 基准记录位置索引
int Partition(SeqList R, int i, int j)
{RecType x = R[i]; // 用区间的第一个记录为基准while (i < j){while (i < j && R[j].key >= x.key)j--; // 从j所指位置起向前（左）搜索if (i < j){R[i] = R[j];i++;}while (i < j && R[i].key <= x.key)i++; // 从i所指位置起向后（右）搜索if (i < j){R[j] = R[i];j--;}}R[i] = x; // 基准记录x位于最终排序的位置上return i;
}// 对顺序表R中的子区间进行快速查询
// 参数:
// SeqList R 顺序列表
// int low 左端点
// int high 右端点
// 返回:
// void
void QuickSort(SeqList R, int low, int high)
{int p;static int k = 1;if (low < high) // 长度大于1{p = Partition(R, low, high); // 做一次划分排序QuickSort(R, low, p - 1); // 对左区间递归排序QuickSort(R, p + 1, high); // 对右区间递归排序}
}程序示例：
#include
#include "Sort.h"void p(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 10;SeqList R;R[1].key = 45; R[2].key = 53; R[3].key = 18; R[4].key = 36; R[5].key = 76;R[6].key = 32; R[7].key = 49; R[8].key = 97; R[9].key = 13; R[10].key = 36;printf("初始状态: "); p(R, n);QuickSort(R, 1, n);printf("排序结果: "); p(R, n);printf("快速排序完成.\n");return 0;
}
7.3 选择排序
7.3.1 直接选择排序
// 选择排序，直接选择排序，对R作直接选择排序
// 参数:
// SeqList R 顺序列表
// int n 顺序表长度
// 返回:
// void
// 复杂度:
// 总比较次数： n(n-1)/2
// 总移动次数(最大值): 3(n-1)
// 平均时间复杂度: O(n^2)
void SelectSort(SeqList R, int n)
{int i, j, k;for (i = 1; i < n; i++) // 做n-1趟排序{k = i; // 设k为第i趟排序中关键字最小的记录位置for (j = i + 1; j <= n; j++) // 在[i..n]选择关键字最小的记录{if (R[j].key < R[k].key)k = j; // 若有比R[k].key小的记录，记住该位置}if (k != i) // 与第i个记录交换{R[0] = R[i];R[i] = R[k];R[k] = R[0];}printf("第%d次排序后:", i);for(int m = 1; m <= n; m++){if (m == 1)printf(" %d", R[m].key);elseprintf(",%d", R[m].key);}printf("\n");}
}程序示例:
#include
#include "Sort.h"void p(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 8;SeqList R;R[1].key = 38; R[2].key = 33; R[3].key = 65; R[4].key = 82; R[5].key = 76;R[6].key = 38; R[7].key = 24; R[8].key = 11;printf("初始状态: "); p(R, n);SelectSort(R, n);printf("排序结果: "); p(R, n);printf("直接选择排序完成.\n");return 0;
}
7.3.2 带头结点的单向链表存储结构的直接排序（升序，交换结点方法）
// 选择排序，带头结点的链式存储选择排序，交换结点方法
// 先找到最小的和第一个结点交换，再找次小的和第二个结点交换，...，以此类推
// 参数:
// LinkList head 单向链表
// 返回:
// void
// 复杂度:
// 平均时间复杂度: O(n^2)
void LSelectSort1(LinkList head)
{ListNode *p, *r, *s;ListNode q;p = head->next; // 链表带头结点while (p != NULL){s = p; // s为保存当前关键字值最小结点地址指针r = p->next;while (r != NULL) // 向后比较，找关键字值最小的结点{if (r->data < s->data)s = r; // 若r指向结点的关键字值最小，使s指向它r = r->next; // 比较下一个}if (s != p) // 说明有关键字值比s的关键字值小的结点，需交换{q = (*p); // 整个结点记录赋值p->data = s->data;s->data = q.data;}p = p->next; // 指向下一个结点}
}
程序示例：
#include
#include "Sort.h"void p(LinkList L)
{ListNode *p = L->next;int i = 1;while (p != NULL){printf("[%d]=%d ", i++, p->data);p = p->next;}printf("\n");
}int main(void)
{LinkList L = CreateLinkList();InsertList(L, 1, (DataType)38);InsertList(L, 2, (DataType)33);InsertList(L, 3, (DataType)65);InsertList(L, 4, (DataType)82);InsertList(L, 5, (DataType)76);InsertList(L, 6, (DataType)38);InsertList(L, 7, (DataType)24);InsertList(L, 8, (DataType)11);printf("排序前，链表内容: "); p(L);LSelectSort1(L);printf("排序后，链表内容: "); p(L);return 0;
} 
7.3.3 带头结点的单向链表存储结构的直接排序（升序，建立新表方法）
// 选择排序，带头结点的单向链式存储选择排序，创建新链表方法
// 先找到最小的和第一个结点交换，再找次小的和第二个结点交换，...，以此类推
// 参数:
// LinkList head 单向链表
// 返回:
// LinkList 创建后的新链表
// 复杂度:
// 平均时间复杂度: O(n^2)
LinkList LSelectSort2(LinkList head)
{ListNode *p, *q, *r, *s, *t, *t1;t = CreateLinkList(); t1 = t->next; // 置空新表，采用尾插建立新链表while (head->next != NULL){s = head->next; // 先假设s指向关键字最小的结点p = head->next; q = NULL; // q指向p的前趋结点r = NULL; // r指向s的后趋结点while (p != NULL){if (p->data < s->data) // 使s指向当前关键字值小的结点{s = p; r = q; // 使r指向s的前一个结点}q = p; p = p->next; // 指向后继结点}if (s == head->next) // 循环前的假设成立head->next = head->next->next; // 指向后继结点elser->next = s->next; // 删除最小结点if (t->next == NULL) // t1指向新表的当前尾结点{t->next = s;t1 = t->next;} else // 插入新结点{t1->next = s;t1 = s;}}t1 ->next = NULL;return t;
}
程序示例：
#include
#include "Sort.h"void p(LinkList L)
{ListNode *p = L->next;int i = 1;while (p != NULL){printf("[%d]=%d ", i++, p->data);p = p->next;}printf("\n");
}int main(void)
{LinkList L = CreateLinkList();LinkList L2 = CreateLinkList();InsertList(L, 1, (DataType)38);InsertList(L, 2, (DataType)33);InsertList(L, 3, (DataType)65);InsertList(L, 4, (DataType)82);InsertList(L, 5, (DataType)76);InsertList(L, 6, (DataType)38);InsertList(L, 7, (DataType)24);InsertList(L, 8, (DataType)11);printf("排序前，链表内容: "); p(L);L2 = LSelectSort2(L);printf("排序后，链表内容: "); p(L2);return 0;
} 
7.3.4 堆排序
// 大根堆排序
// 将R[i..h]调整为大根堆，假定R[i]的左、右子树均满足堆性质
// 参数:
// SeqList R 顺序列表
// int i 序列i
// int h 序列h
// 返回:
// void
void Sift(SeqList R, int i, int h)
{int j;RecType x = R[i]; // 把待筛结点暂存于x中j = 2 * i; // R[j]是R[i]的左孩子while (j <= h) // 当R[i]的左孩子不空时执行循环{if (j < h && R[j].key < R[j + 1].key)j++; // 若右孩子的关键字较大，j为较大右孩子下标if (x.key >= R[j].key)break; // 找到x的最终位置，终止循环R[i] = R[j]; // 将R[j]调整到双亲位置上i = j; j = 2 * i; // 修改i和j的值，使i指向新的调整点}R[i] = x; // 将被筛结点放入最终的位置上
}void p(SeqList R, int n)
{static int k =1;for(int i = 1; i <= n; i++)if (i == 1)printf("第%d趟排序结果: %d", k, R[i].key);elseprintf(",%d", R[i].key);printf("\n");k++;
}// 选择排序，堆排序
// 对R[1..n]进行堆排序，设R[0]为暂存单元
// 参数:
// SeqList R 顺序列表
// int n 顺序列表长度
// 返回:
// void
// 复杂度:
// 平均时间复杂度: O(log2 N)
// 排序稳定: 不稳定
void HeapSort(SeqList R, int n)
{int i;for (i = n / 2; i > 0; i--)Sift(R, i, n); // 对初始数组R[1..n]建大根堆for (i = n; i > 1; i--) // 对R[1..i]进行堆排序，共n-1趟{R[0] = R[1]; R[1] = R[i]; R[i] = R[0];Sift(R, 1, i - 1); // 对无序区R[1..i-1]建大根堆p(R, n);}
}
程序示例：
#include
#include "Sort.h"int main(void)
{int n = 8;SeqList R; // R为待排序的记录文件R[1].key = 47; R[2].key = 33; R[3].key = 61;R[4].key = 56; R[5].key = 72; R[6].key = 11;R[7].key = 25; R[8].key = 47;printf("开始堆排序...\n");HeapSort(R, n);printf("排序结束.\n");
}
7.4 归并排序
// 对有序的R[low..m]和R[m+1..high]归并为有序的MR[low..high]
// 参数:
// SeqList R 原有序列表
// SeqList MR 归并后的有序列表
// int low 左序列起始位置
// int m 截断位置
// int high 右序列截止位置
// 返回:
// void
void Merge(SeqList R, SeqList MR, int low, int m, int high)
{int i, j, k;i = low; j = m + 1; k = low; // 初始化while (i <= m && j <= high){if (R[i].key <= R[j].key)MR[k++] = R[i++];elseMR[k++] = R[j++];}while (i <= m)MR[k++] = R[i++]; // 将R[low..m]中剩余的复制到MR中while (j <= high)MR[k++] = R[j++]; // 将R[m+1..high]中剩余的复制到MR中
}// 对R[1..n]做一趟归并排序
// 参数:
// SeqList R 原有序列表
// SeqList MR 归并后的有序列表
// int len 归并长度
// int n 原序列长度
// 返回:
// void
void MergePass(SeqList R, SeqList MR, int len, int n)
{int i, j;for (i = 1; i + 2 * len - 1 <= n; i = i + 2 * len)Merge(R, MR, i, i + len - 1, i + 2 * len - 1);if (i + len - 1 < n) // 尚有两个子文件，其中最后一个长度小于lenMerge(R, MR, i, i + len - 1, n);else // 文件个数为奇数，最后一个子文件复制到MR中{for (j = i; j <= n; j++)MR[j] = R[j];}
}void p2(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}// 对R[1..n]进行并归排序
// 参数:
// SeqList R 原有序列表
// SeqList MR 归并后的有序列表
// int n 原序列长度
// 返回:
// void
// 复杂度:
// 时间复杂度: O(nlog2 n)
// 总趟数: int(log2 n)
// 排序稳定: 稳定
void MergeSort(SeqList R, SeqList MR, int n)
{int len = 1;static int k = 1;while (len < n){MergePass(R, MR, len, n);printf("第%d趟归并：", k++); p2(MR, n);len = len * 2;MergePass(MR, R, len, n);printf("第%d趟归并：", k++); p2(R, n);len = len * 2;}
}
程序示例：
#include
#include "Sort.h"void p(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 7;SeqList R; // R为待排序的记录文件SeqList MR; //排序结果保存位置R[1].key = 72; R[2].key = 18; R[3].key = 53;R[4].key = 36; R[5].key = 48; R[6].key = 31;R[7].key = 36;printf("排序前: "); p(R, n);printf("开始堆排序...\n");MergeSort(R, MR, n);printf("排序后: "); p(MR, n);printf("排序结束.\n");
}
7.5 分配排序
7.5.1 箱排序
// 对R[1..n]进行箱排序
// 参数:
// SeqList R 原有序列表
// int n 原序列长度
// 返回:
// void
// 复杂度:
// 时间复杂度: O(n)
// 比较次数: int(log2 n)
void BinSort(SeqList R, LinkQueue *Q, int n)
{int i, j;KeyType k;int m = 100;LinkQueue B[100];QueueNode *p;for (i = 1; i <= m; i++)InitQueue(&B[i]); // 置空所有的链队列for (i = 1; i <= n; i++){k = R[i].key; // 分配EnQueue(&B[k], k); // 装箱}i= 1;while (IsQueueEmpty(&B[i])) // 找到第一个非空箱子i++;p = B[i].rear->next->next; // r指向排序后的第一个记录while (p != B[i].rear->next){EnQueue(Q, (*p).data);p = p->next;}for (j = i + 1; j <= m; j++){if (!IsQueueEmpty(&B[j])) // 将所指向记录链接到上一个非空箱子的尾指针所指向的结点之后{p = B[j].rear->next->next;while (p != B[j].rear->next){EnQueue(Q, (*p).data);p = p->next;}}}
}程序范例：
#include
#include "Sort.h"void ptr(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 11, i;SeqList R; // R为待排序的记录文件LinkQueue Q;InitQueue(&Q);QueueNode *p;R[1].key = 36; R[2].key = 25; R[3].key = 48;R[4].key = 10; R[5].key = 32; R[6].key = 25;R[7].key = 6; R[8].key = 58; R[9].key = 56; R[10].key = 82; R[11].key = 6;printf("排序前: "); ptr(R, n);printf("开始堆排序...\n");BinSort(R, &Q, n);p = Q.rear->next->next;printf("排序后队列内容为:\n");i = 1;while (p != Q.rear->next){printf("[%d]=%d ", i++, p->data);p = p->next;}printf("\n排序结束.\n");
}
7.5.2 基数排序
//-----------------------------------------------------------
// 对R[1..n]进行基数排序
// 参数:
// SeqList R 待排序列表
// int n 序列长度
// 返回:
// void
// 复杂度:
// 时间复杂度: O(n)
// 比较次数: int(log2 n)
//-----------------------------------------------------------
void BinSort(SeqList R, LinkList L, int n)
{int i, j, round = 1, maxRound = 1;KeyType k;ListNode *p;bool sign = false; // 标记位，用来记录基数位是否有变化LinkList B[DECMIAL_BASE]; // 链表数组，大小为十进制基数，即0～9for (i = 0; i < DECMIAL_BASE; i++) // 初始化10个链表B[i] = CreateLinkList();while (round <= maxRound) // 使用基数拆分排序，直到最高位已经排序过{for (i = 1; i <= n; i++) // 逐个装入箱子{if (!sign &&(R[i].key / (int)(pow(10, round))) % 10 > 0) // 如果最大基数位未变化或者最大基数位不能整除{ // 说明最大基数位无需变化maxRound++; // 最大基数位+1sign = true; // 最大基数位发生了变化}k = (R[i].key / (int)(pow(10, round - 1))) % 10; // 个位、十位、百位...以此类推p = (ListNode*)malloc(sizeof(ListNode)); // 创建存储空间p->data = R[i].key;AddNode(B[k], p); // 装入箱子}printf("第【%d】趟装箱结果:\n", round);j = 1;for (i = 0; i < DECMIAL_BASE; i++) // 将箱子从最低序号开始提取出来并重新排队{p = B[i]->next;printf("\t\t\tB[%d]=", i);while (p != B[i]){printf("%d,", p->data);R[j++].key = p->data;p = p->next;}printf("\n");}printf("第【%d】趟排序结果:\n", round); // 显示排队后的结果printf("\t\t\t");for(i = 1; i <= n; i++){printf("%d ", R[i].key);}printf("\n");printf("----------------------------------\n");for (i = 0; i < DECMIAL_BASE; i++) // 将箱子清空，未下一个基数位装箱做准备ClearAllNode(B[i]);round++; // 趟数+1，即进入百分位、千分位等等sign = false; // 设置最高基数位可变化}
}#include
#include "Sort.h"void ptr(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 10;SeqList R; // R为待排序的记录文件LinkList L;L = CreateLinkList();R[1].key = 36; R[2].key = 25; R[3].key = 48;R[4].key = 10; R[5].key = 32; R[6].key = 25;R[7].key = 6; R[8].key = 58; R[9].key = 56; R[10].key = 82;printf("排序前: "); ptr(R, n);printf("开始堆排序...\n");BinSort(R, L, n);printf("\n排序结束.\n");
}
例7.5
已知关键字序列{278,109,63,930,589,184,505,269,8,83}写出基数排序（升序）的过程
#include
#include "Sort.h"void ptr(SeqList R, int n)
{for(int i = 1; i <= n; i++)if (i == 1)printf("%d", R[i].key);elseprintf(",%d", R[i].key);printf("\n");
}int main(void)
{int n = 10;SeqList R; // R为待排序的记录文件LinkList L;L = CreateLinkList();R[1].key = 278; R[2].key = 109; R[3].key = 63;R[4].key = 930; R[5].key = 589; R[6].key = 184;R[7].key = 505; R[8].key = 269; R[9].key = 8; R[10].key = 83;printf("排序前: "); ptr(R, n);printf("开始堆排序...\n");BinSort(R, L, n);printf("\n排序结束.\n");
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！