《数据结构（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。

相关文章

Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

《Python中requests与aiohttp在实际项目中的选择策略详解》本文主要介绍了Python爬虫开发中常用的两个库requests和aiohttp的使用方法及其区别,通过实际项目案... 目录一、requests 库二、aiohttp 库三、requests 和 aiohttp 的比较四、requ
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
el-select下拉选择缓存的实现

el-select下拉选择缓存的实现

《el-select下拉选择缓存的实现》本文主要介绍了在使用el-select实现下拉选择缓存时遇到的问题及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录项目场景：问题描述解决方案：项目场景：从左侧列表中选取字段填入右侧下拉多选框，用户可以对右侧
阅读更多...
关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
闲置电脑也能活出第二春？鲁大师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）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2