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

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

相关文章

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient

SpringValidation数据校验之约束注解与分组校验方式

《SpringValidation数据校验之约束注解与分组校验方式》本文将深入探讨SpringValidation的核心功能,帮助开发者掌握约束注解的使用技巧和分组校验的高级应用,从而构建更加健壮和可... 目录引言一、Spring Validation基础架构1.1 jsR-380标准与Spring整合1

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

SpringBatch数据写入实现

《SpringBatch数据写入实现》SpringBatch通过ItemWriter接口及其丰富的实现,提供了强大的数据写入能力,本文主要介绍了SpringBatch数据写入实现,具有一定的参考价值,... 目录python引言一、ItemWriter核心概念二、数据库写入实现三、文件写入实现四、多目标写入

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle