排序算法（冒泡、插入、选择、快排、归并）原理动画及Python、Java实现

排序算法（冒泡、插入、选择、快排、归并）原理动画及Python、Java实现

  • 1 冒泡排序
    • 1.1 原理
    • 1.2 Python、Java实现
  • 2 插入排序
    • 2.1 原理
    • 2.2 Python、Java实现
  • 3 选择排序
    • 3.1 原理
    • 3.2 Python、Java实现
  • 4 快速排序
    • 4.1 原理
    • 4.2 Python
  • 5 归并排序
    • 5.1 原理
    • 5.2 Python

目前就总结这五种了，其它的后面看到了再弄。

1 冒泡排序

参考冒泡排序（详细图解分析+实现，小白一看就会）

1.1 原理

从序列的第一个元素开始，比较相邻两个元素，若顺序错误（如：从小到大排序时，前一个元素大于后一个元素），则交换位置。继续对下一对相邻元素执行相同的操作，直到序列的末尾。

核心：多趟排序，把最大的泡浮上来
每一轮排序的目的都是找到整个数组中最大的数并把它排在最后端，最后一个最大数不再比较移动。一轮一轮的比较，直到只剩下一个数时（完成了N趟的排序）这个排序就完成了，从而实现从小到大的排序。
在这里插入图片描述

1.2 Python、Java实现

def BubbleSort(nums):  # 从小到大n = len(nums)for i in range(n):  # 排序n轮for j in range(n - 1):  # 比较n-1组if nums[j] > nums[j + 1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]return numsnums = [29, 10, 14, 37, 12, 6, 32]
print(BubbleSort(nums))  # [6, 10, 12, 14, 29, 32, 37]"""用一个标记优化"""
def BubbleSort(nums):  # 从小到大n = len(nums)for i in range(n):  # 排序n轮exchange = 0  # 标记是否进入排序循环for j in range(n - 1):  # 比较n-1组if nums[j] > nums[j + 1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]exchange = 1# 如果前面的for循环都结束了，还没有一次交换，说明i后面已经完成了排序# 而前面的排序也已经在前面几轮中完成，所以可以直接跳出循环if exchange == 0:  breakreturn numsnums = [29, 10, 14, 37, 12, 6, 32]
print(BubbleSort(nums))  # [6, 10, 12, 14, 29, 32, 37]

import java.util.Arrays;public class Main {public static void main(String[] args) {int[] nums = {29, 10, 14, 37, 12, 6, 32};BubbleSort(nums);
//        System.out.println(nums);  // 这样会直接输出地址System.out.println(Arrays.toString(nums));  // 一开始想的是循环输出，这样后面的"]"前面还会有", "出现// [6, 10, 12, 14, 29, 32, 37]}/*如果函数被声明为static，它就可以被类直接调用，而不需要实例化类对象。如果函数没有被声明为static，它就必须通过实例化类对象来调用。*/public static void BubbleSort(int[] nums){int n = nums.length;for (int i = 0; i < n; i++) {for (int j = 0; j < n - 1; j++) {if (nums[j] > nums[j+1]) {int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;}}}}}/*函数部分优化*/public static void BubbleSort(int[] nums){int n = nums.length;for (int i = 0; i < n; i++) {int exchange = 0;for (int j = 0; j < n - 1; j++) {if (nums[j] > nums[j+1]) {int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;exchange = 1;}}if (exchange == 0){break;}}}

时间复杂度：O(n^2)

是稳定的吗？
稳定指的是相同的数的相对位置是否改变，即5, 0, 9, 11, 9里面的两个9最后位置是否变化。冒泡排序是稳定的。 这一点在if nums[j] > nums[j + 1]中可以看出。

2 插入排序

十大排序算法（冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序）

2.1 原理

就像是打扑克牌的摸牌过程，每从牌池里抽取一张牌，都会与手头已有的牌做比较，把它放在合适的位置。
在这里插入图片描述
描述：假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序，直到整个序列有序。一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
在这里插入图片描述

2.2 Python、Java实现

def InsertSort(nums):  # 从小到大n = len(nums)for i in range(1, n):  # 外部插入排序，默认第一个数有序，从第二个数开始排序if nums[i] < nums[i-1]:  # 现在这个数小于前面的数时，才进入排序过程（就好像拿到了大王直接往后面一放，不需要进入手中的牌进行排序）temp = nums[i]  # 记录这个要插入的数p = i-1  # 从前面一个开始比较while nums[p] > temp and p >= 0:  # 指针指的数如果大于要插入的数，就往后挪一位nums[p+1] = nums[p]p -= 1nums[p+1] = temp  # 结束循环时，p指向小于temp的数return numsnums = [29, 10, 14, 37, 12, 6, 32]
print(InsertSort(nums))  # [6, 10, 12, 14, 29, 32, 37]

import java.util.Arrays;public class Main {public static void main(String[] args) {int[] nums = {29, 10, 14, 37, 12, 6, 32};InsertSort(nums);
//        System.out.println(nums);  // 这样会直接输出地址System.out.println(Arrays.toString(nums));  // 一开始想的是循环输出，这样后面的"]"前面还会有", "出现// [6, 10, 12, 14, 29, 32, 37]}public static void InsertSort(int[] nums){int n = nums.length;for (int i = 1; i < n; i++) {if (nums[i] < nums[i-1]){int temp = nums[i];int j;for (j = i-1; j >= 0 && nums[j] > temp; j--) {/*应该使用逻辑与符号 "&&" 而不是位与符号 "&"因为逻辑与符号会在第一个条件不成立时直接跳出循环，而位与符号会继续执行第二个条件，可能导致数组越界异常*/nums[j+1] = nums[j];}nums[j+1] = temp;}}}}

时间复杂度：O(n^2)，最好是O(n)

插入排序是稳定的。 这一点在while nums[p] > temp可以看出。

3 选择排序

选择排序（详细图解分析+实现，小白一看就会）

3.1 原理

核心：多趟选择
内层循环中：
第一次在所有n个数里面找最小值，与第一个数交换；
第二次在后面n-1个数里面找最小值，与n-1个数里面的第一个数交换……
在这里插入图片描述

3.2 Python、Java实现

def SelectSort(nums):  # 从小到大n = len(nums)for i in range(n):  # 排序n轮min_num = nums[i]min_index = ifor j in range(i+1, n):if nums[j] < min_num:min_num = nums[j]min_index = jnums[i], nums[min_index] = nums[min_index], nums[i]return numsnums = [29, 10, 14, 37, 12, 6, 32]
print(SelectSort(nums))  # [6, 10, 12, 14, 29, 32, 37]

import java.util.Arrays;public class Main {public static void main(String[] args) {int[] nums = {29, 10, 14, 37, 12, 6, 32};SelectSort(nums);System.out.println(Arrays.toString(nums));  // [6, 10, 12, 14, 29, 32, 37]}public static void SelectSort(int[] nums){int n = nums.length;for (int i = 0; i < n; i++) {int min_num = nums[i];int min_index = i;for (int j = i+1; j < n; j++) {if (nums[j] < min_num){min_num = nums[j];min_index = j;}}int temp = nums[i];nums[i] = nums[min_index];nums[min_index] = temp;}}}

可以优化，设置成同时找最大值和最小值

时间复杂度：O(n^2)

选择排序是不稳定的。 因为发生了交换，如 3，3，2，2要和第一个3交换，则两个3就换了位置。

4 快速排序

【排序算法】快速排序（全坤式超详解）———有这一篇就够啦

4.1 原理

分治思想：随机选一个pivot（一般是最左边或者最右边），然后比 pivot 小的放左边、大的放右边。
在这里插入图片描述

4.2 Python

用递归很快：

def QuickSort(nums):  # 从小到大if len(nums) <= 1:return numselse:pivot = nums[0]left = [num for num in nums[1:] if num < pivot]right = [num for num in nums[1:] if num >= pivot]return QuickSort(left) + [pivot] + QuickSort(right)nums = [29, 10, 14, 37, 12, 6, 32]
print(QuickSort(nums))  # [6, 10, 12, 14, 29, 32, 37]

Java版本就不写了。
左右指针法之类的其实也用了递归，这里不写了。能搜到好多。

时间复杂度：O(nlogn)，最坏情况是O(n^2)
不稳定。

5 归并排序

5.1 原理

同样是分治思想：
在这里插入图片描述

  1. 不断的分割数据，让数据的每一段都有序（一个数据相当于有序）
  2. 当所有子序列有序的时候，在把子序列归并，形成更大的子序列，最终整个数组有序。

核心：合并两个有序数组

在这里插入图片描述

5.2 Python

def MergeSort(nums):  # 从小到大if len(nums) > 1:mid = len(nums) // 2  # 这里不能用 / 来除，会出现小数L = nums[:mid]R = nums[mid:]  # 递归到这里的时候，已经全部拆分成了长度为1的数组，也就是最底层# 递归MergeSort(L)MergeSort(R)# 到这一步的时候，其实就是开始从最底层处理，开始合并l = r = k = 0while l < len(L) and r < len(R):if L[l] <R[r]:nums[k] = L[l]l += 1else:nums[k] = R[r]r += 1k += 1# 左右数组长度可能不一样，所以还要检查是否还有剩余元素while l < len(L):  # 经过了上面，l按理来说应该正好等于len(L)了，如果还小于，说明有剩余的数nums[k] = L[l]l += 1k += 1while r < len(R):  # 经过了上面，l按理来说应该正好等于len(L)了，如果还小于，说明有剩余的数nums[k] = R[r]r += 1k += 1return numsnums = [29, 10, 14, 37, 12, 6, 32]
print(MergeSort(nums))  # [6, 10, 12, 14, 29, 32, 37]

Java版本就不写了。
左右指针法之类的其实也用了递归，这里不写了。能搜到好多。

时间复杂度：O(nlogn)
稳定。

这几种就总结到这里了，其它堆排序之类的也都可以直接看十大排序算法（冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序），接下来可以去牛客网刷题巩固了。

我的刷题笔记（包含答案解释）：排序算法刷题笔记【牛客网】

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

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

相关文章

AI绘图提示词/咒语/词缀/关键词使用指南（Stable Diffusion Prompt 最强提示词手册）

AI绘图提示词/咒语/词缀/关键词使用指南（Stable Diffusion Prompt 最强提示词手册）

一、为什么学习AI绘画关键词 在人工智能技术飞速发展的今天&#xff0c;AI绘画已成为艺术领域的一大热点。学习AI绘画关键词&#xff0c;不仅有助于我们掌握这一新兴技术&#xff0c;还能拓宽我们的创作思路&#xff0c;实现艺术与技术的完美融合。以下是学习AI绘画关键词的几…
阅读更多...
STM32外设SPI(串行通信)，W25Q64（8Mb）

STM32外设SPI(串行通信)，W25Q64（8Mb）

1 非易失存储器:E2PROM,FLASH(断电不丢失) 2 易失存储器&#xff1a;SRAM,DRAM 3 W25Q64 1 从00 00 00 到 7F FF FF 2 block(块)&#xff0c;sector(扇区) &#xff0c;page&#xff08;页区&#xff09; 写数据到FLASH&#xff08;256字节&#xff09; 读数据很快&#…
阅读更多...
WPF MaterialDesign UI

WPF MaterialDesign UI

DialogHost
阅读更多...
优化学习管理：Moodle和ONLYOFFICE文档编辑器的完美结合

优化学习管理：Moodle和ONLYOFFICE文档编辑器的完美结合

目录 前言 一、什么是 Moodle 1、简单快速插入表单字段 3、免费表单模板库 4、开启无缝协作 三、在Moodle中集成ONLYOFFICE文档 四、在Moodle安装使用ONLYOFFICE 1、下载安装 2、配置服务器 3、在Moodle中使用ONLYOFFICE 文档活动 五、未来展望 写在最后 前言 在当今教育科技飞…
阅读更多...
Apache Druid日志实时分析

Apache Druid日志实时分析

业务分析 ​ 秒杀业务中&#xff0c;通常会有很多用户同时蜂拥而上去抢购热卖商品&#xff0c;经常会出现抢购人数远大于商品库存。其实在秒杀过程中&#xff0c;热卖商品并不多&#xff0c;几乎只占1%&#xff0c;而99%的流量都源自热卖商品&#xff0c;很有可能因为这1%的热…
阅读更多...
C--四种排序方法的补充

C--四种排序方法的补充

上一篇文章因为时间原因只写了三种&#xff0c;这一篇来补充第四种&#xff0c;第四种的代码更多&#xff0c;所需要理解的也是更多的。 堆排序 想要学会堆排序&#xff0c;你必须了解二叉树的内容。堆排序的排序速度也是非常的快。 这里都已大堆为例 1.向上调整算法&#…
阅读更多...
xampp安装federated插件，实现mysql数据同步

xampp安装federated插件，实现mysql数据同步

需求&#xff1a;a服务器上的mysql数据库data表插入新数据时&#xff0c;需要同步到b服务器上的data表中。 解决&#xff1a;a服务器上开启federated引擎插件&#xff0c;创建data1对应b服务器上的data表。 在a服务器上的data表创建触发器&#xff0c;data表插入数据后执行触发…
阅读更多...
Vue的状态管理——Vuex34Pinia

Vue的状态管理——Vuex34Pinia

Vue3中Vuex的使用_vue3 vuex-CSDN博客 VueX详解_组合式vuex-CSDN博客 15分钟学会Pinia Vuex 3和4详解 Vuex 3 Vuex 3是Vue.js 2.x版本的状态管理库&#xff0c;它提供了一种集中式存储和管理组件状态的方式。以下是Vuex 3的一些关键特性&#xff1a; 状态集中管理&#x…
阅读更多...
建模杂谈系列250 Hello2Pymc

建模杂谈系列250 Hello2Pymc

说明 pymc算是多年的老朋友了&#xff0c;中间失联了好几年。 内容 1 安装 安装更加麻烦了&#xff0c;不能很好的和其他的环境兼容。在官网上&#xff0c;也是建议用conda的方式安装。 conda create -c conda-forge -n pymc_env "pymc>5" conda activate p…
阅读更多...
自闭症儿童托管学校

自闭症儿童托管学校

在自闭症儿童的成长道路上&#xff0c;寻找一个既能够提供专业康复又充满关爱的托管学校&#xff0c;是许多家庭的重要课题。星启帆自闭症儿童康复机构&#xff0c;作为国内规模较大的自闭症儿童托管学校&#xff0c;以其专业的师资力量、科学的康复方法、严格的管理制度以及温…
阅读更多...
Milvus向量数据库-数据备份与恢复

Milvus向量数据库-数据备份与恢复

前言 随着Milvus版本的持续迭代&#xff0c;越来越多的用户将其作为构建生产环境的向量数据服务使用。作为数据服务使用&#xff0c;其中的运维、数据安全、容灾备份自然是用户最关心且不容有失的需求。为解决这一需求&#xff0c;Milvus-backup项目工具应运而生。 Milvus-ba…
阅读更多...
【并集查找 图论】2421. 好路径的数目

【并集查找 图论】2421. 好路径的数目

本文涉及知识点 C图论 LeetCode2421. 好路径的数目 给你一棵 n 个节点的树&#xff08;连通无向无环的图&#xff09;&#xff0c;节点编号从 0 到 n - 1 且恰好有 n - 1 条边。 给你一个长度为 n 下标从 0 开始的整数数组 vals &#xff0c;分别表示每个节点的值。同时给你…
阅读更多...
【C++11及其特性】函数返回值当引用

【C++11及其特性】函数返回值当引用

函数返回值当引用目录 一.若返回变量为栈变量1.例子2.不能成为其他引用的初始值3.不能作为左值 二.若返回变量为静态变量或全局变量1.列子2.即可左值也可右值 三.若返回变量为形参1.普通形参2.引用形参 四.结论 一.若返回变量为栈变量 1.例子 返回的是局部变量的引用,这里用的…
阅读更多...
【Python系列】SQLAlchemy 基本介绍

【Python系列】SQLAlchemy 基本介绍

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
5.3二叉树——二叉树链式结构实现

5.3二叉树——二叉树链式结构实现

本篇博客梳理二叉树链式结构 明确&#xff1a;二叉树是递归定义的 递归的本质&#xff1a;当前问题子问题&#xff0c;返回条件是最小规模的子问题 一、二叉树的遍历 1&#xff0e;前序、中序与后序遍历 &#xff08;1&#xff09;前序&#xff1a;根->左子树->右子树…
阅读更多...
书生大模型实战营（1）——InterStudio基础知识+Vscode SSH连接远程服务器+Linux基础指令

书生大模型实战营（1）——InterStudio基础知识+Vscode SSH连接远程服务器+Linux基础指令

参加书生.浦江大模型实战训练营&#xff0c;学习大模型知识和微调技术&#xff0c;所有课程免费&#xff0c;通过闯关的形式学习&#xff0c;也比较有趣。一起来了解LLM的世界。邀请链接 产品简介 InternStudio 是大模型时代下的云端算力平台。基于 InternLM 组织下的诸多算法…
阅读更多...
经典文献阅读之--ParkingE2E(基于摄像头的端到端停车网络：从图像到规划)

经典文献阅读之--ParkingE2E(基于摄像头的端到端停车网络：从图像到规划)

0. 简介 自动泊车是智能驾驶领域的一项关键任务。传统泊车算法通常采用基于规则的方案来实现。然而&#xff0c;由于算法设计的复杂性&#xff0c;这些方法在复杂的泊车场景中效果欠佳。相比之下&#xff0c;基于神经网络的方法往往比基于规则的方法更加直观且功能多样。通过收…
阅读更多...
ORACLE 统计信息的备份与恢复

ORACLE 统计信息的备份与恢复

备份 --需要先创建统计信息基础表 exec dbms_stats.create_stat_table(USER1,STAT_TIMESTAMP); --导出某个用户的所有统计信息 exec dbms_stats.export_schema_stats(USER1,STAT_TIMESTAMP);--测试(插入100条&#xff0c;更新统计信息&#xff0c;略) select num_rows,last_ana…
阅读更多...
基于STM32开发的简易自动驾驶系统

基于STM32开发的简易自动驾驶系统

目录 引言环境准备工作 硬件准备软件安装与配置系统设计 系统架构硬件连接代码实现 系统初始化传感器数据采集与处理电机控制与转向OLED显示与状态提示Wi-Fi通信与远程监控应用场景 简易自动驾驶演示智能车模型开发与学习常见问题及解决方案 常见问题解决方案结论 1. 引言 随…
阅读更多...
蜂鸣器奏乐

蜂鸣器奏乐

一、粗略了解简谱 拍号&#xff1a;如图&#xff0c;“2”表示一个小节有2拍&#xff0c;“4”表示4分音符为一拍 终止线表示歌曲结束 注意&#xff1a;以下音符都按以四分音符为一拍计算拍数 四分音符&#xff1a; 唱一拍 二分音符&#xff1a; 某一个音右边有一个小横线&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023