算法快学笔记(十七):史上最全排序算法总结

2024-02-14 11:08

本文主要是介绍算法快学笔记(十七):史上最全排序算法总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 简介

本文对常见排序算法进行总结

2. 排序算法

2.1 冒泡排序

该算法比较简单,几乎所有语言涉及到算法时,都会涉及到冒泡算法。

算法思路:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
    持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

2.2 选择排序

每次选择一个最大(小)的,直到所有元素都被输出。

可参考:https://blog.csdn.net/sun7545526/article/details/85165618

2.3 直接插入排序

插入排序的基本方法是:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止

算法思路:

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

以[21,25,49,25,16,08]为例,排序过程如下所示:
在这里插入图片描述

在小规模数据集或是基本有序时,该算法效率较高。

2.4 希尔排序

先对数据进行预处理,使其基本有序,然后再用直接插入排序算法排序。

详细过程可参考:https://blog.csdn.net/eric_sunah/article/details/103080731

2.5 快速排序

利用“分而治之”的思想对集合进行排序
可参考:https://blog.csdn.net/sun7545526/article/details/85165742

2.6 堆排序

说堆排序前,先说下啥是堆。

堆:堆是满足下列性质的完全二叉树:

  • 每个节点都大于或是等于其左右孩子节点的值,称为大顶堆
  • 每个节点都小于或是等于其左右孩子节点的值,称为小顶堆

接下来说下堆是如何做排序的,思路如下(以大顶堆为例):

  1. 根节点是整个堆的最大值,将他移走。
  2. 将剩余n-1个节点重新构造成一个堆,再将根节点移走
  3. 重复执行1,2。直到没有节点可移动,就生成了有序序列。

该算法有两个需要解决问题:

  1. 如何将一个无序序列构建一个堆。
  2. 移除根节点后,如何用剩余的节点重建堆。

详细介绍参见:https://blog.csdn.net/eric_sunah/article/details/103081878

2.7 归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

详细介绍参见:https://blog.csdn.net/eric_sunah/article/details/103082607

3. 总结

分类总结:

在这里插入图片描述

时间复杂度总结:
在这里插入图片描述

这篇关于算法快学笔记(十七):史上最全排序算法总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot结成MyBatis-Plus最全配置指南

《SpringBoot结成MyBatis-Plus最全配置指南》本文主要介绍了SpringBoot结成MyBatis-Plus最全配置指南,包括依赖引入、配置数据源、Mapper扫描、基本CRUD操... 目录前言详细操作一.创建项目并引入相关依赖二.配置数据源信息三.编写相关代码查zsRArly询数据库数

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

Python中DataFrame转列表的最全指南

《Python中DataFrame转列表的最全指南》在Python数据分析中,Pandas的DataFrame是最常用的数据结构之一,本文将为你详解5种主流DataFrame转换为列表的方法,大家可以... 目录引言一、基础转换方法解析1. tolist()直接转换法2. values.tolist()矩阵

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

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

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式