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

相关文章

Mybatis 传参与排序模糊查询功能实现

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》：本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
C语言实现两个变量值交换的三种方式

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量（推荐）2.相加和相减的方式（值较大时可能丢失数据）3.按位异或运算1.使用临时
阅读更多...
使用C语言实现交换整数的奇数位和偶数位

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现：将一个整
阅读更多...
C++快速排序超详细讲解

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...
基于Python实现多语言朗读与单词选择测验

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、
阅读更多...
前端知识点之Javascript选择输入框confirm用法

前端知识点之Javascript选择输入框confirm用法

《前端知识点之Javascript选择输入框confirm用法》：本文主要介绍JavaScript中的confirm方法的基本用法、功能特点、注意事项及常见用途,文中通过代码介绍的非常详细,对大家... 目录1. 基本用法2. 功能特点①阻塞行为：confirm 对话框会阻塞脚本的执行，直到用户作出选择。②
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
Spring排序机制之接口与注解的使用方法

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri
阅读更多...
大数据小内存排序问题如何巧妙解决

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法：数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高；分治法高效但实现复杂；位图法可读性差,但存储空间受限... 目录三种方法：方法概要数据库排序（http://www.chinasem.cn对数据库设备要求较高）分治法（常
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2