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

相关文章

闲置电脑也能活出第二春？鲁大师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
阅读更多...
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）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（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 In
阅读更多...
CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...
【软考】希尔排序算法分析

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组，例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量，换值int temp;in
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2