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

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

news 来源：原创 2024/9/20 23:20:53

8.3 交换排序

8.3.1 冒泡排序

【算法特点】
(1) 稳定排序。
(2) 可用于链式存储结构。
(3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;
typedef char InfoType;typedef struct
{KeyType key;InfoType otherinfo;
}RedType;typedef struct
{RedType r[MAXSIZE + 1];  //r[O]闲置或用做哨兵单元int length;
}SqList;void CreateSqList(SqList& L);
void BubbleSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);BubbleSort(L);printSqList(L);return 0;
}void CreateSqList(SqList& L)
{int i = 0;printf("请输入顺序表的元素个数：");scanf_s(" %d", &L.length);for (i = 1; i <= L.length; i++){printf("请输入第%d个关键字：", i);scanf_s(" %d", &L.r[i].key);}
}//算法8.4 冒泡排序
void BubbleSort(SqList& L)
{int m = L.length - 1;int flag = 1;  //flag用来标记某一趟排序是否发生交换int j = 0;RedType temp = { 0,'\0' };while (m > 0 && flag == 1){flag = 0;  //flag置为0, 如果本趟排序没有发生交换，则不会执行下一趟排序//第 L.length - m 趟冒泡排序for (j = 1; j <= m; j++)  //j最大值只能取到m.每趟冒泡排序针对的是从L.r[1]到L.r[m+1]，将其中最大的，放到最后一个位置，即L.r[m+1]处{if (L.r[j].key > L.r[j + 1].key) //当L.r[j].key == L.r[j+1].key时，不会发生交换，保证了本冒泡排序的稳定性。{flag = 1;  //flag置为1, 表示本趟排序发生了交换//交换前后两个记录temp = L.r[j];L.r[j] = L.r[j + 1];L.r[j + 1] = temp;}}//序列中从L.r[m + 1]到L.r[L.length]处的元素都有序了--m; //【m自减之后】下一次冒泡排序针对的仍然是从L.r[1]到L.r[m+1]的关键字}
}void printSqList(SqList L)
{int i = 0;printf("\n\n排序后的序列为：");for (i = 1; i <= L.length; i++){printf("\nr[%d].key = %d", i, L.r[i].key);}
}

在这里插入图片描述
在这里插入图片描述

8.3.2 快速排序

【算法特点】
(1)记录非顺次的移动导致排序方法是不稳定的。
(2)排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构。
(3)当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、 n较大时的情况。

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;
typedef char InfoType;typedef struct
{KeyType key;InfoType otherinfo;
}RedType;typedef struct
{RedType r[MAXSIZE + 1];  //r[O]闲置或用做哨兵单元int length;
}SqList;void CreateSqList(SqList& L);
int Partition(SqList& L, int low, int high);
void QSort(SqList& L, int low, int high);
void QuickSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);QuickSort(L);printSqList(L);return 0;
}void CreateSqList(SqList& L)
{int i = 0;printf("请输入顺序表的元素个数：");scanf_s(" %d", &L.length);for (i = 1; i <= L.length; i++){printf("请输入第%d个关键字：", i);scanf_s(" %d", &L.r[i].key);}
}//算法8.5 快速排序
//对顺序表L中的子表r[low...high]进行一趟排序，返回枢轴位置
int Partition(SqList& L, int low, int high)
{L.r[0] = L.r[low];KeyType pivotkey = L.r[low].key;while (low < high) {while (low < high && L.r[high].key >= pivotkey){--high;}L.r[low] = L.r[high];while (low < high && L.r[low].key <= pivotkey){++low;}L.r[high] = L.r[low];}L.r[low] = L.r[0];  //枢轴记录到位return low;  //返回枢轴位置
}//对顺序表L中的子序列L.r[low ..high]做快速排序
void QSort(SqList& L, int low, int high)
{if (low < high){//对顺序表L.r[low...high]先进行一趟快速排序，使之一分为二，pivotloc是枢轴位置int pivotloc = Partition(L, low, high);//对左、右子表进行递归排序QSort(L, low, pivotloc - 1);QSort(L, pivotloc + 1, high);/*   当子表不断往下分，直到分到某一子表中仅有三个或两个元素时，因为均无法通过该子表的左右子表QSort函数中的if语句，此时，对该含有三个或两个元素的子表的快速排序就结束了。之后，会返回到分出该含有三个或两个元素的子表的那一层快速排序递归，进行后面的步骤。	*/}
}//对顺序表L做快速排序
void QuickSort(SqList& L)
{QSort(L, 1, L.length);
}void printSqList(SqList L)
{int i = 0;printf("\n\n排序后的序列为：");for (i = 1; i <= L.length; i++){printf("\nr[%d].key = %d", i, L.r[i].key);}
}

在这里插入图片描述
在这里插入图片描述

8.4 选择排序

8.4.1 简单选择排序

【算法特点】
(1)就选择排序方法本身来讲，它是一种稳定的排序方法，但下图所表现出来的现象是不稳定的，这是因为第一种实现选择排序的算法采用 “交换记录” 的策略所造成的，改变这个策略，可以写出不产生 “不稳定现象” 的选择排序算法。

选择排序的稳定解法 ——— Jekk_cheng

(2)可用于链式存储结构。
(3)移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快。

8.4.1.1 不稳定解法

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;
typedef char InfoType;typedef struct
{KeyType key;InfoType otherinfo;
}RedType;typedef struct
{RedType r[MAXSIZE + 1];  //r[O]闲置或用做哨兵单元int length;
}SqList;void CreateSqList(SqList& L);
void SelectSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);SelectSort(L);printSqList(L);return 0;
}void CreateSqList(SqList& L)
{int i = 0;printf("请输入顺序表的元素个数：");scanf_s(" %d", &L.length);for (i = 1; i <= L.length; i++){printf("请输入第%d个关键字：", i);scanf_s(" %d", &L.r[i].key);}
}//算法8.6 简单选择排序
void SelectSort(SqList& L)
{int i = 0;int j = 0;int k = 0;RedType temp = { 0,'\0' };/* 整个序列刚开始第一趟（i = 1）是没有有序部分的，全部都属于无序部分。从第二趟开始（i>=2），在进行下一趟简单选择排序之前，从L.r[1]到L.r[i-1]是序列中的有序部分。最多进行n-1趟。  */for (i = 1; i < L.length; ++i){/********* 求序列无序部分（从L.r[i]到L.r[L.length]）的最小关键字下标，并记录在k中 *********/k = i;   //k的初始值为无序部分第一个元素的下标ifor (j = i + 1; j <= L.length; ++j){if (L.r[j].key < L.r[k].key){k = j;}}//k == i 说明无序部分最小关键字即为无序部分的第一个元素L.r[i]，不用进行交换if (k != i){temp = L.r[i];L.r[i] = L.r[k];L.r[k] = temp;}}
}void printSqList(SqList L)
{int i = 0;printf("\n\n排序后的序列为：");for (i = 1; i <= L.length; i++){printf("\nr[%d].key = %d", i, L.r[i].key);}
}

在这里插入图片描述
在这里插入图片描述

8.4.1.2 稳定解法

选择排序的稳定解法 ——— Jekk_cheng

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;
typedef char InfoType;typedef struct
{KeyType key;InfoType otherinfo;
}RedType;typedef struct
{RedType r[MAXSIZE + 1];  //r[O]闲置或用做哨兵单元int length;
}SqList;void CreateSqList(SqList& L);
void SelectSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);SelectSort(L);printSqList(L);return 0;
}void CreateSqList(SqList& L)
{int i = 0;printf("请输入顺序表的元素个数：");scanf_s(" %d", &L.length);for (i = 1; i <= L.length; i++){printf("请输入第%d个关键字：", i);scanf_s(" %d", &L.r[i].key);}
}//算法8.6 简单选择排序（采取稳定策略）
void SelectSort(SqList& L)
{int i = 0;int j = 0;int k = 0;RedType temp = { 0,'\0' };/* 整个序列刚开始第一趟（i = 1）是没有有序部分的，全部都属于无序部分。从第二趟开始（i>=2），在进行下一趟简单选择排序之前，从L.r[1]到L.r[i-1]是序列中的有序部分。最多进行n-1趟。  */for (i = 1; i < L.length; ++i){/********* 求序列无序部分（从L.r[i]到L.r[L.length]）的最小关键字下标，并记录在k中 *********/k = i;   //k的初始值为无序部分第一个元素的下标ifor (j = i + 1; j <= L.length; ++j){if (L.r[j].key < L.r[k].key){k = j;}}/* 无序部分（从L.r[i]到L.r[L.length]）的最小关键字为L.r[k]k == i 说明无序部分最小关键字即为无序部分的第一个元素L.r[i]，不会进行移动否则，就把L.r[k]前面的无序元素（从L.r[i]到L.r[k-1]），依次向后移动一个，再将最小关键字插入到有序部分的后面（也是此时无序部分的第一个）L.r[i]处 */temp = L.r[k];//printf("\n\n最小值为：temp = L.r[%d] = %d", k, L.r[k]);while(k != i){//printf("\n L.r[k - 1] = L.r[%d] = %d", k - 1, L.r[k - 1]);L.r[k] = L.r[k - 1];k--;}L.r[i] = temp;}
}void printSqList(SqList L)
{int i = 0;printf("\n\n排序后的序列为：");for (i = 1; i <= L.length; i++){printf("\nr[%d].key = %d", i, L.r[i].key);}
}

在这里插入图片描述

8.4.2 树形选择排序 / 锦标赛排序

在这里插入图片描述

8.4.3 堆排序

【算法特点】
(1)是不稳定排序。
(2) 只能用于顺序结构，不能用于链式结构 。
(3)初始建堆所需的比较次数较多，因此记录数较少时不宜采用。
【在处理大量数据时，堆排序是一个很好的选择，因为它具有较好的平均性能；
但是在处理少量数据时，由于初始建堆的成本相对较高，这个过程需要进行大量的比较操作，对于较大的数组来说，这个开销是可以接受的，因为之后的排序过程中每次只需要O(nlog2n)的时间来维护堆。但是对于较小的数组，这个预先构建堆的操作就显得相对成本较高，不如直接使用一些简单排序算法来得高效。】

堆排序在最坏情况下时间复杂度为O(nlog2n), 相对于快速排序最坏情况下的O(n^2)而言是一个优点，当记录较多时较为高效。

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;
typedef char InfoType;typedef struct
{KeyType key;InfoType otherinfo;
}RedType;typedef struct
{RedType r[MAXSIZE + 1];  //r[O]闲置或用做哨兵单元int length;
}SqList;void CreateSqList(SqList& L);
void HeadAdjust(SqList& L, int s, int m);
void CreateHeap(SqList& L);
void HeapSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);HeapSort(L);printSqList(L);return 0;
}void CreateSqList(SqList& L)
{int i = 0;printf("请输入顺序表的元素个数：");scanf_s(" %d", &L.length);for (i = 1; i <= L.length; i++){printf("请输入第%d个关键字：", i);scanf_s(" %d", &L.r[i].key);}
}//算法8.7 筛选法调整堆
//假设r[s + l...m]已经是堆，将r[s...m]调整为以r[s]为根的大根堆
void HeadAdjust(SqList& L, int s, int m)
{RedType rc = L.r[s];int j = 0;for (j = 2 * s; j <= m; j *= 2)  //j = j*2{if (j < m && L.r[j].key < L.r[j + 1].key){++j;}if (rc.key >= L.r[j].key){break;}L.r[s] = L.r[j];s = j;}L.r[s] = rc;
}//算法8.8 建初堆
//把无序序列L.r[l...n]建成大根堆
void CreateHeap(SqList& L)
{int n = L.length;int i = 0;for (i = n / 2; i > 0; --i){HeadAdjust(L, i, n);}
}//算法8.9 堆排序
//对顺序表L进行堆排序
void HeapSort(SqList& L)
{RedType x = { 0,'\0' };int i = 0;CreateHeap(L);  //初建堆for (i = L.length; i > 1; --i){x = L.r[1];L.r[1] = L.r[i];L.r[i] = x;HeadAdjust(L, 1, i - 1);}
}void printSqList(SqList L)
{int i = 0;printf("\n\n排序后的序列为：");for (i = 1; i <= L.length; i++){printf("\nr[%d].key = %d", i, L.r[i].key);}
}

在这里插入图片描述

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • [数据集][图像分类]熊分类数据集309张5类别黑熊泰迪北极熊等
  • 动手学深度学习（pytorch）学习记录25-汇聚层(池化层)[学习记录]
  • AIGC与数据分析融合，引领商业智能新变革（TOP企业实践）
  • iOS——GCD再学习
  • rexroth拧紧系统
  • 使用EDM邮件群发营销管理平台发送推广邮件在什么时间段发信效果最好
  • 【C++ Primer Plus习题】14.1
  • pytest压力测试:不断发送数据，直到发现数据丢失
  • 【AcWing】861. 二分图的最大匹配(匈牙利算法)
  • python-网页自动化（二）
  • 强烈推荐！分享5款ai论文生成软件
  • 修改密码模块中对轮询接口响应用户失效问题的处理
  • Android13 Hotseat客制化--Hotseat修改布局、支持滑动、去掉开机弹动效果、禁止创建文件夹
  • GitHub图床
  • pytorch pyro 贝叶斯神经网络 bnn beyesean neure network svi ​定制SVI目标和培训循环，变更推理
  • 分享一款快速APP功能测试工具
  • 【刷算法】从上往下打印二叉树
  • AzureCon上微软宣布了哪些容器相关的重磅消息
  • CentOS7 安装JDK
  • java取消线程实例
  • JS数组方法汇总
  • JS正则表达式精简教程（JavaScript RegExp 对象）
  • Lucene解析 - 基本概念
  • miaov-React 最佳入门
  • nginx 负载服务器优化
  • php面试题 汇集2
  • Promise面试题，控制异步流程
  • Python连接Oracle
  • Vim Clutch | 面向脚踏板编程……
  • VirtualBox 安装过程中出现 Running VMs found 错误的解决过程
  • 多线程 start 和 run 方法到底有什么区别？
  • 快速构建spring-cloud+sleuth+rabbit+ zipkin+es+kibana+grafana日志跟踪平台
  • 如何实现 font-size 的响应式
  • 实现菜单下拉伸展折叠效果demo
  • 实战｜智能家居行业移动应用性能分析
  • 一个6年java程序员的工作感悟，写给还在迷茫的你
  • 译米田引理
  • ​埃文科技受邀出席2024 “数据要素×”生态大会​
  • ​学习笔记——动态路由——IS-IS中间系统到中间系统（报文/TLV）​
  • （3）nginx 配置(nginx.conf)
  • (c语言+数据结构链表)项目：贪吃蛇
  • (pojstep1.3.1)1017(构造法模拟)
  • (vue)页面文件上传获取:action地址
  • （笔记）M1使用hombrew安装qemu
  • （大众金融）SQL server面试题（1）-总销售量最少的3个型号的车及其总销售量
  • （二）windows配置JDK环境
  • (过滤器)Filter和(监听器)listener
  • （黑马出品_高级篇_01）SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式
  • （七）Appdesigner-初步入门及常用组件的使用方法说明
  • （十八）三元表达式和列表解析
  • （一）硬件制作--从零开始自制linux掌上电脑（F1C200S) ＜嵌入式项目＞
  • (转)shell中括号的特殊用法 linux if多条件判断
  • （转）程序员技术练级攻略
  • .dat文件写入byte类型数组_用Python从Abaqus导出txt、dat数据
  • .NET分布式缓存Memcached从入门到实战