蓝桥杯python基础算法（2-1）——排序

目录

一、排序

二、例题 P3225——宝藏排序Ⅰ

三、各种排序比较

四、例题 P3226——宝藏排序Ⅱ

一、排序

（一）冒泡排序

  • 基本思想：比较相邻的元素，如果顺序错误就把它们交换过来。

（二）选择排序

  • 基本思想：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

（三）插入排序

  • 基本思想：将未排序数据插入到已排序序列的合适位置。

（四）快速排序

  • 基本思想：选择一个基准值，将数组分为两部分，小于基准值的放在左边，大于基准值的放在右边，然后对左右两部分分别进行排序。

（五）归并排序

  • 基本思想：将数组分成两个子数组，对两个子数组分别进行排序，然后将排序好的子数组合并成一个有序的数组。

 （七）桶排序

  • 基本思想：将待排序的数据元素，按照一定的规则划分到不同的“桶”中。每个桶内的数据元素再根据具体情况进行单独排序（通常可以使用其他简单排序算法，如插入排序），最后将各个桶中排好序的数据元素依次取出，就得到了一个有序的序列。

应用要点

  • 时间复杂度：不同排序算法时间复杂度不同，如冒泡排序、选择排序、插入排序平均时间复杂度为 O(n^2)​，快速排序平均时间复杂度为 O(nlogn)​，归并排序时间复杂度稳定在 O(nlogn)​。蓝桥杯题目对时间限制严格，大数据量下应优先选择 O(nlogn)​ 级别的排序算法。

  • 空间复杂度：有些题目对空间也有限制。例如归并排序空间复杂度为 O(n)​，而快速排序如果实现合理（如原地分区）空间复杂度可以为 O(logn)​。

  • 稳定性：排序稳定性指相等元素在排序前后相对位置是否改变。例如插入排序、冒泡排序是稳定的，选择排序、快速排序是不稳定的。如果题目要求保持相等元素相对顺序，要选择稳定排序算法。

二、例题 P3225——宝藏排序Ⅰ

在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。

输入描述

输入第一行包括一个数字 n ，表示宝藏总共有 n 个。

输入的第二行包括 n 个数字，第 ii 个数字 a[i] 表示第 i 个宝藏的珍贵程度。

数据保证 1≤n≤1000,1≤a[i]≤10^6 。

输出描述

输出 n 个数字，为对宝藏按照珍贵程度从小到大排序后的数组。

# 冒泡排序
def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr# 选择排序
def selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i + 1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr# 插入排序
def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j = j - 1arr[j + 1] = keyreturn arr# 快速排序
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)# 归并排序
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]left_half = merge_sort(left_half)right_half = merge_sort(right_half)return merge(left_half, right_half)def merge(left, right):result = []left_index = 0right_index = 0while left_index < len(left) and right_index < len(right):if left[left_index] < right[right_index]:result.append(left[left_index])left_index += 1else:result.append(right[right_index])right_index += 1result.extend(left[left_index:])result.extend(right[right_index:])return result# 桶排序
def bucket_sort(arr):max_val = max(arr)min_val = min(arr)bucket_size = 1000bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]for num in arr:index = (num - min_val) // bucket_sizebuckets[index].append(num)for i in range(bucket_count):buckets[i].sort()sorted_arr = []for bucket in buckets:sorted_arr.extend(bucket)return sorted_arrn = int(input())
treasures = list(map(int, input().split()))print("冒泡排序结果:")
print(bubble_sort(treasures[:]))print("选择排序结果:")
print(selection_sort(treasures[:]))print("插入排序结果:")
print(insertion_sort(treasures[:]))print("快速排序结果:")
print(quick_sort(treasures[:]))print("归并排序结果:")
print(merge_sort(treasures[:]))print("桶排序结果:")
print(bucket_sort(treasures[:]))

三、各种排序比较

import time
import random# 冒泡排序
def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr# 选择排序
def selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i + 1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr# 插入排序
def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j = j - 1arr[j + 1] = keyreturn arr# 快速排序
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)# 归并排序
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]left_half = merge_sort(left_half)right_half = merge_sort(right_half)return merge(left_half, right_half)def merge(left, right):result = []left_index = 0right_index = 0while left_index < len(left) and right_index < len(right):if left[left_index] < right[right_index]:result.append(left[left_index])left_index += 1else:result.append(right[right_index])right_index += 1result.extend(left[left_index:])result.extend(right[right_index:])return result# 桶排序
def bucket_sort(arr):max_val = max(arr)min_val = min(arr)bucket_size = 1000bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]for num in arr:index = (num - min_val) // bucket_sizebuckets[index].append(num)for i in range(bucket_count):buckets[i].sort()sorted_arr = []for bucket in buckets:sorted_arr.extend(bucket)return sorted_arr# ——————————————————————————————————————————————
# 生成测试数据
test_array = [random.randint(1, 10000) for _ in range(10000)]# 记录每种排序的时间
sorting_methods = [("冒泡排序", bubble_sort),("选择排序", selection_sort),("插入排序", insertion_sort),("快速排序", quick_sort),("归并排序", merge_sort),("桶排序", bucket_sort)
]# 比较排序结果
sorted_results = {}
for name, sort_func in sorting_methods:start_time = time.time()sorted_array = sort_func(test_array[:])end_time = time.time()sorted_results[name] = sorted_arrayprint(f"{name} 耗时: {end_time - start_time} 秒")# 比较排序结果是否一致
base_result = sorted_results[sorting_methods[0][0]]
is_consistent = True
for name, result in sorted_results.items():if result != base_result:is_consistent = Falseprint(f"{name} 的排序结果与基准排序结果不一致")if is_consistent:print("所有排序算法的排序结果一致")# 比较稳定性
# 稳定性定义: 排序后相同元素的相对顺序不变
# 生成包含重复元素的测试数据
test_stability_array = [5, 3, 8, 3, 6]
stable_sorts = []
unstable_sorts = []for name, sort_func in sorting_methods:original_array = test_stability_array[:]sorted_array = sort_func(original_array)original_indices = [i for i, x in enumerate(original_array) if x == 3]sorted_indices = [i for i, x in enumerate(sorted_array) if x == 3]if original_indices == sorted_indices:stable_sorts.append(name)else:unstable_sorts.append(name)print("\n稳定的排序算法: ", stable_sorts)
print("不稳定的排序算法: ", unstable_sorts)space_complexity = {"冒泡排序": "O(1)","选择排序": "O(1)","插入排序": "O(1)","快速排序": "O(log n) 平均, O(n) 最坏","归并排序": "O(n)","桶排序": "O(n + k) 其中 k 是桶的数量"
}print("\n空间复杂度:")
for name, complexity in space_complexity.items():print(f"{name}: {complexity}")

四、例题 P3226——宝藏排序Ⅱ

问题描述

注意：这道题于宝藏排序Ⅰ的区别仅是数据范围

在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。

输入描述

输入第一行包括一个数字 n ，表示宝藏总共有 n 个。

输入的第二行包括 n 个数字，第 i 个数字 a[i] 表示第 i 个宝藏的珍贵程度。

数据保证 1≤n≤10^5,1≤a[i]≤10^9。

输出描述

输出 n 个数字，为对宝藏按照珍贵程度从小到大排序后的数组。

list.sort()​：是Python标准库中已经实现好的方法，它是基于优化的C语言代码实现的，内部实现经过了高度优化，以确保在各种情况下都能高效运行。

n = int(input())   
treasures = list(map(int, input().split()))# 使用Python内置的排序函数进行排序   
sorted_treasures = sorted(treasures)for treasure in sorted_treasures:print(treasure, end=" ")

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/11805.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

对象的实例化、内存布局与访问定位

对象的实例化、内存布局与访问定位

一、创建对象的方式 二、创建对象的步骤: 一、判断对象对应的类是否加载、链接、初始化: 虚拟机遇到一条new指令&#xff0c;首先去检查这个指令的参数能否在Metaspace的常量池中定位到一个类的符号引用&#xff0c;并且检查这个符号引用代表的类是否已经被加载、解析和初始化…
阅读更多...
OSCP - Proving Grounds - Roquefort

OSCP - Proving Grounds - Roquefort

主要知识点 githook 注入Linux path覆盖 具体步骤 依旧是nmap扫描开始&#xff0c;3000端口不是很熟悉&#xff0c;先看一下 Nmap scan report for 192.168.54.67 Host is up (0.00083s latency). Not shown: 65530 filtered tcp ports (no-response) PORT STATE SERV…
阅读更多...
Python + Tkinter + pyttsx3实现的桌面版英语学习工具

Python + Tkinter + pyttsx3实现的桌面版英语学习工具

Python Tkinter pyttsx3实现的桌面版英语学习工具 在多行文本框输入英文句子&#xff0c;双击其中的英文单词&#xff0c;给出英文读音和中文含义和音标。 本程序查询本地词典数据。通过菜单栏"文件"->"打开词典编辑器"进入编辑界面。 词典数据存储…
阅读更多...
实验六 项目二 简易信号发生器的设计与实现 （HEU）

实验六 项目二 简易信号发生器的设计与实现 （HEU）

声明&#xff1a;代码部分使用了AI工具 实验六 综合考核 Quartus 18.0 FPGA 5CSXFC6D6F31C6N 1. 实验项目 要求利用硬件描述语言Verilog&#xff08;或VHDL&#xff09;、图形描述方式、IP核&#xff0c;结合数字系统设计方法&#xff0c;在Quartus开发环境下&#xff…
阅读更多...
17.3.4 颜色矩阵

17.3.4 颜色矩阵

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 17.3.4.1 矩阵基本概念 矩阵&#xff08;Matrix&#xff09;是一个按照长方阵列排列的复数或实数集合&#xff0c;类似于数组。 由…
阅读更多...
音视频入门基础：RTP专题（8）——使用Wireshark分析RTP

音视频入门基础：RTP专题（8）——使用Wireshark分析RTP

一、引言 通过Wireshark可以抓取RTP数据包&#xff0c;该软件可以从Wireshark Go Deep 下载。 二、通过Wireshark抓取RTP数据包 首先通过FFmpeg将一个媒体文件转推RTP&#xff0c;生成RTP流&#xff1a; ffmpeg -re -stream_loop -1 -i input.mp4 -vcodec copy -an -f rtp …
阅读更多...
【leetcode100】路径总和Ⅲ

【leetcode100】路径总和Ⅲ

1、题目描述 给定一个二叉树的根节点 root &#xff0c;和一个整数 targetSum &#xff0c;求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始&#xff0c;也不需要在叶子节点结束&#xff0c;但是路径方向必须是向下的&#xff08;只能从父节点…
阅读更多...
解锁数据结构密码：层次树与自引用树的设计艺术与API实践

解锁数据结构密码：层次树与自引用树的设计艺术与API实践

1. 引言&#xff1a;为什么选择层次树和自引用树&#xff1f; 数据结构是编程中的基石之一&#xff0c;尤其是在处理复杂关系和层次化数据时&#xff0c;树形结构常常是最佳选择。层次树&#xff08;Hierarchical Tree&#xff09;和自引用树&#xff08;Self-referencing Tree…
阅读更多...
python-leetcode-二叉树的层序遍历

python-leetcode-二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣&#xff08;LeetCode&#xff09; # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right from coll…
阅读更多...
c++可变参数详解

c++可变参数详解

目录 引言 库的基本功能 va_start 宏: va_arg 宏 va_end 宏 va_copy 宏 使用 处理可变参数代码 C11可变参数模板 基本概念 sizeof... 运算符 包扩展 引言 在C编程中&#xff0c;处理不确定数量的参数是一个常见的需求。为了支持这种需求&#xff0c;C标准库提供了 &…
阅读更多...
w191教师工作量管理系统的设计与实现

w191教师工作量管理系统的设计与实现

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…
阅读更多...
Vuex状态管理

Vuex状态管理

1、Vuex 是什么&#xff1f; Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式 库。它采用集中式存储管理应用的所有组件的状态&#xff0c;并以相应的规则保证状态以一种可预测的方式发生变化。 简单理解 Vuex可以帮我们管理全局的属性&#xff0c;并且是是响应式的&…
阅读更多...
DBASE DBF数据库文件解析

DBASE DBF数据库文件解析

基于Java实现DBase DBF文件的解析和显示 JDK19编译运行&#xff0c;实现了数据库字段和数据解析显示。 首先解析数据库文件头代码 byte bytes[] Files.readAllBytes(Paths.get(file));BinaryBufferArray bis new BinaryBufferArray(bytes);DBF dbf new DBF();dbf.VersionN…
阅读更多...
亚博microros小车-原生ubuntu支持系列：20 ROS Robot APP建图

亚博microros小车-原生ubuntu支持系列：20 ROS Robot APP建图

依赖工程 新建工程laserscan_to_point_publisher src/laserscan_to_point_publisher/laserscan_to_point_publisher/目录下新建文件laserscan_to_point_publish.py #!/usr/bin/env python3import rclpy from rclpy.node import Node from geometry_msgs.msg import PoseStam…
阅读更多...
冷启动+强化学习：DeepSeek-R1 的原理详解——无需监督数据的推理能力进化之路

冷启动+强化学习：DeepSeek-R1 的原理详解——无需监督数据的推理能力进化之路

本文基于 DeepSeek 官方论文进行分析，论文地址为：https://github.com/deepseek-ai/DeepSeek-R1/blob/main/DeepSeek_R1.pdf 有不足之处欢迎评论区交流 原文翻译 在阅读和理解一篇复杂的技术论文时，逐字翻译是一个重要的步骤。它不仅能帮助我们准确把握作者的原意，还能为后续…
阅读更多...
优选算法的灵动之章：双指针专题（一）

优选算法的灵动之章：双指针专题（一）

个人主页&#xff1a;手握风云 专栏&#xff1a;算法 一、双指针算法思想 双指针算法主要用于处理数组、链表等线性数据结构中的问题。它通过设置两个指针&#xff0c;在数据结构上进行遍历和操作&#xff0c;从而实现高效解决问题。 二、算法题精讲 2.1. 查找总价格为目标值…
阅读更多...
数据结构之栈和队列(超详解)

数据结构之栈和队列(超详解)

文章目录 概念与结构栈队列 代码实现栈栈是否为空&#xff0c;取栈顶数据、栈的有效个数 队列入队列出队列队列判空&#xff0c;取队头、队尾数据&#xff0c;队列的有效个数 算法题解有效的括号用队列实现栈用栈实现队列复用 设计循环队列数组结构实现循环队列构造、销毁循环队…
阅读更多...
解析 Oracle 中的 ALL_SYNONYMS 和 ALL_VIEWS 视图：查找同义词与视图的基础操作

解析 Oracle 中的 ALL_SYNONYMS 和 ALL_VIEWS 视图：查找同义词与视图的基础操作

目录 前言1. ALL_SYNONYMS 视图2. ALL_VIEWS 视图3. 扩展 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 1. ALL_SYNONYMS 视图 在 Oracle 数据库中&#xff0c;同义词&#xff08;Synonym&#xff09;是对数…
阅读更多...
DeepSeek-R1 本地部署教程（超简版）

DeepSeek-R1 本地部署教程（超简版）

文章目录 一、DeepSeek相关网站二、DeepSeek-R1硬件要求三、本地部署DeepSeek-R11. 安装Ollama1.1 Windows1.2 Linux1.3 macOS 2. 下载和运行DeepSeek模型3. 列出本地已下载的模型 四、Ollama命令大全五、常见问题解决附&#xff1a;DeepSeek模型资源 一、DeepSeek相关网站 官…
阅读更多...
【C语言入门】解锁核心关键字的终极奥秘与实战应用（二）

【C语言入门】解锁核心关键字的终极奥秘与实战应用（二）

目录 一、sizeof 1.1. 作用 2.2. 代码示例 二、const 2.1. 作用 2.2. 代码示例 三、signed 和 unsigned 3.1. 作用 3.2. 代码示例 四、struct、union、enum 4.1. struct&#xff08;结构体&#xff09; 4.1.1. 作用 4.1.2. 代码示例 4.2. union&#xff08;联合…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023