当前位置: 首页 > news >正文

常见的8种排序(含代码):插入排序、冒泡排序、希尔排序、快速排序、简单选择排序、归并排序、堆排序、基数排序

时间复杂度O(n^2)

1、插入排序 (Insertion Sort)

        从第一个元素开始,该元素可以认为已经被排序;取出下一个元素,在已经排序的元素序列中从后向前扫描;如果该元素(已排序)大于新元素,将该元素移到下一位置;重复步骤,直到找到已排序的元素小于或者等于新元素的位置;将新元素插入到该位置后。

void insertionSort(int arr[], int n) {  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  --j;  }  arr[j + 1] = key;  }  
}

2、冒泡排序 (Bubble Sort)

        重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

void bubbleSort(int arr[], int n) {  for (int i = 0; i < n - 1; ++i) {  for (int j = 0; j < n - i - 1; ++j) {  if (arr[j] > arr[j + 1]) {  std::swap(arr[j], arr[j + 1]);  }  }  }  
}

3、简单选择排序 (Selection Sort)

        每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

void selectionSort(int arr[], int n) {  for (int i = 0; i < n - 1; i++) {  int min_idx = i;  for (int j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx]) {  min_idx = j;  }  }  std::swap(arr[min_idx], arr[i]);  }  
}  

时间复杂度O(nlog2n)

4、希尔排序(Shell Sort)

        是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法的基本思想是:先将整个待排序的记录序列分割成为若干子序列(由相隔某个“增量”的记录组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
(这里只给出增量的简化选择,实际应用中增量序列的选择会更复杂)

void shellSort(int arr[], int n) {  int gap = n / 2;  while (gap > 0) {  for (int i = gap; i < n; ++i) {  int temp = arr[i];  int j = i;  while (j >= gap && arr[j - gap] > temp) {  arr[j] = arr[j - gap];  j -= gap;  }  arr[j] = temp;  }  gap /= 2;  }  
}

5、快速排序(Quick Sort)

        通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

int partition(int arr[], int low, int high) {  int pivot = arr[high];  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  if (arr[j] < pivot) {  i++;  std::swap(arr[i], arr[j]);  }  }  std::swap(arr[i + 1], arr[high]);  return (i + 1);  
}  void quickSort(int arr[], int low, int high) {  if (low < high) {  int pi = partition(arr, low, high);  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  
}

6、堆排序(Heap Sort)

        堆排序是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。堆排序主要要解决两个问题:

        1)如何根据给定的序列建初始堆

         2)如何在交换掉根结点后,将剩下的结点调整为新的堆(筛选)

void set(int p,int m){//小顶堆int i,j;i=p;j=i*2;while(j<=m){if(j<=m-1&&k[j]>k[j+1])//改为<j++;if(k[j]>=k[i])//改为<=,则为大顶堆break;else{swap(k[i],k[j]);i=j;j=i*2;}}
}void heapSort(){int i,j;for(i=n/2;i>0;i--)//建堆set(i,n);for(i=n;i>1;i--)//排序{swap(k[i],k[1]);set(1,i-1);}
}

7、归并排序 (Merge Sort)

        归并排序采用分治法的思想,将数组分成两半,分别对它们进行排序,然后将结果合并起来。

        1)编写一个辅助函数来合并两个已排序的子数组。

        2)编写主归并排序函数,该函数将递归地分解数组,直到子数组只包含一个元素(已排序),然后合并这些子数组,直到整个数组排序完成。

void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {  int i = 0, j = 0, k = 0;  while (i < leftSize && j < rightSize) {  if (left[i] <= right[j]) {  arr[k++] = left[i++];  } else {  arr[k++] = right[j++];  }  }  while (i < leftSize) {  arr[k++] = left[i++];  }  while (j < rightSize) {  arr[k++] = right[j++];  }  
}  void mergeSort(int arr[], int left, int right) {  if (left < right) {  int mid = left + (right - left) / 2;  int leftSize = mid - left + 1;  int rightSize = right - mid;  int leftArr[leftSize], rightArr[rightSize];  // 拷贝数据到临时数组  for (int i = 0; i < leftSize; i++) {  leftArr[i] = arr[left + i];  }  for (int j = 0; j < rightSize; j++) {  rightArr[j] = arr[mid + 1 + j];  }  // 递归地对子数组进行排序  mergeSort(leftArr, 0, leftSize - 1);  mergeSort(rightArr, 0, rightSize - 1);  // 合并两个已排序的子数组  merge(arr, leftArr, leftSize, rightArr, rightSize);  }  
}  

时间复杂度O(d(n+rd))

8、基数排序(Radix Sort)

        基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。为了适用于负数和非整数,这里给出一个简化的版本,仅适用于非负整数,并且假设所有整数的位数相同(或可以通过填充前导零来使它们具有相同的位数)。

#include <vector>  
#include <algorithm>  void countingSort(std::vector<int>& arr, int exp) {  std::vector<int> output(arr.size());  std::vector<int> count(10, 0);  // 存储每个桶中的元素数量  for (int i = 0; i < arr.size(); i++)  count[(arr[i] / exp) % 10]++;  // 更改count[i],使其包含每个数字小于或等于i的数量  for (int i = 1; i < 10; i++)  count[i] += count[i - 1];  // 构建输出数组  for (int i = arr.size() - 1; i >= 0; i--) {  output[count[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  }  // 复制回原数组  for (int i = 0; i < arr.size(); i++)  arr[i] = output[i];  
}  void radixsort(std::vector<int>& arr) {  int maxVal = *std::max_element(arr.begin(), arr.end());  // 找到最大数的位数  int exp = 1;  while (maxVal / exp > 0) {  countingSort(arr, exp);  exp *= 10;  }  
}  

或者

#include <iostream>  
#include <cmath>  
#include <algorithm> // 使用std::max来找到数组中的最大值  // 获取数组中的最大值  
int getMax(int arr[], int n) {  int mx = arr[0];  for (int i = 1; i < n; i++) {  if (arr[i] > mx) {  mx = arr[i];  }  }  return mx;  
}  // 基数排序函数  
void radixsort(int arr[], int n) {  // 找到数组中的最大值  int maxVal = getMax(arr, n);  // 基数排序使用计数排序作为子程序  // 这里为了简单起见,我们假设所有的整数都是非负的  // 如果有负数,需要做适当的转换  // 对每一位执行计数排序  for (int exp = 1; maxVal / exp > 0; exp *= 10) {  int output[n]; // 输出数组  int count[10] = {0}; // 计数器数组  // 存储每个元素的频次  for (int i = 0; i < n; i++) {  int index = (arr[i] / exp) % 10;  count[index]++;  }  // 更改count[i]的值,这样它现在包含位置i处之前的所有元素  for (int i = 1; i < 10; i++) {  count[i] += count[i - 1];  }  // 生成输出数组  for (int i = n - 1; i >= 0; i--) {  int index = (arr[i] / exp) % 10;  output[count[index] - 1] = arr[i];  count[index]--;  }  // 将排序后的元素复制回原数组  for (int i = 0; i < n; i++) {  arr[i] = output[i];  }  }  
}  int main() {  int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};  int n = sizeof(arr) / sizeof(arr[0]);  radixsort(arr, n);  std::cout << "Sorted array: \n";  for (int i = 0; i < n; i++) {  std::cout << arr[i] << " ";  }  std::cout << std::endl;  return 0;  
}

28edbba515494195b2405823ebde7468.png

 

相关文章:

常见的8种排序(含代码):插入排序、冒泡排序、希尔排序、快速排序、简单选择排序、归并排序、堆排序、基数排序

时间复杂度O(n^2) 1、插入排序 (Insertion Sort) 从第一个元素开始&#xff0c;该元素可以认为已经被排序&#xff1b;取出下一个元素&#xff0c;在已经排序的元素序列中从后向前扫描&#xff1b;如果该元素&#xff08;已排序&#xff09;大于新元素&#xff0c;将该元素移到…...

go语言day2

使用cmd 中的 go install &#xff1b; go build 命令出现 go cannot find main module 错误怎么解决&#xff1f; go学习-问题记录(开发环境)go: cannot find main module&#xff1b; see ‘go help modules‘_go: no flags specified (see go help mod edit)-CSDN博客 在本…...

vue echarts画多柱状图+多折线图

<!--多柱状图折线图--> <div class"echarts-box" id"multiBarPlusLine"></div>import * as echarts from echarts;mounted() {this.getMultiBarPlusLine() },getMultiBarPlusLine() {const container document.getElementById(multiBar…...

cesium for unity 打包webgl失败,提示不支持

platform webgl is not supported with HDRP use the Vulkan graphics AR instead....

python开发基础——day7 序列类型方法

一、初识序列类型方法 序列类型的概念&#xff1a;数据的集合&#xff0c;在序列类型里面可以存放任意的数据&#xff0c;也可以对数据进行更方便的操作&#xff0c;这个操作是叫增删改查(crud) ( 增加(Creat)&#xff0c;读取查询(Retrieve)&#xff0c;更新(Update)&#xf…...

用java写一个二叉树翻转

class TreeNode {int val;TreeNode left, right;TreeNode(int val) {this.val val;left right null;} }public class BinaryTree {TreeNode root;// 递归翻转二叉树public TreeNode invertTree(TreeNode root) {if (root null) {return null;}// 递归翻转左子树和右子树Tre…...

数学建模系列(3/4):典型建模方法

目录 引言 1. 回归分析 1.1 线性回归 基本概念 Matlab实现 1.2 多元回归 基本概念 Matlab实现 1.3 非线性回归 基本概念 Matlab实现 2. 时间序列分析 2.1 时间序列的基本概念 2.2 移动平均 基本概念 Matlab实现 2.3 指数平滑 基本概念 Matlab实现 2.4 ARIM…...

AI播客下载:Machine Learning Street Talk(AI机器学习)

该频道由 Tim Scarfe 博士、Yannic Kilcher 博士和 Keith Duggar 博士管理。 他们做了出色的工作&#xff0c;对每个节目进行了彻底的研究&#xff0c;并与机器学习行业中一些受过最高教育、最全面的嘉宾进行了双向对话。 每一集都会教授一些新内容&#xff0c;并且提供未经过滤…...

鱼缸补水器工作原理是什么

鱼缸补水器是一种应用广泛的智能设备&#xff0c;主要用于自动监测和补充鱼缸内的水位&#xff0c;以确保鱼类生存环境的稳定。其工作原理简单而高效&#xff0c;为饲主提供了方便和安全的使用体验。 该补水器通常由两部分组成&#xff1a;控制器和吸盘。首先&#xff0c;用户…...

Linux-Tomcat服务配置到系统服务

目录 前言一、系统环境二、配置步骤step1 了解环境的安装路径step2 配置生成tomcat.pid文件step3 配置tomcat.service文件 三、测试systemctl命令管理Tomcat服务3.1 systemctl命令启动Tomcat服务3.2 systemctl命令查看Tomcat服务3.3 systemctl命令关闭Tomcat服务3.4 systemctl命…...

Python抓取高考网图片

Python抓取高考网图片 一、项目介绍二、完整代码一、项目介绍 本次采集的目标是高考网(http://www.gaokao.com/gkpic/)的图片,实现图片自动下载。高考网主页如下图: 爬取的流程包括寻找数据接口,发送请求,解析图片链接,向图片链接发送请求获取数据,最后保存数据。 二…...

Vue配置项data

data 目录 data 目录类型介绍关键原理编译过程 Vue2Vue3 &#x1f4cc;Vue.js 中的 data&#xff08;Obj/Function&#xff09;属性是 Vue 实例的一个配置选项 类型介绍 对象式 对于根实例或者非复用组件&#xff0c;通常直接提供一个对象字面量作为 data 的值。在对象式中…...

在IDEA 2024.1.3 (Community Edition)中创建Maven项目

本篇博客承继自博客&#xff1a;Windows系统Maven下载安装-CSDN博客 Maven版本&#xff1a;maven-3.9.5 修改设置&#xff1a; 首先先对Idea的Maven依赖进行设置&#xff1b;打开Idea&#xff0c;选择“Costomize”&#xff0c;选择最下边的"All settings" 之后找…...

动手学深度学习(Pytorch版)代码实践 -卷积神经网络-28批量规范化

28批量规范化 """可持续加速深层网络的收敛速度""" import torch from torch import nn import liliPytorch as lp import matplotlib.pyplot as pltdef batch_norm(X, gamma, beta, moving_mean, moving_var, eps, momentum):""&quo…...

Apache Paimon系列之:Append Table和Append Queue

Apache Paimon系列之&#xff1a;Append Table和Append Queue 一、Append Table二、Data Distribution三、自动小文件合并四、Append Queue五、压缩六、Streaming Source七、Watermark Definition八、Bounded Stream 一、Append Table 如果表没有定义主键&#xff0c;则默认为…...

Vue使用vue-esign实现在线签名 加入水印

Vue在线签名 一、目的二、样式三、代码1、依赖2、代码2.1 在线签名组件2.1.1 基础的2.1.2 携带时间水印的 2.2父组件 一、目的 又来了一个问题&#xff0c;直接让我在线签名&#xff08;还不能存储base64&#xff09;&#xff0c;并且还得上传&#xff0c;我直接***违禁词。 好…...

与码无关:分数限制下,选好专业还是选好学校?

本文的目标读者&#xff1a;24届的高考生和家长。 写这篇非技术性文章&#xff0c;是因为我看到了24届考生和21年的我同样迷茫。 事先声明&#xff0c;本文带有强烈的个人思考色彩&#xff0c;可能会引起不适&#xff0c;如有不同观点&#xff0c;欢迎在评论区讨论。 一、前言…...

什么是负载均衡技术?

随着网络技术的快速发展&#xff0c;互联网行业也越来越广泛&#xff0c;人们的日常生活中也离不开网络技术&#xff0c;大量的用户进行浏览访问网站时&#xff0c;企业会使用负载均衡技术&#xff0c;降低当前网站的负载&#xff0c;以此来提高网站的访问速度。 今天小编就来给…...

存在重复元素Ⅱ python3

存在重复元素Ⅱ 问题描述解题思路代码实现复杂度 问题描述 给你一个整数数组 nums 和一个整数 k &#xff0c;判断数组中是否存在两个 不同的索引 i 和 j &#xff0c;满足 nums[i] nums[j] 且 abs(i - j) < k 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff…...

【CV炼丹师勇闯力扣训练营 Day13:§6二叉树1】

CV炼丹师勇闯力扣训练营 代码随想录算法训练营第13天 二叉树的递归遍历 二叉树的迭代遍历、统一迭代 二叉树的层序遍历 一、二叉树的递归遍历&#xff08;深度优先搜索&#xff09; 【递归步骤】 1.确定递归函数的参数和返回值&#xff1a;确定哪些参数是递归的过程中需要处理…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...

动态规划-1035.不相交的线-力扣(LeetCode)

一、题目解析 光看题目要求和例图&#xff0c;感觉这题好麻烦&#xff0c;直线不能相交啊&#xff0c;每个数字只属于一条连线啊等等&#xff0c;但我们结合题目所给的信息和例图的内容&#xff0c;这不就是最长公共子序列吗&#xff1f;&#xff0c;我们把最长公共子序列连线起…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...