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

2024-09-09 07:20
文章标签 选择 数据结构 排序 交换 第二 第八章 语言版 8.4 8.3

本文主要是介绍《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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);}
}

在这里插入图片描述

这篇关于《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1150519。

相关文章

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言，在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况，这使得“存储焦虑”不再是个别现象，而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得，我们似乎正处在互联网信息飞速增长的阶段，对于存储的需求也将会不断扩大。对于苹果用户而言，这一问题愈发严峻，毕竟512GB和1TB版本的iPhone可不是人人都消费得起的，因此成熟的外置存储方案开
阅读更多...
如何选择适合孤独症兄妹的学校？

如何选择适合孤独症兄妹的学校？

在探索适合孤独症儿童教育的道路上，每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时，选择一所能够同时满足两个孩子特殊需求的学校，更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择，并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症，这一复杂的神经发育障碍，影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个?

cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈？ cross-plateform 跨平台应用程序-03-如果只选择一个框架，应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte
阅读更多...
如何选择SDR无线图传方案

如何选择SDR无线图传方案

在开源软件定义无线电（SDR）领域，有几个项目提供了无线图传的解决方案。以下是一些开源SDR无线图传方案： 1. **OpenHD**：这是一个远程高清数字图像传输的开源解决方案，它使用SDR技术来实现高清视频的无线传输。OpenHD项目提供了一个完整的工具链，包括发射器和接收器的硬件设计以及相应的软件。 2. **USRP（Universal Software Radio Periphera
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2