【算法基础】一文掌握十大排序算法,冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序

目录

1 冒泡排序(Bubble Sort)

2 插入排序(Insertion Sort)

3 选择排序(Selection Sort)

4. 快速排序(Quick Sort)

5. 归并排序(Merge Sort)

6 堆排序 (Heap Sort)

7 计数排序 (Counting Sort)

8 基数排序 (Radix Sort)

9 希尔排序(Shell Sort)

10 桶排序


   

1 冒泡排序(Bubble Sort)

       冒泡排序是一种基本的排序算法,其核心思想是多次遍历待排序的元素,比较相邻的两个元素,如果它们的顺序不正确,则交换它们,直到整个数组按照指定顺序排列。

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]# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("冒泡排序后的数组:", arr)

        冒泡排序通过多次遍历数组,每次比较相邻的两个元素,如果它们的顺序不正确就交换它们。这个过程将最大的元素逐渐“冒泡”到数组的末尾。

        

        时间复杂度为 O(n^2),不适合大规模数据集。 

2 插入排序(Insertion Sort)

        插入排序是一种稳定的排序算法,其核心思想是将未排序的元素逐个插入到已排序的部分,从前往后遍历,保持前面的元素有序。

def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:# 将较大的元素向右移动arr[j + 1] = arr[j]j -= 1arr[j + 1] = key# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("插入排序后的数组:", arr)

        插入排序逐个将未排序的元素插入到已排序的部分,从前往后遍历,保持前面的元素有序。时间复杂度为 O(n^2),适合小规模数据集和部分有序的数据。 

3 选择排序(Selection Sort)

        选择排序是一种简单的不稳定排序算法,其核心思想是找到未排序部分的最小元素,将其与未排序部分的第一个元素交换位置。

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 = j# 交换最小元素与未排序部分的第一个元素arr[i], arr[min_index] = arr[min_index], arr[i]# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("选择排序后的数组:", arr)

      选择排序通过多次选择未排序部分的最小元素,并将其与未排序部分的第一个元素交换位置来进行排序。时间复杂度为 O(n^2),不适合大规模数据集。

4. 快速排序(Quick Sort)

        快速排序是一种高效的分治排序算法,它选择一个基准元素,将数组分成两部分,左边的元素都小于基准,右边的元素都大于基准,然后递归对左右两部分进行排序。

def quick_sort(arr):# 基本情况:如果数组为空或只包含一个元素,无需排序if len(arr) <= 1:return arr# 选择中间元素作为基准点(pivot)pivot = 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)# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
arr = quick_sort(arr)
print("快速排序后的数组:", arr)
  • 快速排序是一种高效的分治排序算法,它通过选择一个基准点(通常是数组中的中间元素)将数组分成左右两部分,并递归地对左右两部分进行排序。
  • 基本情况是数组为空或只包含一个元素,无需排序。
  • 针对每个元素,将它与基准点进行比较,分成小于、等于和大于基准点的三个子数组。
  • 然后,递归地对左右两部分进行排序,最后将它们与基准点合并,形成一个有序的数组。

5. 归并排序(Merge Sort)

        归并排序是一种稳定的分治排序算法,它将数组分成两半,分别排序,然后将已排序的两个子数组合并成一个有序数组。

def merge_sort(arr):# 基本情况:如果数组为空或只包含一个元素,无需排序if len(arr) <= 1:return arr# 将数组分成两半mid = len(arr) // 2left = arr[:mid]right = arr[mid:]# 递归地对左右两部分进行排序left = merge_sort(left)right = merge_sort(right)# 合并已排序的左右两部分return merge(left, right)def merge(left, right):result = []i = j = 0# 合并两个已排序的子数组while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1# 如果左边或右边的子数组还有剩余元素,将它们添加到结果中result.extend(left[i:])result.extend(right[j:])return result# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
arr = merge_sort(arr)
print("归并排序后的数组:", arr)
  • 归并排序是一种稳定的分治排序算法,它将数组递归分成两半,然后合并已排序的子数组。
  • 基本情况是数组为空或只包含一个元素,无需排序。
  • 递归地对左右两部分进行排序,然后使用 merge 函数将它们合并成一个有序的数组。
  • merge 函数将两个已排序的子数组合并,同时维护它们的有序性。

6 堆排序 (Heap Sort)

        堆排序是一种不稳定的排序算法,它使用堆数据结构(通常是最大堆)来进行排序。堆排序分为两个主要步骤:建立堆和排序。

def heapify(arr, n, i):largest = ileft = 2 * i + 1right = 2 * i + 2# 找到左子节点和右子节点中的最大值if left < n and arr[left] > arr[largest]:largest = leftif right < n and arr[right] > arr[largest]:largest = right# 如果最大值不是当前节点,交换它们if largest != i:arr[i], arr[largest] = arr[largest], arr[i]def heap_sort(arr):n = len(arr)# 构建最大堆for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 一个接一个地从堆中取出元素,交换根节点与最后一个节点,然后重新构建堆for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("堆排序后的数组:", arr)
  • 排序使用堆数据结构(通常是最大堆)来进行排序。首先构建最大堆,然后一个接一个地从堆中取出元素,交换根节点与最后一个节点,然后重新构建堆。
  • heapify 函数用于维护堆的性质,即父节点的值大于或等于子节点的值。
  • 这个算法的时间复杂度为 O(nlogn),是一种高效的排序算法。

7 计数排序 (Counting Sort)

        计数排序是一种非比较排序算法,它根据输入元素的计数来对元素进行排序。它适用于整数或有限范围内的非负整数。

def counting_sort(arr):max_val = max(arr)min_val = min(arr)range_of_elements = max_val - min_val + 1count_arr = [0] * range_of_elementsoutput_arr = [0] * len(arr)# 计数每个元素的出现次数for num in arr:count_arr[num - min_val] += 1# 计算每个元素的累积计数for i in range(1, len(count_arr)):count_arr[i] += count_arr[i - 1]# 根据累积计数将元素放入输出数组for i in range(len(arr) - 1, -1, -1):output_arr[count_arr[arr[i] - min_val] - 1] = arr[i]count_arr[arr[i] - min_val] -= 1return output_arr# 示例用法
arr = [4, 2, 2, 8, 3, 3, 1]
arr = counting_sort(arr)
print("计数排序后的数组:", arr)
  • 计数排序是一种非比较排序算法,适用于整数或有限范围内的非负整数。
  • 首先,计算每个元素的出现次数,然后计算每个元素的累积计数,最后根据累积计数将元素放入输出数组。
  • 这个算法的时间复杂度为 O(n+k),其中 k 是输入范围的大小。 

8 基数排序 (Radix Sort)

        基数排序是一种非比较排序算法,它将数字按照每个位数进行排序,从最低位到最高位,依次排列。

def counting_sort(arr, exp):n = len(arr)output = [0] * ncount = [0] * 10# 计数每个元素的出现次数for i in range(n):index = arr[i] // expcount[index % 10] += 1# 计算每个元素的累积计数for i in range(1, 10):count[i] += count[i - 1]# 根据累积计数将元素放入输出数组i = n - 1while i >= 0:index = arr[i] // expoutput[count[index % 10] - 1] = arr[i]count[index % 10] -= 1i -= 1# 将输出数组的内容复制到原始数组中for i in range(n):arr[i] = output[i]def radix_sort(arr):max_val = max(arr)exp = 1while max_val // exp > 0:counting_sort(arr, exp)exp *= 10# 示例用法
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("基数排序后的数组:", arr)
  • 基数排序是一种非比较排序算法,它按照每个位数进行排序,从最低位到最高位,依次排列。
  • 首先使用计数排序对每个位数进行排序,然后再次对下一个位数进行排序,依次进行直到最高位。
  • 这个算法的时间复杂度为 O(nk),其中 k 是数字的最大位数。

9 希尔排序(Shell Sort)

        希尔排序(Shell Sort)是一种插入排序的改进版本,也被称为缩小增量排序。希尔排序通过将数组分成若干个子序列来排序数据,然后逐渐缩小子序列的间隔,最终得到一个完全排序的数组。希尔排序的主要思想是提前交换较远的元素,以加快排序过程。

算法原理

  1. 选择一个增量序列(间隔序列),通常选择的增量是数组长度的一半,然后逐渐减小增量。

  2. 对于每个增量,将数组分成若干个子序列,每个子序列使用插入排序进行排序。

  3. 重复步骤2,逐渐减小增量,直到增量为1。

  4. 当增量为1时,整个数组成为一个序列,使用插入排序对其进行排序。

def shell_sort(arr):n = len(arr)gap = n // 2  # 初始增量取数组长度的一半while gap > 0:for i in range(gap, n):temp = arr[i]j = i# 使用插入排序对子序列进行排序while j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = tempgap //= 2  # 缩小增量# 示例用法
arr = [64, 34, 25, 12, 22, 11, 90]
shell_sort(arr)
print("希尔排序后的数组:", arr)

         希尔排序的关键在于选择合适的增量序列。常见的增量序列有希尔增量、Hibbard增量、Knuth增量等,不同的增量序列会影响排序的性能。

  • 希尔排序的时间复杂度取决于增量序列的选择,平均时间复杂度通常在 O(n^1.25) 到 O(n^2) 之间,比插入排序要快。

  • 希尔排序是一种不稳定排序算法,适用于中等大小的数据集。虽然不如快速排序和归并排序快,但在某些情况下比插入排序更快。希尔排序通常用于嵌入式系统等资源有限的环境。

10 桶排序(Bucket Sort)

         桶排序(Bucket Sort)是一种分布式排序算法,它将元素分散到一组桶中,然后对每个桶中的元素进行排序,最后将所有桶中的元素按顺序合并成一个有序序列。桶排序适用于元素均匀分布在一个范围内的情况,特别适用于浮点数排序。

算法原理

  1. 确定桶的数量和范围,通常根据输入数据的分布来选择桶的数量。如果元素均匀分布在一个范围内,那么可以选择桶的数量等于元素的数量。

  2. 将每个元素分配到相应的桶中。元素的分配可以采用不同的方法,例如线性划分或哈希函数。

  3. 对每个桶中的元素进行排序,可以使用任何排序算法,通常选择插入排序。

  4. 合并所有桶中的元素,按照桶的顺序得到最终的有序序列。

def bucket_sort(arr):# 确定桶的数量,这里选择与输入元素数量相同n = len(arr)if n <= 1:return arr# 初始化桶max_val = max(arr)min_val = min(arr)bucket_range = (max_val - min_val) / n  # 每个桶的范围bucket_count = n  # 桶的数量等于元素数量buckets = [[] for _ in range(bucket_count)]# 将元素分配到桶中for num in arr:index = int((num - min_val) / bucket_range)buckets[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# 示例用法
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
arr = bucket_sort(arr)
print("桶排序后的数组:", arr)

         桶排序的性能取决于桶的数量和元素的分布。如果元素均匀分布在一个范围内,并且桶的数量足够多,那么桶排序可以非常高效。

  • 桶排序的时间复杂度通常为 O(n + k),其中 n 是元素的数量,k 是桶的数量。

  • 桶排序是一种稳定排序算法,适用于浮点数排序等特定情况。不过,它需要额外的内存空间来存储桶,因此不适用于数据集非常大的情况。

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

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

相关文章

RK3568的CAN驱动适配

目录 背景&#xff1a; 1.内核驱动模块配置 2.设备树配置 3.功能测试 4.bug修复 背景&#xff1a; 某个项目上使用RK3568的芯片&#xff0c;需要用到4路CAN接口进行通信&#xff0c;经过方案评审后决定使用RK3568自带的3路CAN外加一路spi转的CAN实现功能&#xff0c;在这个…

【Java-LangChain:使用 ChatGPT API 搭建系统-2】语言模型,提问范式与 Token

第二章 语言模型&#xff0c;提问范式与 Token 在本章中&#xff0c;我们将和您分享大型语言模型&#xff08;LLM&#xff09;的工作原理、训练方式以及分词器&#xff08;tokenizer&#xff09;等细节对 LLM 输出的影响。我们还将介绍 LLM 的提问范式&#xff08;chat format…

【计算机基础知识】字符的编码表示

欢迎来到我的&#xff1a;世界 希望作者的文章对你有所帮助&#xff0c;有不足的地方还请指正&#xff0c;大家一起学习交流 ! 目录 前言1.西文字符编码2.中文字符编码汉字输入码汉字国标码汉字机内码汉字字形码 总结 前言 计算机处理的数据中&#xff0c;除了数值型数据以外…

unity脚本_Input鼠标键盘 c#

获取鼠标坐标 检测鼠标输入 如果在运行游戏场景中点击一下鼠标左键 检测鼠标抬起 选中即可 检测键盘按下 当前屏幕分辨率 注意&#xff1a;获取的是显示器的分辨率 获取设备屏幕宽高 屏幕休眠模式 窗口/全屏模式 移动设备屏幕转向

10-Node.js入门

01.什么是 Node.js 目标 什么是 Node.js&#xff0c;有什么用&#xff0c;为何能独立执行 JS 代码&#xff0c;演示安装和执行 JS 文件内代码 讲解 Node.js 是一个独立的 JavaScript 运行环境&#xff0c;能独立执行 JS 代码&#xff0c;因为这个特点&#xff0c;它可以用来…

背靠背 HVDC-MMC模块化多电平转换器输电系统-用于无源网络系统的电能质量调节(Simulink仿真实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

《深度不确定条件下的决策:从理论到实践》PDF

制定未来计划时需要预测变化&#xff0c;尤其是制定长期计划或针对罕见事件的计划时。当这些变化存在高度不确定性的时候&#xff0c;这种预期就变得越来越困难。 今天给大家介绍的这本《深度不确定条件下的决策&#xff1a;从理论到实践》正是解决以上问题的良方。完整书籍文…

STM32--人体红外感应开关

本文主要介绍基于STM32F103C8T6和人体红外感应开关实现的控制算法 简介 人体红外模块选用HC-SR501人体红外传感器&#xff0c;人体红外感应的主要器件为人体热释电红外传感器。人体都有恒定的体温&#xff0c;一般在36~37度&#xff0c;所以会发出特定波长的红外线&#xff0…

企业电子招投标采购系统源码之电子招投标的组成

功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为外部供…

手把手教你编写LoadRunner脚本

编写 LoadRunner 脚本需要熟悉脚本语言、业务场景、参数化技术、断言和事务等基础知识。 在实际编写时&#xff0c;可以根据具体测试需求&#xff0c;结合实际情况进行合理的配置和调整。 基本步骤 创建脚本 在 LoadRunner 的 Controller 模块中&#xff0c;创建一个新的测试…

数据结构——堆(C语言)

本篇会解决一下几个问题&#xff1a; 1.堆是什么&#xff1f; 2.如何形成一个堆&#xff1f; 3.堆的应用场景 堆是什么&#xff1f; 堆总是一颗完全二叉树堆的某个节点总是不大于或不小于父亲节点 如图&#xff0c;在小堆中&#xff0c;父亲节点总是小于孩子节点的。 如图&a…

为go vet添加一个新的分析器,用于检查append后面的值缺失

缘起: 2023年5月25号&#xff0c;知名Go技术专家&#xff0c;WA语言联合发起人&#xff0c;多本技术书籍的合著者柴大&#xff0c;遇到一个append忘记写要添加的元素&#xff0c;只写了第一个参数(要追加的切片)的问题&#xff0c;可以编译通过&#xff0c;但大概率不是开发者本…

应用层协议 HTTP

一、应用层协议 我们已经学过 TCP/IP , 已然知道数据能从客户端进程经过路径选择跨网络传送到服务器端进程。 我们还需要知道的是&#xff0c;我们把数据从 A 端传送到 B 端&#xff0c; TCP/IP 解决的是顺丰的功能&#xff0c;而两端还要对数据进行加工处理或者使用&#xf…

SSM - Springboot - MyBatis-Plus 全栈体系(二十一)

第四章 SpringMVC 四、RESTFUL 风格设计和实战 1. RESTFul 风格概述 1.1 RESTFul 风格简介 RESTful&#xff08;Representational State Transfer&#xff09;是一种软件架构风格&#xff0c;用于设计网络应用程序和服务之间的通信。它是一种基于标准 HTTP 方法的简单和轻量…

TCP四次挥手

四次挥手发生在断开连接的时候&#xff0c;在程序中当调用了close()会使用TCP协议进行四次挥手。 客户端和服务器端都可以主动发起断开连接&#xff0c;谁先调用close()谁就是发起。 因为在TCP连接的时候&#xff0c;采用三次握手建立的的连接是双向的&#xff0c;在断开的时候…

股票买进和卖出手续费怎么算,一文看懂,不用研究那些旧规则了

先说结论 印花税&#xff0c;上个月刚下调为0.05%&#xff08;万分之五&#xff09;&#xff0c;单向收取 过户费&#xff0c;最新政策是0.001%&#xff08;十万分之一&#xff09;&#xff0c;双向收取 券商佣金&#xff0c;各家不同&#xff0c;每个客户经理也不同0.0086%…

python笔记:pandas/geopandas DataFrame逐行遍历

在Pandas和GeoPandas中&#xff0c;可以使用几种不同的方法来遍历DataFrame的每一行 0 数据 import pandas as pddata {column1: range(1, 1001),column2: range(1001, 2001) } df pd.DataFrame(data) df 1 iterrows for index, row in df.iterrows():print(index)print(r…

ChatGPT Vision初体验

本周&#xff0c;OpenAI为其广受欢迎的 ChatGPT 平台发布了一项突破性的补充。除了处理文本之外&#xff0c;ChatGPT 现在还可以处理图像并聊天。 很难夸大这件事的重要性。目前多达70% 的内容是视觉内容而不是书面内容。人们每年会生成数千张照片&#xff0c;而当今许多最大的…

FastThreadLocal 快在哪里 ?

FastThreadLocal 快在哪里 &#xff1f; 引言FastThreadLocalset如何获取当前线程私有的InternalThreadLocalMap &#xff1f;如何知道当前线程使用到了哪些FastThreadLocal实例 ? get垃圾回收 小结 引言 FastThreadLocal 是 Netty 中造的一个轮子&#xff0c;那么为什么放着…

JavaScript系列从入门到精通系列第十八篇:JavaScript中的函数作用域

文章目录 前言 一&#xff1a;函数作用域 前言 我们刚才提到了&#xff0c;在<Script>标签当中进行定义的变量、对象、函数对象都属于全局作用域&#xff0c;全局作用域在页面打开的时候生效在页面关闭的时候失效。 一&#xff1a;函数作用域 调用函数时创建函数作用域…