【海贼王的数据航海】排序——概念|直接插入排序|希尔排序

2024-03-13 21:20

本文主要是介绍【海贼王的数据航海】排序——概念|直接插入排序|希尔排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1 -> 排序的概念及其运用

1.1 -> 排序的概念

1.2 -> 常见的排序算法

2 -> 插入排序

2.1 -> 基本思想

2.2 -> 直接插入排序

2.2.1 -> 代码实现

2.3 -> 希尔排序(缩小增量排序)

2.3.1 -> 代码实现


1 -> 排序的概念及其运用

1.1 -> 排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序不变,即在原序列中,r[ i ] = r[ j ],且r[ i ] 在 r[ j ]之前,而在排序后的序列中,r[ i ] 仍在 r[ j ]之前,则称这种排序算法是稳定的;否则称为不稳定。

内部排序:数据元素全部放在内存中的排序。

外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 -> 常见的排序算法

2 -> 插入排序

2.1 -> 基本思想

直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。

实际中我们玩扑克牌时,就用到了插入排序的思想。

2.2 -> 直接插入排序

当插入第i(i >= 1)个元素时,前面的arr[0],arr[1],arr[2]……,arr[i - 1]已经排好序,此时用arr[i]的排序码与arr[i - 1],arr[i - 2]……的排序码顺序进行比较,找到插入位置即将arr[i]插入,原来位置上的元素顺序后移。

直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高;
  2. 时间复杂度:O(N^{2})
  3. 空间复杂度:O(1),他是一种稳定的排序算法;
  4. 稳定性:稳定;

2.2.1 -> 代码实现

#define  _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 打印
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++)printf("%d ", a[i]);printf("\n");
}// 插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[i + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];--end;}else{break;}a[end + 1] = tmp;}}
}void TestInsertSort()
{int a[] = { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();return 0;
}

2.3 -> 希尔排序(缩小增量排序)

希尔排序法又称缩小增量法。希尔排序的基本思想就是:先选定一个整数,把待排序文件中所有记录分成各子序列,并对每一组内的记录进行排序,重复上述分组和排序的工作。当gap = 1时,完成排序。

希尔排序的特性总结:

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序了,这样就会很快。整体而言,可以达到优化的效果。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算。
  4. 稳定性:不稳定。

2.3.1 -> 代码实现

#define  _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[i + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];--end;}else{break;}a[end + 1] = tmp;}}
}// 希尔排序
void ShellSort(int* a, int n)
{int gap = n;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}void TestShellSort()
{int a[] = { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestShellSort();return 0;
}


感谢大佬们的支持!!!

互三啦!!!

这篇关于【海贼王的数据航海】排序——概念|直接插入排序|希尔排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/806241

相关文章

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

MySQL大表数据的分区与分库分表的实现

《MySQL大表数据的分区与分库分表的实现》数据库的分区和分库分表是两种常用的技术方案,本文主要介绍了MySQL大表数据的分区与分库分表的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录1. mysql大表数据的分区1.1 什么是分区?1.2 分区的类型1.3 分区的优点1.4 分

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

SpringBoot整合jasypt实现重要数据加密

《SpringBoot整合jasypt实现重要数据加密》Jasypt是一个专注于简化Java加密操作的开源工具,:本文主要介绍详细介绍了如何使用jasypt实现重要数据加密,感兴趣的小伙伴可... 目录jasypt简介 jasypt的优点SpringBoot使用jasypt创建mapper接口配置文件加密

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

MySQL使用binlog2sql工具实现在线恢复数据功能

《MySQL使用binlog2sql工具实现在线恢复数据功能》binlog2sql是大众点评开源的一款用于解析MySQLbinlog的工具,根据不同选项,可以得到原始SQL、回滚SQL等,下面我们就来... 目录背景目标步骤准备工作恢复数据结果验证结论背景生产数据库执行 SQL 脚本,一般会经过正规的审批