绿色门户网站模板下载河北建设厅网站

当前位置： 首页 > news >正文

绿色门户网站模板下载,河北建设厅网站,自适应网站内容区做多大合适,网站备案协议书内部排序 文章目录 内部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序10.2.2.1 折半插入排序(Binary Insertion Sort)10.2.2.2 2-路插入排序#xff08;Two-Way Insertion Sort#xff09;10.2.2.3 表插入排序#xff08;Table Insertion Sort#xf…内部排序 文章目录 内部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序10.2.2.1 折半插入排序(Binary Insertion Sort)10.2.2.2 2-路插入排序Two-Way Insertion Sort10.2.2.3 表插入排序Table Insertion Sort 10.2.3 希尔排序(Shells Sort) 10.3 交换排序10.3.1 冒泡排序(Bubble Sort)10.3.2 快速排序(Quick Sort) 10.4 选择排序10.4.1 简单选择排序(Simple Selection Sort)10.4.2 树形选择排序(Tree Selection Sort)10.4.3 堆排序(Heap Sort) 10.5 归并排序(Merging Sort)10.6 基数排序(Radix Sorting)10.6.1 多关键字的排序10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论 10.1 概述 排序 将一组杂乱无章的数据按一定规律顺次排列起来。即将无序序列排成一个有序序列 (由小到大或由大到小) 的运算。 如果参加排序的数据结点包含多个数据域那么排序往往是针对其中某个域而言。 排序方法分类 按数据存储介质: 内部排序和外部排序 内部排序数据量不大、数据在内存无需内外存交换数据外部排序数据量较大、数据在外存(文件排序) —— 外部排序时要将数据分批调入内存来排序中间结果还要及时放入外存 按比较器个数: 串行排序和并行排序 串行排序单处理机(同一时刻比较一对元素)并行排序多处理机(同一时刻比较多对元素) 按主要操作: 比较排序和基数排序 比较排序用比较的方法 —— 插入排序、交换排序、选择排序、归并排序基数排序不比较元素的大小仅仅根据元素本身的取值确定其有序位置。 按辅助空间: 原地排序和非原地排序 原地排序辅助空间用量为O(1)的排序方法(所占的辅助存储空间与参加排序的数据量大小无关)·非原地排序辅助空间用量超过O(1的排序方法(所占的辅助存储空间与参加排序的数据量大小有关)· 按稳定性: 稳定排序和非稳定排序 稳定排序能够使任何数值相等的元素排序以后相对次序不变。例如直接插入排序 非稳定性排序数值相等的元素排序以后相对次序改变。例如简单选择排序 排序方法是否稳定并不能衡量一个排序算法的优劣。 按自然性: 自然排序和非自然排序 自然排序输入数据越有序排序的速度越快的排序方法。非自然排序输入数据越有序排序的速度慢的排序方法。
存储结构 顺序表存储待排序的一组记录存放在地址连续的一组存储单元上。记录之间的次序关系由其存储位置决定则实现排 序必须借助移动记录 # define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字//InfoType otherinfo; //其它数据项 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;链表存储待排序记录存放在静态链表中记录之间的次序关系由 指针指示则实现排序不需要移动记录仅需修改指针即可 地址存储待排序记录本身存储在一组地址连续的存储单元内同时另设一个指示各个记录存储位置的地址向量在排序过 程中不移动记录本身而移动地址向量中这些记录的“地址,在排序结束之后再按照地址向量中的值调整记录的存储位置。
10.2 插入排序 插入排序 在有序序列中插入一个元素保持序列有序有序长度不断增加。 有序插入方法 在插入a[i]前数组a的前半段(a[0]~a[i-1])是有序段, 后半段(a[i]~a[n-1])是停留于输入次序的“无序段“插入a[i]使a[0]~a[i-1]有序也就是要为a[i]找到有序位置j (0≤j≤i) ,将a[i]插入在a[j]的位置上。 根据找插入位置方法不同分为 顺序法定位插入位置直接插入排序二分法定位插入位置二分插入排序缩小增量多遍插入排序希尔排序 10.2.1 直接插入排序 实现排序的基本操作有两个: ​ (1) “比较”序列中两个关键字的大小; ​ (2) “移动”记录。 #includestdio.h# define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;void InsertSort(SqList* L) {int i, j;for (i 2; i L-length; i){if (L-r[i].key L-r[i - 1].key) //后面比前面数小则需要进行排序{L-r[0] L-r[i]; // 复制插入元素到哨兵//记录后移寻找插入位置L-r[i] L-r[i - 1];for (j i - 2; L-r[0].key L-r[j].key; j–){L-r[j 1] L-r[j];}//插人到正确位置L-r[j 1] L-r[0];}//后面数大于等于前面数只需继续循环比较下一个数} }int main() {int i;int r[7] {32,12,24,5,16,43,20};SqList L;L.length 7;for (i 0; i 7; i){L.r[i 1].key r[i];}InsertSort(L);for (i 0; i 7; i){printf(%d , L.r[i 1].key);}return 0; }n个元素 最好情况顺序有序 比较次数 ∑ i 2 n 1 n − 1 \sum{i2}^{n}1 n-1 i2∑n​1n−1移动次数0时间复杂度 O(n) 最坏情况逆序有序 比较次数平均值 ∑ i 2 n i ( n 2 ) ( n − 1 ) 2 \sum{i2}^{n}i \frac{(n2)(n-1)}{2} i2∑n​i2(n2)(n−1)​ 移动次数平均值 ∑ i 2 n ( i 1 ) ( n 4 ) ( n − 1 ) 2 \sum{i2}^{n}(i1) \frac{(n4)(n-1)}{2} i2∑n​(i1)2(n4)(n−1)​ 时间复杂度 O(n2)
平均情况 比较次数平均值 ∑ i 2 n i 1 2 ( n 2 ) ( n − 1 ) 4 \sum{i2}^{n}\frac{i1}{2} \frac{(n2)(n-1)}{4} i2∑n​2i1​4(n2)(n−1)​移动次数平均值 ∑ i 2 n ( i 1 2 1 ) ( n 6 ) ( n − 1 ) 4 \sum_{i2}^{n}(\frac{i1}{2}1) \frac{(n6)(n-1)}{4} i2∑n​(2i1​1)4(n6)(n−1)​时间复杂度 O(n2) - 最坏的情况的一半 空间复杂度O(1) 稳定性稳定 原始数据越接近有序排序速度越快 10.2.2 其他插入排序 10.2.2.1 折半插入排序(Binary Insertion Sort) 插入排序的基本操作是在一个有序表中进行查找和插入这个“查找“操作可利用“折半查找”来实现再进行插入则称之为折半插入排序(Binary Insertion Sort) #includestdio.h# define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;void BInsertSort(SqList* L) {int i, j;for (i 2; i L-length; i){L-r[0] L-r[i]; // 复制插入元素到哨兵int low 1;int high i - 1;while (low high) { //在 r[low.. high]中折半查找有序插入的位置int m (low high) / 2; // 折半if (L-r[0].key L-r[m].key) //插入点在低半区{high m - 1;}else { //插入点在高半区low m 1;}}//循环结束high1 则为插入位置for (j i - 1; jhigh1; j–){L-r[j 1] L-r[j]; //记录后移}L-r[high 1] L-r[0]; // 插入} }int main() {int i;int r[7] {32,12,24,5,16,43,20};SqList L;L.length 7;for (i 0; i 7; i){L.r[i 1].key r[i];}BInsertSort(L);for (i 0; i 7; i){printf(%d , L.r[i 1].key);}return 0; }折半插入排序特点 折半查找比顺序查找快关键码比较次数与待排座对象序列的初始排列无关仅依赖于对象个数。当n较大时总关键码比较次数比直接插入排序的最坏情况要好得多但比其最好情况要差;在对象的初始排列已经按关键码排好序或接近有序时直接插入排序比折半插入排序执行的关键码比较次数要少;平均性能优于直接插入排序 n个元素 折半插入排序仅减少了关键字间的比较次数而记录的移动次数不变 时间复杂度仍为O(n2) 空间复杂度O(1) 稳定性稳定 10.2.2.2 2-路插入排序Two-Way Insertion Sort 2- 路插入排序是在折半插入排序的基础上再改进之其目的是减少排序过程中移动 记录的次数但为此需要n个记录的辅助空间。 初始化一个与原数组一样大小的辅助数组d并将原数组的第一个元素放入辅助数组的第一个位置。将d看成是一个循环向量,并设两个指针 first 和 final分别指示排序过程中得到的有序序列中的第一个和最后一个记录在d中的位置。从第二个元素开始遍历原数组对于每个待排序元素 如果待排序元素小于辅助数组的最小值则通过移动first将其插入到最小值之前。如果待排序元素大于辅助数组的最大值则过移动final将其插入到最大值之后。否则通过移动final将大于的数值向后移动并将待排序元素插入到适当的位置。 处理完所有元素后将辅助数组中的元素复制回原数组完成排序。 #includestdio.h #includestdlib.h#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;void TwoWayInsertSort(SqList* L) {/* 初始化一个与原数组一样大小的辅助数组 /RedType d;d (RedType*)malloc((L-length) * sizeof(RedType));if (d NULL) {return;}/* 设L的第1个记录为d中排好序的记录(在位置[0]) /d[0] L-r[1];/ first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 /int first, final;first final 0;int i, j;/ 依次将L的第2个最后1个记录插入d中 /for (i 2; i L-length; i) {if (L-r[i].key d[first].key) {/ 待插记录小于d中最小值插到d[first]之前(不需移动d数组的元素) /first (first - 1 L-length) % L-length;d[first] L-r[i];}else if (L-r[i].key d[final].key) {/ 待插记录大于d中最大值插到d[final]之后(不需移动d数组的元素) /final;d[final] L-r[i];}else {/ 待插记录大于d中最小值小于d中最大值插到d的中间(需要移动d数组的元素) /j final;while (L-r[i].key d[j].key){d[(j 1) % L-length] d[j];j (j - 1 L-length) % L-length;}d[j 1] L-r[i];}}for (i 1; i L-length; i) { // 修改循环条件L-r[i] d[i - 1]; // 将排序后的元素放回L中}for (i 1; i L-length; i) { // 输出排序后的Lprintf(%d , L-r[i].key);}printf(\n);printf(在L中first: %d \n, first 1);printf(在L中final: %d , final 1);free(d); // 释放内存 }int main() {int i;int r[8] { 49,38,65,97,76,13,27,49 };SqList L;L.length 8;for (i 1; i L.length; i) {L.r[i].key r[i - 1];}TwoWayInsertSort(L);return 0; }n个元素 ‌时间复杂度‌2-路插入排序的时间复杂度为O(n2)移动次数大约为n2/8次尽管减少了移动次数但并不能完全避免移动操作。 ‌空间复杂度‌需要额外的辅助数组空间复杂度为O(n)。 10.2.2.3 表插入排序Table Insertion Sort 在排序过程中不移动记 录只有改变存储结构 算法思路 初始化表头结点设数组中下标为0的分量为表头结点并令表头结点记录的关键字取最大整数 MAXINT表插入排序的过程 首先将静态链表中数组下标为1的分量结点和表头结点构成一个循环链表然后依次将下标为2至n的分量结点按记录关键字非递减有序插人到循环链表中 #includestdio.h #includelimits.h#define MAXSIZE 20 // 设记录不超过20个 #define MAXVALUE INT_MAX // 定义最大值typedef struct SLNode {int data; // 存储数据int link; // 存储指向下一个元素的索引 }SLNode, Table[MAXSIZE];void TableInsertSort(Table tb, int n) {//与第一个数据元素构成循环列表(*tb)[0].link 1; // 初始化顺序表的头结点将其link指向第一个数据元素int p, q; // 用于在排序过程中存储当前元素和前驱元素的索引for (int i 2; i n; i) // 从第二个元素开始遍历{p (*tb)[0].link; q 0;while (p ! 0 (*tb)[p].data (*tb)[i].data){q p; //q是p的前驱p (*tb)[p].link; // p更新为下一个元素的索引}(*tb)[i].link (*tb)[q].link; // 将i插入到q的后面(tb)[q].link i; // 更新q的link使其指向i} }int main() {int i;int r[9] { 0,49,38,65,97,76,13,27,49 };Table tb;// 初始化表头结点tb[0].data MAXVALUE;tb[0].link 0;for (i 1; i 9; i){tb[i].data r[i];tb[i].link 0;}TableInsertSort(tb, 9);for (i 0; i 9; i){if (tb[i].data MAXVALUE){printf(%c , M);continue;}printf(%d , tb[i].data);}printf(\n);for (i 0; i 9; i){printf(%d , tb[i].link);}return 0; }10.2.3 希尔排序(Shell’s Sort) 又称“缩小增量排序(Diminishing Increment Sort) 基本思想 先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序待整个序列中的记录“基本有序”时再对全体记录进行一次直接插入排序。 选择一个增量序列 DkDM DM-1 … D1 1 必须递减对每个Dk进行“Dk-间隔”插入排序K MM-1…1 #includestdio.h #includestdlib.h#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;void ShellInsert(SqList L, int dk) {int i, j;for (i dk 1; i L-length; i)// 从第dk1个元素开始向后遍历顺序表{ if (L-r[i].key L-r[i - dk].key)// 如果当前元素的key小于它dk位置前的元素的key{ L-r[0] L-r[i];// L-r[0]是暂存单元暂存当前元素for (j i - dk; j 0 (L-r[0].key L-r[j].key); j j - dk){// 从当前元素向前遍历步长为dkL-r[j dk] L-r[j]; // 将比暂存元素大的元素向后移动dk个位置}L-r[j dk] L-r[0]; // 将暂存的元素插入到正确的位置}} }void ShellSort(SqList *L, int dlta[], int t) {int i, k;for (k 0; k t; k){ShellInsert(L, dlta[k]);printf(\n第 D%d 增量序列排序结果\n, dlta[k]);for (i 1; i 13; i){printf(%d , L-r[i].key);}} }int main() {int i;int r[13] { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length 13;for (i 1; i L.length; i) {L.r[i].key r[i - 1];}// 增量序列int dlta[3] { 5,3,1 };ShellSort(L, dlta, 3);printf(\n—————–\n);printf(排序结果\n);for (i 1; i 13; i){printf(%d , L.r[i].key);}return 0; }希尔排序算法效率与增量序列的取值有关 Hibbard增量序列 Dk 2 k-1 —— 相邻元素互质最坏: Tworst O(n3/2)猜想: Tavg O(n5/4) Sedgewick增量序列 {1,5,19,41,109,……} —— 9 * 4i - 9 * 2i 1 或 4i - 3 * 2i 1最坏: Tworst O(n4/3)猜想: Tavg O(n7/6) 稳定性不稳定 时间复杂度O(n1.25) ~ O(1.6n1.25) – 经验公式 ​ 最好O(n) ​ 最坏O(n2) ​ 最好~O(n1.3) 空间复杂度O(1) 不宜在链式存储结构上实现 10.3 交换排序 交换排序两两比较如果发生逆序则交换直到所有记录都排好序为止。 10.3.1 冒泡排序(Bubble Sort) 基本思想: 每趟不断将记录两两比较并按“前小后大”规则交换 #includestdio.h #includestdlib.h#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;void bubble_sort(SqList *L) {int i, j;RedType x; // 交换时临时存储for (i 1; i L-length - 1; i) // 需要比较i趟n个记录 总共n-1趟{for (j 1; j L-length - i; j) // 每一趟需要比较的次数n个记录比较n-i次{if (L-r[j].key L-r[j 1].key) // 比较 {//发生逆序 - 交换x L-r[j]; L-r[j] L-r[j 1];L-r[j 1] x;}}printf(\n第 %d 趟排序结果\n, i);for (j 1; j L-length; j){printf(%d , L-r[j].key);}} }int main() {int i;int r[13] { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length 13;for (i 1; i L.length; i) {L.r[i].key r[i - 1];}bubble_sort(L);printf(\n—————–\n);printf(排序结果\n);for (i 1; i 13; i){printf(%d , L.r[i].key);}return 0; }改进冒泡处理过程中没有进行任何交换说明序列已有序则停止交换 #includestdio.h #includestdlib.h#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;void bubble_sort(SqList L) {int i, j;int flag 1;RedType x; // 交换时临时存储for (i 1; (i L-length - 1) (flag 1); i) // 需要比较i趟n个记录 总共n-1趟{flag 0;for (j 1; j L-length - i; j) // 每一趟需要比较的次数n个记录比较n-i次{if (L-r[j].key L-r[j 1].key) // 比较 {flag 1;//发生逆序 - 交换x L-r[j]; L-r[j] L-r[j 1];L-r[j 1] x;}}printf(\n第 %d 趟排序结果\n, i);printf(flag %d \n, flag);for (j 1; j L-length; j){printf(%d , L-r[j].key);}} }int main() {int i;int r[13] { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length 13;for (i 1; i L.length; i) {L.r[i].key r[i - 1];}bubblesort(L);printf(\n—————–\n);printf(排序结果\n);for (i 1; i 13; i){printf(%d , L.r[i].key);}return 0; }最好情况正序 比较次数n-1移动次数0时间复杂度 O(n) 最坏情况逆序 比较次数平均值 ∑ i 1 n − 1 ( n − i ) ( n 2 − n ) 2 \sum{i1}^{n-1}(n - i) \frac{(n^2-n)}{2} i1∑n−1​(n−i)2(n2−n)​ 移动次数平均值 3 ∑ i 1 n − 1 ( n − i ) 3 ( n 2 − n ) 2 3\sum_{i1}^{n-1}(n - i) \frac{3(n^2-n)}{2} 3i1∑n−1​(n−i)23(n2−n)​ 时间复杂度 O(n2)
平均情况 时间复杂度 O(n2) 空间复杂度O(1) 稳定性稳定 10.3.2 快速排序(Quick Sort) 基本思想: 任取一个元素 (如:第一个) 为中心pivot - 可以是第一个数、最后一个数、最中间一个数、任选一个数等 所有比它小的元素一律前放比它大的元素一律后放形成左右两个子表; 对各子表重新选择中心元素并依此规则调整 【递归思想】 直到每个子表的元素只剩一个 #includestdio.h #includestdlib.h#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;int Partition(SqList L, int low, int high) {int pivotkey L-r[low].key; //任取一个元素 (第一个) 为中心pivotL-r[0] L-r[low]; // 将中心pivot放到0处while (low high){while (low high L-r[high].key pivotkey) // high 中心 移动high向前{–high;}L-r[low] L-r[high]; //high 中心, 把该值移动到low那一侧while (low high L-r[low].key pivotkey)// low 中心 移动low向后{low;}L-r[high] L-r[low];//low 中心, 把该值移动到high那一侧}L-r[low] L-r[0]; // 中心放到对应位置return low; }void QSort(SqList L, int low, int high) {if (low high)//长度大于1{int pivotloc Partition(L, low, high); //将L.r[low .. high]一分为二printf(low %d, high %d, pivotloc %d\n, low, high, pivotloc);for (int i 1; i 13; i){printf(%d , L-r[i].key);}printf(\n—————–\n);QSort(L, low, pivotloc - 1); //对低子表递归排序QSort(L, pivotloc 1, high); //对高子表递归排序} }int main() {int i;int r[13] { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length 13;for (i 1; i L.length; i) {L.r[i].key r[i - 1];}QSort(L,1, L.length);printf(排序结果\n);for (i 1; i 13; i){printf(%d , L.r[i].key);}return 0; }划分元素的选取是影响时间性能的关键 最好情况 时间复杂度 O(nlogn) 最坏情况 时间复杂度 O(n2) 平均情况 时间复杂度O(nlogn) ​ QSort()O(logn) ​ Partition()O(n) 空间复杂度 ​ 平均情况O(logn) ​ 最坏情况O(n) 稳定性不稳定 快速排序不适于对原本有序或基本有序包括正序和逆序的记录序列进行排序退化成冒泡排序 10.4 选择排序 10.4.1 简单选择排序(Simple Selection Sort) 基本思想 在待排序的数据中选出最大(小)的元素放在其最终的位置。 基本操作: 首先通过n-1次关键字比较从n个记录中找出关键字最小的记录将它与第一个记录交换再通过n-2次比较从剩余的n-1个记录中找出关键字次小的记录将它与第二个记录交换重复上述操作共进行n-1趟排序后排序结束 #includestdio.h #includestdlib.h#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为int型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList;void SelectSort(SqList L) {int i, j, k;for (i 1; i L-length; i){k i; for (j i 1; j L-length; j){if (L-r[j].key L-r[k].key){k j;}}if (k ! i){L-r[0] L-r[k];L-r[k] L-r[i];L-r[i] L-r[0];}printf(\n第 %d 次排序结果\n, i);for (j 1; j L-length; j){printf(%d , L-r[j].key);}} }int main() {int i;int r[13] { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length 13;for (i 1; i L.length; i) {L.r[i].key r[i - 1];}SelectSort(L);printf(\n—————–\n);printf(排序结果\n);for (i 1; i 13; i){printf(%d , L.r[i].key);}return 0; }时间复杂度 - O(n2) 移动次数 最好情况0最坏情况3(n-1) 比较次数 最好情况O(n2)最坏情况O(n2)平均情况O(n2) ∑ i 1 n − 1 ( n − i ) n ( n − 1 ) 2 \sum_{i1}^{n-1}(n - i) \frac{n(n-1)}{2} i1∑n−1​(n−i)2n(n−1)​
空间复杂度O(1) 稳定性不稳定 10.4.2 树形选择排序(Tree Selection Sort) 又称锦标赛排序(Tournament Sort) 基本思想 首先对n个记录的关键字进行两两比较然后在 其中⌈ n / 2⌉个较小者之间再进行两两比较如此重复直至选出最小关键字的记录为止。 10.4.3 堆排序(Heap Sort) 若n个元素的序列{a1a2,…, an}满足 ai ≤ a2i ai ≤ a2i1 则称该序列为小根堆 若n个元素的序列{a1a2,…, an}满足 ai ≥ a2i ai ≥ a2i1 则称该序列为大根堆 从堆的定义可以看出堆实质是满足如下性质的完全二叉树:二又树中任一非叶子结点均小于(大于)它的孩子结点 堆排序: 若在输出堆顶的最小值(最大值)后使得剩余n-1个元素的序列重又建成一个堆则得到n个元素的次小值(次大值)…如此反复便能得到一个有序序列。【堆顶就是最小值(最大值)每次都取堆顶就可得到一个有序序列】 堆序列需解决两个问题 如何由无序序列建成一个堆? 单结点的二又树是堆 在完全二叉树中所有以叶子结点(序号in/2【最后一个结点是n那么他的双亲是n/2所以叶子结点是 n/2】)为根的子树是堆。 只需依次将以序号为n/2n/2 - 1… 1的结点为根的子树均调整为堆即可。 如何在输出堆顶元素后调整剩余元素为一个新的堆? ​ 小根堆: 输出堆顶元素之后以堆中最后一个元素【编号最大的元素】替代之; 然后将根结点值与左、右子树的根结点值进行比较并与其中小者进行交换 重复上述操作直至叶子结点将得到新的堆称这个从堆顶至叶子的调整过程为“筛选
#includestdio.h #includestdlib.h#define MAXSIZE 20 // 设记录不超过20个 typedef int KeyType; // 设关键字为 int 型typedef struct { //定义每个记录(数据元素)的结构KeyType key; //关键字 }RedType;typedef struct { // 定义顺序表结构RedType r[MAXSIZE 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度 }SqList; typedef SqList HeapType; // 堆采用顺序表存储表示/大根堆/ void HeapAdjust_big(HeapType* H, int s, int m) {//调整R[s]关键字使R[s…m]成为一个大根堆RedType rc H-r[s];int j;for (j 2 * s; j m; j * 2){// H-r[j]和 H-r[j 1]分别代表H-r[s]的左子结点和右子结点比较出两者之间最大值if (j m H-r[j].key H-r[j 1].key){j;}//再和比较H-r[s]比较最大值if (rc.key H-r[j].key){//H-r[s]最大即无需改动位置break;}H-r[s] H-r[j];s j;}H-r[s] rc;//插入 }/小根堆/ void HeapAdjust_small(HeapType* H, int s, int m) {//调整R[s]关键字使R[s…m]成为一个小根堆RedType rc H-r[s];int j;for (j 2 * s; j m; j * 2){if (j m H-r[j].key H-r[j 1].key){j;}if (rc.key H-r[j].key){break;}H-r[s] H-r[j];s j;}H-r[s] rc; }void HeapSort(HeapType* H) {//对顺序表H进行堆排序int i;for (i H-length / 2; i 0; i–) //建初始堆 从 i H-length / 2 往前到1{HeapAdjust_small(H, i, H-length);}for (i H-length; i 1; i–) //进行n-1趟排序{printf(%d , H-r[1].key);//根与最后一个元素交换H-r[0] H-r[i];H-r[i] H-r[1];H-r[1] H-r[0];//对R[1]到R[i-1]重新建堆HeapAdjust_small(H, 1, i-1);} }int main() {int i;int r[13] { 81,94,11,96,12,35,17,95,28,58,41,75,15 };HeapType H;H.length 13;for (i 1; i H.length; i) {H.r[i].key r[i - 1];}printf(排序结果\n);HeapSort(H);return 0; }时间复杂度 初始堆化所需时间不超过O(n)排序阶段(不含初始堆化) 一次重新堆化所需时间不超过O(logn)n-1次循环所需时间不超过O(nlogn) Tw(n)0(n) O(nlogn) O(nlogn) —— 最好情况、最坏情况、平均情况 空间复杂度O(1) 稳定性不稳定 不适用于待排序记录个数n较少的情况但对于n较大的文件还是很有效的。 10.5 归并排序(Merging Sort) 基本思想将两个或两个以上的有序子序列“归并”为一个有序序列该算法采用经典的分治divide-and-conquer策略分治法将问题 分(divide) 成一些小的问题然后递归求解而 治(conquer) 的阶段则将分的阶段得到的各答案修补在一起即分而治之)。 通常采用2-路归并排序将两个位置相邻的有序子序列R[l…]m]和R[m1…]n] 归并为一个有序序列R[l…n] 整个归并排序仅需 ⌈log2n⌉ 趟 #includestdio.h #includestdlib.hvoid Merge(int* arr, int left, int mid, int right) {int* temp (int*)malloc((right - left 1) * sizeof(int));/* i [left, mid]j [mid 1, right]/int i left, j mid 1, k 0;while (i mid j right) {if (arr[i] arr[j]) {temp[k] arr[i];}else {temp[k] arr[j];}}while (i mid) {temp[k] arr[i];}while (j right) {temp[k] arr[j];}for (i left, k 0; i right; i, k) {arr[i] temp[k];}free(temp); }void MergeSort(int arr, int left, int right) {if (left right) {return;}int mid (left right) / 2;MergeSort(arr, left, mid);MergeSort(arr, mid 1, right);Merge(arr, left, mid, right); }void printArray(int* arr, int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n); }int main() {int arr[] { 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 };int n sizeof(arr) / sizeof(arr[0]);MergeSort(arr, 0, n - 1);printArray(arr, n);return 0; } 时间复杂度O(nlogn) —— 最好情况、最坏情况、平均情况 空间复杂度O(n) 稳定性稳定 10.6 基数排序(Radix Sorting) 10.6.1 多关键字的排序 基本步骤 确定每个关键字的优先级对每个关键字进行排序根据优先级合并排序结果 关键字的次序K0, K1, … , Kd-1 最主位关键字K0 最次位关键字Kd-1 最高位优先 (Most Significant Digit first)法简称 MSD 法 先对最主位关键字 K0 进行排序将序列分成若干子序列每个子序 列中的记录都具有相同的K0值 然后分别就每个子序列对关键字 K1 进行排序按K1值 不同再分成若干更小的子序列 依次重复 直至对 Kd-2 进行排序之后得到的每一子序列 中的记录都具有相同的关键字(K0, K1, … , Kd-2), 而后分别每个子序列对 Kd-1 进行排 序最后将所有子序列依次联接在一起成为一个有序序列
​
最低位优先 (Least Significant Digit first) 法简称 LSD 法 从最次位关键字 Kd-1 起进行排序。然后再对高一位的关键字 Kd-2 进行排序依次重复直至对 K0 进行排序后便成 为一个有序序列 ​
/————–使用LSD基数排序算法—————/ /* K 由 3个关键字(K0,0K1 ,K2)组成其中 K0 是百位数K1 是十位数K2 是个位数/#includestdio.h #includestdlib.h// 定义最大数字的位数 #define MAX_DIGITS 3 // 3位数字百位、十位、个位// 定义桶的大小 #define BUCKET_SIZE 10 // 10个桶分别对应0-9/** 函数分配数据到桶中* param data 要排序的数据数组* param bucket 桶数组用于统计每个数字出现的次数* param n 数据数组的长度* param digit 当前正在处理的位数1、10、100/ void distribute(int data, int* bucket, int n, int digit) {int i;// 遍历数据数组统计每个数字在当前位数上的值for (i 0; i n; i) {// 计算当前数字在当前位数上的值int index (data[i] / digit) % 10;// 将该值对应的桶计数加1bucket[index];} }/*** 函数收集数据从桶中* param data 要排序的数据数组* param bucket 桶数组用于统计每个数字出现的次数* param temp 临时数组用于存储收集的数据* param n 数据数组的长度* param digit 当前正在处理的位数1、10、100/ void collect(int data, int* bucket, int* temp, int n, int digit) {int i, j 0;// 遍历桶数组收集数据for (i 0; i BUCKET_SIZE; i) {// 循环直到该桶的计数为0while (bucket[i] 0) {// 遍历数据数组找到对应的数字for (int k 0; k n; k) {// 如果当前数字在当前位数上的值与桶的索引相等if ((data[k] / digit) % 10 i) {// 将该数字收集到临时数组中temp[j] data[k];j;// 将桶的计数减1bucket[i]–;}}}}// 将收集的数据复制回原始数据数组for (i 0; i n; i) {data[i] temp[i];} }// 函数基数排序 void radixSort(int* data, int n) {int digit 1;int* temp (int*)malloc(n * sizeof(int));int bucket[BUCKET_SIZE] { 0 };// 进行MAX_DIGITS次分配和收集for (int i 0; i MAX_DIGITS; i) {// 分配数据到桶中distribute(data, bucket, n, digit);// 收集数据从桶中collect(data, bucket, temp, n, digit);// 将位数乘以10下一位digit * 10;// 重置桶数组for (int j 0; j BUCKET_SIZE; j) {bucket[j] 0;}// 打印当前的数据状态printf(第 %d 趟分配 收集后的数据\n, i);for (int i 0; i n; i) {printf(%d , data[i]);}printf(\n);} }// 主函数 int main() {int data[] { 278, 109, 63, 930, 589, 184, 505, 269, 8, 83};int n sizeof(data) / sizeof(data[0]);radixSort(data, n); return 0; }10.6.2 链式基数排序 基数排序是借助 “分配“和“收集“ 两种操作对单逻辑关键字进行排序并用链表作存储结构 的一种内部排序 方法。 基本步骤 将数据分成多个桶每个桶对应一个基数位对每个桶进行排序使用链表存储排序结果迭代基数位重复步骤1和2直到所有基数位完成 #include stdio.h #include stdlib.h// 定义节点结构包含数据和指向下一个节点的指针 typedef struct Node {int data;struct Node* next; } Node;// 定义链表结构包含头节点和尾节点 typedef struct List {Node* head;Node* tail; } List;// 初始化链表函数设置头节点和尾节点为NULL void initList(List* list) {list-head NULL;list-tail NULL; }// 插入节点到链表末尾 void insertNode(List* list, int data) {// 分配新节点的内存Node* newNode (Node)malloc(sizeof(Node));// 设置新节点的数据newNode-data data;// 置新节点的下一个节点为NULLnewNode-next NULL;// 如果链表为空设置新节点为头节点和尾节点if (list-head NULL) {// 设置头节点为新节点list-head newNode;// 设置尾节点为新节点list-tail newNode;}// 如果链表不为空插入新节点到尾节点后面else {// 设置尾节点的下一个节点为新节点list-tail-next newNode;// 更新尾节点为新节点list-tail newNode;} }// 打印链表 void printList(List list) {// 从头节点开始遍历链表Node* current list-head;// 遍历链表直到到达NULLwhile (current ! NULL) {// 打印当前节点的数据printf(%d , current-data);// 移动到下一个节点current current-next;}printf(\n); }// 分配节点到桶中的函数 void allocateNodes(List* list, List* bucket, int digit) {// 分配节点到桶中Node* current list-head; // 从头节点开始遍历链表while (current ! NULL) {// 计算当前节点的数据在当前位数上的值int index (current-data / digit) % 10;// 将当前节点插入到对应的桶中insertNode(bucket[index], current-data);// 移动到下一个节点current current-next;} }// 收集节点从桶中的函数 void collectNodes(List* list, List* bucket) {// 收集节点从桶中list-head NULL;// 重置头节点为NULLlist-tail NULL;// 重置尾节点为NULLfor (int j 0; j 10; j) {// 从每个桶中收集节点Node* current bucket[j].head;// 从桶的头节点开始遍历while (current ! NULL) {// 将当前节点插入到链表中insertNode(list, current-data);// 移动到下一个节点current current-next;}// 初始化每个桶initList(bucket[j]);} }// 基数排序函数 void radixSort(List* list) {int digit 1; // 初始化位数为个位1List bucket[10]; // 定义10个桶用于存储不同位数的数据for (int i 0; i 10; i) {// 初始化每个桶initList(bucket[i]);}// 进行3次分配和收集针对3位数字for (int i 0; i 3; i) {// 分配节点到桶中allocateNodes(list, bucket, digit);// 收集节点从桶中collectNodes(list, bucket);// 将位数乘以10下一位digit * 10;// 打印当前的数据状态printf(第 %d 趟分配 收集后的数据\n, i 1);printList(list);} }int main() {List list;initList(list);int r[] { 614,738,921,485,637,101,215,530,790,306 };int i;int n sizeof® / sizeof(r[0]);for (i 0; i n; i){insertNode(list, r[i]);}// 插入示例数据printf(原始数据\n);printList(list);radixSort(list);return 0; }适用范围多关键字排序可以处理多种数据类型而链式基数排序仅适用于整数或字符串数据。 时间复杂度: O(k*(nm)) ​ k:关键字个数 ​ m:关键字取值范围为m个值 空间复杂度: O(nm) 稳定性: 稳定 10.7 各种内部排序方法的比较讨论 一、时间性能 按平均的时间性能来分有三类排序方法:· 时间复杂度为O(nlogn)的方法有: 快速排序、堆排序和归并排序其中以快速排序为最好 时间复杂度为O(n2)的有: 直接插入排序、冒泡排序和简单选择排序其中以直接插入为最好 时间复杂度为O(n)的排序方法只有: 基数排序。 当待排记录序列按关键字顺序有序时直接插入排序和冒泡排序达到O(n)的时间复杂度; 而对于快速排序而言这是最不好的情况此时的时间性能退化为O(n2)因此是应该尽量避免的情况。
二、空间性能指的是排序过程中所需的辅助空间大小 所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为O(1) 快速排序为O(logn)为栈所需的辅助空间 归并排序所需辅助空间最多其空间复杂度为O(n) 链式基数排序需附设队列首尾指针则空间复杂度为O(rd) 参考 教材严蔚敏《数据结构》C语言版.pdf 视频 数据结构与算法基础青岛大学-王卓 表插入排序算法实现 博客 2-路插入排序详解