《数据结构（C语言版）第二版》第八章-排序（8.2-插入排序）

2024-09-07 07:20
文章标签 数据结构 排序 第二 插入排序 第八章 语言版 8.2

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

【8.2插入类、8.3交换类、8.4选择类、8.5归并类、8.6分配类 都属于内部排序。 】

8.2 插入排序

8.2.1 直接插人排序

【算法特点】
(1)稳定排序。
(2)算法简便，且容易实现。
(3)也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。
(4)更适合于初始记录基本有序（正序）的情况。
当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用。

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 20typedef 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 InsertSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);InsertSort(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.1 直接插入排序
void InsertSort(SqList& L)
{int i = 0;int j = 0;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];  //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];}}
}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.2.2 折半插人排序

【算法特点】
(1)稳定排序。
(2)因为要进行折半查找 ， 所以只能用于顺序结构，不能用于链式结构。
(3)适合初始记录无序、n较大时的情况。

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 20typedef 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 BInsertSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);BInsertSort(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.2 折半插入排序
void BInsertSort(SqList& L)
{int i = 0;int j = 0;int low = 1;int high = 1;int mid = 0;for (i = 2; i <= L.length; ++i){L.r[0] = L.r[i]; //无序序列的第一个下标/位置数i，暂存到监视哨中low = 1;        //（非递减）有序序列的最小下标/位置数lowhigh = i - 1;  //（非递减）有序序列的最大下标/位置数high//折半查找的非递归算法while (low <= high){mid = (low + high) / 2;if (L.r[0].key < L.r[mid].key){high = mid - 1;}else //if(L.r[0].key >= L.r[mid].key). 当L.r[0].key == L.r[mid].key时，也是low=mid+1,保证了本折半插入排序的稳定性{low = mid + 1; }}/*在折半查找中，当low > high时，跳出while循环。跳出后，L.r[0]即原L.r[i]的插入点在L.r[high+1]处，也就是最后的L.r[mid]处（此时mid = low = high+1. 本来三者相等，high由于L.r[0].key < L.r[mid].key，等于mid-1而小于了low）；或者是在L.r[low]处，也就是最后的L.r[mid+1]处（此时mid = high = low-1. 本来三者相等，low由于L.r[0].key >= L.r[mid].key，等于mid+1而大于了high）*///有序序列中，从L.r[high+1]（包括L.r[high+1]，j取的最小值为high+1）到L.r[i-1]（j取得最大值为i-1），每个记录都往后移for (j = i - 1; j >= high + 1; --j){L.r[j + 1] = L.r[j];}L.r[high + 1] = L.r[0];}
}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.2.3 希尔排序

【算法特点】
(1)记录跳跃式地移动导致排序方法是不稳定的。
(2)只能用于顺序结构，不能用于链式结构。
(3)增量序列可以有各种取法，但应该使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。
(4)记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以同折半插入排序一样，适合初始记录无序、n较大时的情况。

#include <stdio.h>
#include <stdlib.h>
#include <math.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 ShellInsert(SqList& L, int dk);
void ShellSort(SqList& L, int dt[]);
int checkPrimeNumber(int n);
void PrimeNumber(SqList L, int dt[], int& len);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };int dt[MAXSIZE] = {0};CreateSqList(L);ShellSort(L,dt);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.3 希尔（插入）排序
//对顺序表L做一趟增量是dk的希尔插入排序
void ShellInsert(SqList& L, int dk)
{int i = 0;int j = 0;//分组之后，第k组的元素下标/位置数为：k, dk+k, 2dk+k, 3dk+k, ...(k = 1,..,dk)for (i = dk + 1; i <= L.length; ++i){if (L.r[i].key < L.r[i - dk].key){L.r[0] = L.r[i];  //暂存在L.r[O]中，L.r[O]不是哨兵for (j = i - dk; j>0 && L.r[0].key < L.r[j].key; j-=dk)  //j = j-dk{L.r[j+dk] = L.r[j];   //比较的同时，记录后移}L.r[j + dk] = L.r[0];}}
}//按增量序列 dt[O...len-1]对顺序表 L作len 趟希尔排序
//对顺序表L完成一次完成的希尔插入排序
void ShellSort(SqList &L,int dt[])
{int i = 0;int len = 0; PrimeNumber(L, dt, len);for (i = 0; i < len; i++) {ShellInsert(L, dt[i]);}
}//应使增量序列dt中的值没有除 l 之外的公因子
//取[1,L.length]范围内所有的质数，从大到小存入dt数组中
void PrimeNumber(SqList L,int dt[],int &len)
{int i = 0;int status = checkPrimeNumber(0);int k = 0;for (i = L.length; i >= 1; i--)  {status = checkPrimeNumber(i);if (status){dt[k] = i;k++;}}dt[k] = 1;  //增量序列最后一个增量值必须等于1len = k+1;printf("\n\n该序列的增量序列为：");for (i = 0; i < len; i++){printf("%d ", dt[i]);}
}//判断一个数是否是质数
int checkPrimeNumber(int n)
{int i = 0;int sq = floor(sqrt(n));if (n <= 1){return 0;}if (n == 2 || n == 3){return 1;}//只有6x-1和6x+1的数才有可能是质数（但不一定就是，如n=35，还需要继续判断）if (n % 6 != 1 && n % 6 != 5)   //n=4和n=6时，n%6满足该if条件，返回false，正好符合情况{return false;}for (i = 5; i <= sq; i += 6){if (n % i == 0 || n % (i + 2) == 0){return 0;}}//n = 5 和 n=7 时，不会进入if判断语句，也不会进入for循环，而是直接返回true，此时也判断正确return true;
}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.2-插入排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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

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

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

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

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

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

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...
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对数据库设备要求较高）分治法（常
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

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

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

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

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

对于大多数人而言，在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况，这使得“存储焦虑”不再是个别现象，而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得，我们似乎正处在互联网信息飞速增长的阶段，对于存储的需求也将会不断扩大。对于苹果用户而言，这一问题愈发严峻，毕竟512GB和1TB版本的iPhone可不是人人都消费得起的，因此成熟的外置存储方案开
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2