2024年回炉计划之排序算法(一)

2024-01-19 07:52
文章标签 算法 排序 2024 计划 回炉

本文主要是介绍2024年回炉计划之排序算法(一),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法是计算机科学和信息技术中的重要领域,涉及到问题求解和数据处理的方法。要学习算法,你可能需要掌握以下一些基本知识:

  1. 基本数据结构: 了解和熟练使用各种数据结构,如数组、链表、栈、队列、树和图等。数据结构是算法的基础,不同的问题可能需要不同的数据结构来解决。

  2. 算法的时间复杂度和空间复杂度: 理解算法的运行时间和空间占用对于选择合适的算法至关重要。学习如何分析算法的时间复杂度和空间复杂度,以便能够在不同情境下做出合理的选择。

  3. 排序和搜索算法: 排序和搜索是常见的算法问题。了解各种排序算法(如冒泡排序、快速排序、归并排序等)和搜索算法(如二分查找、深度优先搜索、广度优先搜索等)。

  4. 递归和迭代: 了解递归和迭代的概念,以及它们在算法设计中的应用。有时,递归是一种简洁而优雅的解决问题的方式。

  5. 动态规划和贪心算法: 学会应用动态规划和贪心算法解决问题。这两种方法在解决一些优化问题时非常有效。

  6. 图算法: 理解图的基本概念和算法,如深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法(Dijkstra、Bellman-Ford)、最小生成树算法(Prim、Kruskal)等。

  7. 字符串匹配算法: 了解字符串匹配问题和相关的算法,如暴力法、KMP 算法、Boyer-Moore 算法等。

  8. 数学基础: 一些算法问题涉及到数学知识,特别是在设计和分析算法时。熟悉一些基本的数学概念和运算,可能会有助于理解某些算法的原理。

  9. 算法设计模式: 了解一些常见的算法设计模式,如分治法、贪心法、动态规划等。这有助于你在解决问题时选择合适的策略。

  10. 实践和练习: 最重要的是实践。通过解决各种算法问题,参与编程竞赛,或者在实际项目中应用算法,能够更好地理解和掌握算法。

        回归正题,特种兵有年度演习,开发者也应有年度回炉,不然脑袋锈掉。本周开启算法训练,先从排序算法开始(使用TS编码)。

一、冒泡排序

        在此之前,先弄个实现一个方法:

  • generateUniqueRandomIntegers: 函数名称。
  • count: number: 生成随机整数的个数。
  • max: number: 随机整数的最大值(包含在生成范围内)。
  • min: number = 0: 随机整数的最小值,默认为 0。
/*** 生成指定范围、个数、不重复的随机正整数集合。* @param count 范围* @param max 最大数* @param min 最小数*/
export function generateUniqueRandomIntegers(count: number, max: number, min: number = 0): number[] {if (count <= 0 || max <= min || !Number.isInteger(max) || !Number.isInteger(min) || !Number.isInteger(count)) {throw new Error("Invalid input parameters.Please ensure count is a positive integer, min is a non-negative integer, max is a positive integer greater than min.")}if (!(count <= (max - min + 1))) {throw new Error("(max - min + 1) should be >= count.")}const result: number[] = [];const uniqueNumbers: Set<number> = new Set();while (uniqueNumbers.size < count) {const randomInteger = Math.floor(Math.random() * (max - min +1)) + min;uniqueNumbers.add(randomInteger);}uniqueNumbers.forEach((value) => {result.push(value)})return  result;
}

        冒泡排序是最简单的排序算法之一,其基本思想是将相邻的两个元素进行比较,如果顺序不对就交换它们的位置。该算法的时间复杂度为O(n^2)。

const maopaoClickListener = () => {let length: number = 4;let array: number[] = generateUniqueRandomIntegers(length, 100, 1);rawData.value = JSON.stringify([...array])for (let i = 0; i < length - 1; i++) {let flag = false;for (let j = 0; j < length - 1 - i; j++) {if (array[j] > array[j + 1]) {let temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true;}}if (!flag) break;}result.value = JSON.stringify([...array])
}

二、插入排序

        插入排序的基本思想是将未排序序列(无序)中的每个元素插入到已排序序列(有序)的合适位置。该算法的时间复杂度也为O(n^2)。

        第一步,分为有序、无序两部分。

        第二步,取出无序部分的首个,在有序部分从后往前比较,插入到合适的部分。

        拆解: 代码部分第一个for(i=1;;i++),队列首个【3】是有序的,那么,i = 1,而非 0;

        拆解: 代码部分 j = i - 1; array[i] 往前逐个比较,有序部分逐个后移,直到找到合适位置;

const charuClickListener = () => {let length: number = 4;let array: number[] = generateUniqueRandomIntegers(length,100,1);rawData.value = JSON.stringify([...array])for (let i = 1; i < length; i++) {let itemI = array[i]let j = i - 1// 条件:有序值 大于 无序首个while (j > 0 && array[j] > itemI) {// 往后移array[j + 1] = array[j]j--}array[j + 1] = itemI}result.value = JSON.stringify([...array])
}

三、选择排序

        选择排序的基本思想是每次选择未排序序列中最小或最大的元素,将其放到已排序序列的末尾。该算法的时间复杂度也为O(n^2)。

        

const xuanzeClickListener = () => {let length: number = 4;let array: number[] = getArray(length);rawData.value = JSON.stringify({...array})for (let i = 0; i < length; i++) {let minIndex = ifor (let j = i + 1; j < length; j++) {if (array[i] > array[j]) {minIndex = j}}let temp = array[i]array[i] = array[minIndex]array[minIndex] = temp}result.value = JSON.stringify({...array})
}

这篇关于2024年回炉计划之排序算法(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Python中lambda排序的六种方法

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

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

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

《Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)》:本文主要介绍Python基于火山引擎豆包大模型搭建QQ机器人详细的相关资料,包括开通模型、配置APIKEY鉴权和SD... 目录豆包大模型概述开通模型付费安装 SDK 环境配置 API KEY 鉴权Ark 模型接口Prompt

Oracle数据库执行计划的查看与分析技巧

《Oracle数据库执行计划的查看与分析技巧》在Oracle数据库中,执行计划能够帮助我们深入了解SQL语句在数据库内部的执行细节,进而优化查询性能、提升系统效率,执行计划是Oracle数据库优化器为... 目录一、什么是执行计划二、查看执行计划的方法(一)使用 EXPLAIN PLAN 命令(二)通过 S