程序员不得不知道的排序算法-上

目录

前言

1.冒泡排序

2.选择排序

3.插入排序

4.希尔排序

5.快速排序

6.归并排序

总结

前言

今天给大家讲一下常用的排序算法

1.冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地从待排序的元素中比较相邻的两个元素，如果它们的顺序错误就交换它们，直到整个序列有序为止。

冒泡排序的基本思想是通过不断交换相邻的元素，将最大（或最小）的元素逐渐“冒泡”到序列的末尾。每一轮冒泡操作都会将当前未排序部分的最大（或最小）元素放到已排序部分的末尾。

 

代码实现

public static void BubbleSort(int[] arr){for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr.length-1; j++) {if(arr[j] > arr[j+1]){swap(arr,j,j+1);}}System.out.println("第"+(i+1)+"轮");System.out.println(Arrays.toString(arr));}
}public static void swap(int[] arr,int i,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

看出来了没?,多循环了两次,明明我们后面的已经有序了,就没有必要再进行比较了,基于此可以来改善我们的代码

public static void BubbleSort(int[] arr){for (int i = 0; i < arr.length; i++) {boolean flag = false;for (int j = 0; j < arr.length-1 -i; j++) {if(arr[j] > arr[j+1]){swap(arr,j,j+1);flag = true;}}if(!flag){break;}}
}

定义标志位flag 如果遍历一遍数组,没有发生交换,就说明已经有序了,直接跳出即可

时间复杂度: 冒泡排序的时间复杂度是O(n2)，其中n是待排序数组的长度。冒泡排序的基本思想是通过不断交换相邻的元素，将最大（或最小）的元素逐渐“冒泡”到序列的末尾。每一轮冒泡操作都需要比较和交换n-1次，总共需要进行n-1轮冒泡操作。因此，总的比较和交换次数为(n-1) + (n-2) + ... + 1 = n(n-1)/2，时间复杂度为O(n2)。

空间复杂度: 冒泡排序的空间复杂度是O(1)，因为它只需要使用常数级别的额外空间来存储临时变量。

稳定性: 冒泡排序是一种稳定的排序算法。稳定性指的是如果两个元素的值相等，排序后它们的相对顺序不会发生改变。在冒泡排序中，只有当相邻两个元素需要交换时才会改变它们的相对顺序，因此相等元素的相对顺序不会发生改变，冒泡排序是稳定的排序算法。

2.选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每次从待排序的元素中选择最小（或最大）的元素，放到已排序部分的末尾。

选择排序的实现步骤如下：

  1. 遍历待排序的数组，从第一个元素开始。
  2. 在未排序部分中找到最小（或最大）的元素，记录其位置。
  3. 将最小（或最大）的元素与当前遍历位置的元素交换位置，将最小（或最大）的元素放到已排序部分的末尾。
  4. 重复步骤2和步骤3，直到遍历完整个数组，排序完成。

代码实现

public static void selectSort(int[] arr){for (int i = 0; i < arr.length; i++) {// 默认认为i下标的元素为最小值int minIndex = i;for (int j = i+1; j < arr.length; j++) {if(arr[j] < arr[minIndex]){// 碰见更小的元素,更新minIndex的值minIndex = j;}}swap(arr,i,minIndex);}
}

 时间复杂度: 选择排序和冒泡排序的时间复杂度都是O(n^2)，其中n是待排序数组的长度。它们都是基于比较的排序算法，需要进行n(n-1)/2次比较操作。

空间复杂度: 选择排序的空间复杂度是O(1)，因为它只需要使用常数级别的额外空间来存储临时变量。

稳定性: 选择排序是一种稳定的排序算法。

3.插入排序

插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素插入到已排序部分的合适位置。

插入排序的步骤如下：

  1. 将待排序数组分为已排序部分和未排序部分。初始时，已排序部分只有一个元素，即数组的第一个元素。
  2. 从未排序部分依次取出一个元素，与已排序部分的元素进行比较。
  3. 将该元素插入到已排序部分的合适位置，使得已排序部分仍然保持有序。
  4. 重复步骤2和步骤3，直到遍历完整个数组，排序完成。

代码实现

public static void insertSort(int[] arr){for (int i = 1; i < arr.length; i++) {// 当前要插入的元素int cur = arr[i];int j;for (j = i-1; j >=0; j--) {if(cur >= arr[j]){break;}else{arr[j+1] = arr[j];}}arr[j+1] = cur;}
}

时间复杂度: 选择排序的时间复杂度是O(n^2)，其中n是待排序数组的长度。在最坏情况下，即待排序数组是逆序的情况下，需要进行n(n-1)/2次比较和n-1次交换操作。

空间复杂度: 选择排序的空间复杂度是O(1)，因为它只需要使用常数级别的额外空间来存储临时变量。

稳定性: 选择排序是不稳定的排序算法。

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高(应用场景为接近有序的一组数组内进行排序)

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

4.希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组， 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达 =1时，所有记录在统一组内排好序。

public static void shellSort(int[] arr){// 分组for (int gap = arr.length/2; gap >= 1; gap = gap/2) {// 遍历每一个分组for (int i = gap; i < arr.length; i++) {int cur = arr[i];int j;for ( j = i - gap; j >=0 ; j-=gap) {if(arr[j] > cur){arr[j+gap] = arr[j];}else{break;}}arr[j+gap] = cur;}}
}

 

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定

4. 稳定性：不稳定

5.快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

 快速排序的基本步骤如下：

  1. 选择一个基准元素（pivot），一般选择数组的第一个元素。
  2. 将数组分成两部分，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素。这个过程称为分区（partition）。
  3. 对左右两部分分别进行快速排序，递归地调用上述步骤。
  4. 合并左右两部分，得到最终的排序结果。

代码实现

public static void quickSort(int[] arr){quick(arr,0,arr.length-1);
}
public static void quick(int[] arr,int left,int right){if(left >= right){return;}int pivot = partition(arr,left,right);// 向左递归quick(arr,left,pivot-1);// 向右递归quick(arr,pivot+1,right);
}// 分区 返回基准下标 方便下一次进行递归
// 1. Hoare版
private static int partition(int[] arr,int left,int right){int pivot = arr[left];int i = left;int j = right;while (left < right) {while (left < right && arr[right] >= pivot) {right--;}while (left < right && arr[left] <= pivot) {left++;}swap(arr, left, right);}
// 将基准更新为相遇点swap(arr, left, i);return left;
}

// 2.挖坑法

private static int partition2(int[] arr, int left, int right) {int key = arr[left];while(left < right){while(left < right && arr[right] >= key){right--;}arr[left] = arr[right];while(left < right && arr[left] <= key){left++;}arr[right] = arr[left];}arr[left] = key;return left;
}

hoare法

挖坑法

快速排序总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

 3. 空间复杂度：O(logN)

4. 稳定性：不稳定

6.归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使 子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

 

归并排序的具体步骤如下：

  1. 将待排序序列不断地二分，直到每个子序列只有一个元素。
  2. 逐层合并相邻的子序列，直到合并成一个完整的有序序列。

代码实现

public static void mergeSort(int[] arr){mergeSeparate(arr,0,arr.length-1);
}
// 归
public static void mergeSeparate(int[] arr,int left,int right){if(left >= right){return;}int mid = (left+right)/2;mergeSeparate(arr,left,mid);mergeSeparate(arr,mid+1,right);merge(arr,left,right,mid);
}
// 并
public static void merge(int[] arr,int left ,int right,int mid){int[] array = new int[right-left+1];int i = left;int j = mid+1;int k = 0;while(i<=mid && j<=right){while(i<=mid && arr[i] <= arr[j]){array[k++] = arr[i++];}while(j<=right && arr[j] <= arr[i]){array[k++] = arr[j++];}}while(i <= mid){array[k++] = arr[i++];}while(j <= mid){array[k++] = arr[j++];}// 将新数组中的元素拷贝到老数组中for (int l = 0; l < array.length; l++) {arr[left++] = array[l];}
}

总结

这篇博客就到这了,大家多理解一下就ok

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

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

相关文章

vue event bus 事件总线

vue event bus 事件总线

vue event bus 事件总线 创建 工程&#xff1a; H:\java_work\java_springboot\vue_study ctrl按住不放 右键 悬着 powershell H:\java_work\java_springboot\js_study\Vue2_3入门到实战-配套资料\01-随堂代码素材\day04\准备代码\08-事件总线-扩展 vue --version vue crea…
阅读更多...
【C语言】文件操作（一）

【C语言】文件操作（一）

前言 本篇博客讲解对文件的操作&#xff0c;包括打开&#xff0c;关闭操作。在下篇博客将讲解文件的读写。 文章目录 一、 什么是文件&#xff1f;1.1 用于存储数据1.2 文件类型1.3 文件名1.4 二进制文件和文本文件 二、文件的打开和关闭2.1 流和标准流2.2 文件指针2.3文件的打…
阅读更多...
你的周末和你一起失去了价值(打工人篇)

你的周末和你一起失去了价值(打工人篇)

花儿在绽放盛开之前&#xff0c;会在无人的清晨吸收甘露&#xff0c;然后赶上第一趟的朝阳&#xff0c;才换来路人赞许 一言指南北 选择你的职业&#xff0c;确认你的方向&#xff0c;没有方向&#xff0c;就无法体验时间感 如果你是打工人&#xff0c;那么请接着往下看 如果是…
阅读更多...
React项目中如何实现一个简单的锚点目录定位

React项目中如何实现一个简单的锚点目录定位

小册 这是我整理的学习资料&#xff0c;非常系统和完善&#xff0c;欢迎一起学习 现代JavaScript高级小册 深入浅出Dart 现代TypeScript高级小册 linwu的算法笔记&#x1f4d2; 前言 锚点目录定位功能在长页面和文档类网站中非常常见,它可以让用户快速定位到页面中的某个…
阅读更多...
GLTF编辑器也可以转换GLB模型

GLTF编辑器也可以转换GLB模型

1、GLB模型介绍 GLB&#xff08;GLTF Binary&#xff09;是一种用于表示三维模型和场景的文件格式。GLTF是"GL Transmission Format"的缩写&#xff0c;是一种开放的、跨平台的标准&#xff0c;旨在在各种3D图形应用程序和引擎之间进行交换和共享。 GLB文件是GLTF文件…
阅读更多...
Java之线程的详细解析一

Java之线程的详细解析一

实现多线程 简单了解多线程【理解】 是指从软件或者硬件上实现多个线程并发执行的技术。 具有多线程能力的计算机因有硬件支持而能够在同一时间执行多个线程&#xff0c;提升性能。 并发和并行【理解】 并行&#xff1a;在同一时刻&#xff0c;有多个指令在多个CPU上同时执行…
阅读更多...
【excel密码】如何给excel设置带有密码的只读模式

【excel密码】如何给excel设置带有密码的只读模式

大家提起只读模式&#xff0c;应该都不会联想到密码&#xff0c;想起excel密码可能会想到打开密码或者工作表保护。今天给大家分享如何设置带有密码的只读模式。 打开excel文件&#xff0c;将文件进行【另存为】设置&#xff0c;然后停留在保存路径的界面中&#xff0c;我们点…
阅读更多...
SourceTree 账号或者密码输入错误 Incorrect username or password ( access token )解决办法

SourceTree 账号或者密码输入错误 Incorrect username or password ( access token )解决办法

修改来修改去一直解决不了&#xff0c;那就试试查看一下源文件记录的账号密码吧&#xff01;
阅读更多...
谷器数据参加世界制造业大会及数字化转型高峰论坛

谷器数据参加世界制造业大会及数字化转型高峰论坛

9月20日至24日&#xff0c;由工业和信息化部、科技部、商务部、国务院国资委、中国工程院、安徽省人民政府等单位组织共同主办的2023世界制造业大会在合肥市滨湖国际会展中心盛大举行。谷器数据受邀出席&#xff0c;并同期参加”数字化转型高峰论坛”&#xff0c;与国家工信部相…
阅读更多...
自定义热加载：如何不停机实现核心代码更新

自定义热加载：如何不停机实现核心代码更新

文章目录 1. 常见的几种实现代码热更新的几种方式对于开发环境我们可以使用部署环境1. 使用 Arthas 的 redefine 命令来加载新的 class 文件2. 利用 URLClassLoader 动态加载3. 通过Java的Instrumentation API 也是可以实现的 2. 实现1. ClassScanner扫描目录和加载类2. 定时任…
阅读更多...
十六，镜面IBL--预滤波环境贴图

十六，镜面IBL--预滤波环境贴图

又到了开心的公式时刻了。 先看看渲染方程 现在关注第二部分&#xff0c;镜面反射。 其中 这里很棘手&#xff0c;与输入wi和输出w0都有关系&#xff0c;所以&#xff0c;再近似 其中第一部分&#xff0c;就是预滤波环境贴图&#xff0c;形式上与前面的辐照度图很相似&#…
阅读更多...
离线环境harbor 搭建及使用

离线环境harbor 搭建及使用

一 摘要 本文主要介绍harbor 的安装及使用。 二 环境信息及部署图 2.1 环境信息 名称版本备注操作系统centos7.9容器docker 23.0.1harbor2.7代理nginx待补充 2.2 架构图 说明&#xff1a; 1.harbor 核心服务里有个nginx &#xff0c;也可以用该nginx 做代理 2.proxy-ngin…
阅读更多...
ISP图像信号处理——平场校正介绍以及C++实现

ISP图像信号处理——平场校正介绍以及C++实现

参考文章1&#xff1a;http://t.csdn.cn/h8TBy 参考文章2&#xff1a;http://t.csdn.cn/6nmsT 参考网址3&#xff1a;opencv平场定标 - CSDN文库 平场校正一般先用FPN(Fixed Pattern Noise)固定图像噪声校正,即暗场校正&#xff1b;再用PRNU(Photo Response Non Uniformity)…
阅读更多...
自动化测试-友好的第三方库

自动化测试-友好的第三方库

目录 mock furl coverage deepdiff pandas jsonpath 自动化测试脚本开发中&#xff0c;总是会遇到各种数据处理&#xff0c;例如MOCK、URL处理、JSON数据处理、结果断言等&#xff0c;也会遇到所采用的测试框架不能满足当前需求&#xff0c;这些问题都需要我们自己动手解…
阅读更多...
IP地址定位的特点

IP地址定位的特点

IP地址定位是一种广泛应用于网络领域的技术&#xff0c;它允许我们确定特定设备或用户在互联网上的位置。这项技术在很多方面都具有重要的特点&#xff0c;本文将深入探讨这些特点。 1.全球性覆盖&#xff1a; IP地址定位IP66_ip归属地在线查询_免费ip查询_ip精准定位平台具有全…
阅读更多...
通信协议：Uart的Verilog实现（下）

通信协议：Uart的Verilog实现（下）

4、UART接收器 UART接收器负责接收串行比特流&#xff0c;去除起始位和停止位&#xff0c;并以并行格式将数据保存到与主机数据总线相连的寄存器里。接收器无法获得发送时钟&#xff0c;因此尽管数据以标准比特率到达&#xff0c;但数据未必与接收主机内的时钟同步。同步问题可…
阅读更多...
LaTex模板免费下载网站

LaTex模板免费下载网站

LaTex模板免费下载网站 在进行文档排版时候&#xff0c;有时需要对不同类型文章的格式进行编辑&#xff0c;本博文推荐一个免费下载LaTex模板的网站。 一、网站地址 链接: LaTex模板网址&#xff1a;http://www.latextemplates.com/ 二、模板类型 模板类型如图2和图3所示。…
阅读更多...
Ctfshow web入门 phpCVE篇 web311-web315 详细题解 全

Ctfshow web入门 phpCVE篇 web311-web315 详细题解 全

CTFshow phpCVE web311 CVE-2019-11043 PHP远程代码执行漏洞复现&#xff08;CVE-2019-11043&#xff09;【反弹shell成功】-腾讯云开发者社区-腾讯云 (tencent.com) 漏洞描述 CVE-2019-11043 是一个远程代码执行漏洞&#xff0c;使用某些特定配置的 Nginx PHP-FPM 的服务…
阅读更多...
程序开发常用在线工具汇总

程序开发常用在线工具汇总

菜鸟工具# https://c.runoob.com/ 编码# ASCII码# https://www.habaijian.com/ 在线转换# https://www.107000.com/T-Ascii/http://www.ab126.com/goju/1711.html Base64# 在线转换# https://www.qqxiuzi.cn/bianma/base64.htmhttp://www.mxcz.net/tools/Unicode.aspx …
阅读更多...
【Html】用CSS定义咖啡 - 咖啡配料展示

【Html】用CSS定义咖啡 - 咖啡配料展示

显示效果 代码 index.html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>CodePen - For The Love Of Coffee</title><link rel"stylesheet" href"./style.css">&l…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023