常见算法题目5 -常见的排序算法

article/2025/7/2 22:48:50

常见算法题目5 -常见的排序算法

本文介绍常见的排序算法的思路及代码实现(都是按照从小到大排列)，包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

1.冒泡排序

  • 思路：重复遍历数组，依次比较相邻元素，若顺序错误则交换，直至没有交换发生。每次外层循环后，最大的都会移动到数组末尾，就像冒水泡一样(水泡由水底往上升起的过程中原来越大)，故称为冒泡排序。
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 实现代码：
    /*** 常见的排序算法(从小到大排列) 之 冒泡排序* @param arr*/public static void bubbleSort1(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {// 比较相邻元素 前>后 则交换位置if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}// 为了直观的显现冒泡的过程，可以在这里打下输出System.out.println("冒泡排序，第" + (i + 1) + "轮排序后，：" + Arrays.toString(arr));}}
  • 测试：
public class SortTest {public static void main(String[] args) {int[] arr1 = {7, 6, 5, 4, 3, 2, 1};System.out.println("原数组：" + Arrays.toString(arr1));bubbleSort1(arr1);System.out.println("冒泡排序后：" + Arrays.toString(arr1));}

在这里插入图片描述

2. 选择排序

  • 思路：每次从未排序部分选择最小元素，与未排序部分的第一个元素交换。每次外层循环结束后，最小的元素都会一步步移动到数据的前面。
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定。与冒泡排序相比都涉及数据位置交换，但涉及相同数值数据的交换，会改变相同数值的相对位置，因此不稳定。但冒泡排序在进行等值判断后不会进行位置交换，故稳定。
  • 实现代码：
    /*** 常见的排序算法(从小到大排列) 之 选择排序* @param arr*/public static void testSelectionSort2(int[] arr) {// 遍历比较for (int i = 0; i < arr.length - 1; i++) {// 存储最小值下标索引int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换位置if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}// 为了直观的显现选择排序的过程，可以在这里打下输出System.out.println("选择排序，第" + (i + 1) + "轮排序后，：" + Arrays.toString(arr));}}
  • 测试：
public class SortTest {public static void main(String[] args) {int[] arr2 = {7, 6, 5, 4, 3, 2, 1};System.out.println("原数组：" + Arrays.toString(arr2));testSelectionSort2(arr2);System.out.println("选择排序后：" + Arrays.toString(arr2));}

在这里插入图片描述

3. 插入排序

  • 思路：将数组分为已排序部分和未排序部分，已排序部分为已排序的元素，未排序部分为未排序的元素。将未排序部分中的每一个元素逐个插入到已排序部分的正确位置。
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 实现代码：
    /*** 常见的排序算法(从小到大排列) 之 插入排序* @param arr*/public static void insertSort3(int[] arr) {// 循环判断for (int i = 1; i < arr.length; i++) {// 存储当前元素int temp = arr[i];// 循环判断，找到插入的位置int j = i - 1;// 已排序部分的元素，找到插入的位置while (j >= 0 && arr[j] > temp) {arr[j + 1] = arr[j];j--;}// 当前循环下标位置数据赋值arr[j + 1] = temp;// 为了直观的显现插入排序的过程，可以在这里打下输出System.out.println("插入排序，第" + i + "轮排序后，：" + Arrays.toString(arr));}}
  • 测试：
public class SortTest {public static void main(String[] args) {int[] arr3 = {7, 6, 5, 4, 3, 2, 1};System.out.println("原数组：" + Arrays.toString(arr3));insertSort3(arr3);System.out.println("插入排序后：" + Arrays.toString(arr3));}

在这里插入图片描述

4. 快速排序

  • 思路：将数组分为已排序部分和未排序部分，已排序部分为已排序的元素，未排序部分为未排序的元素。将未排序部分中的每一个元素逐个插入到已排序部分的正确位置。
    ①选择基准元素：一般选择第一个或最后一个元素作为基准元素。
    ②数组分区：比基准元素小的在基准元素的左边，比基准元素大的在基准元素的右边
    ③递归：递归对基准元素左边和右边的部分进行快速排序
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(logn)
  • 稳定性：不稳定
  • 实现代码：
    /*** 常见的排序算法 之 快速排序(从小到大排列) * @param arr*/public static void quickSort4(int[] arr, int left, int right) {if (left < right) {int baseIndex = partition(arr, left, right);// 递归对基准元素左边和右边的进行快速排序quickSort4(arr, left, baseIndex - 1);quickSort4(arr, baseIndex + 1, right);}}/*** 获取基准原始位置* @param arr* @param left* @param right* @return*/private static int partition(int[] arr, int left, int right) {// 选择最后一个元素为基准元素int baseValue = arr[right];int i = left - 1;for (int j = left; j < right; j++) {// 当前元素小于基准元素if (arr[j] < baseValue) {// 交换位置i++;// 交换当前元素与较小元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}System.out.println("快速排序，排序中间过程结果：" + Arrays.toString(arr));}// 交换基准元素与较小元素索引下一个元素int temp = arr[i + 1];arr[i + 1] = arr[right];arr[right] = temp;System.out.println("快速排序，基准元素交换位置后结果：" + Arrays.toString(arr));// 返回基准元素索引return i + 1;}
  • 测试：
public class SortTest {public static void main(String[] args) {int[] arr4 = {5, 6, 2, 3, 1, 7, 4};System.out.println("原数组：" + Arrays.toString(arr4));quickSort4(arr4, 0, arr4.length - 1);System.out.println("快速排序后：" + Arrays.toString(arr4));}

在这里插入图片描述

5.归并排序

  • 思路：归并排序是一种典型的分治算法。
    ①分：将数组分成两半；
    ②治：递归对左右两部分进行排序；
    ③合：将左右两部分有序数组合并为有序数组。
  • 时间复杂度：O(nlog n)
  • 空间复杂度：O(n)
  • 稳定性：稳定
  • 实现代码：
    /*** 常见的排序算法 之 归并排序(从小到大排列) * @param arr*/public static void mergeSort5(int[] arr, int left, int right, int[] temp) {if (arr == null || arr.length < 1) {return;}if (left < right) {// 取中间索引int mid = (right + left) / 2;// 递归排序左半边mergeSort5(arr, left, mid, temp);// 递归排序右半边mergeSort5(arr, mid + 1, right, temp);// 合并左右两个有序数组merge(arr, left, mid, right, temp);}}/*** 合并两个有序数组** @param arr   原数组* @param left  左指针* @param mid   中间索引* @param right 右指针* @param temp  临时数组*/private static void merge(int[] arr, int left, int mid, int right, int[] temp) {// 左子数组起始索引int leftIndex = left;// 右子数组起始索引int rightIndex = mid + 1;//  临时数组索引int tempIndex = 0;// 比较左右两部分的元素，将较小的放入tempwhile (leftIndex <= mid && rightIndex <= right) {if (arr[leftIndex] <= arr[rightIndex]) {temp[tempIndex++] = arr[leftIndex++];} else {temp[tempIndex++] = arr[rightIndex++];}}// 将左边剩余元素填充进temp中while (leftIndex <= mid) {temp[tempIndex++] = arr[leftIndex++];}//  将右边剩余元素填充进temp中while (rightIndex <= right) {temp[tempIndex++] = arr[rightIndex++];}// 将temp中的元素拷贝到arr中tempIndex = 0;while (left <= right) {arr[left++] = temp[tempIndex++];}}
  • 测试：
public class SortTest {public static void main(String[] args) {int[] arr5 = {5, 6, 2, 3, 1, 7, 4};System.out.println("原数组：" + Arrays.toString(arr5));int[] tempArr = new int[arr5.length];mergeSort5(arr5, 0, arr5.length - 1, tempArr);System.out.println("归并排序后：" + Arrays.toString(arr5));}

在这里插入图片描述

6. 堆排序

  • 思路：堆排序(Heap Sort)是一种基于二叉堆数据结构的比较排序算法,排序思路：
    ①构建堆，将无序数组构建成一个最大堆（或者最小堆）
    ②排序，每次取出堆顶元素，并调整堆，将堆顶元素放到已排序的末尾，重复n-1次，即可得到一个有序数组。
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 实现代码：
    /*** 常见的排序算法 之 堆排序(从小到大排列) * @param arr*/public static void heapSort6(int[] arr) {if (arr == null || arr.length < 1) {return;}// 构建最大堆buildMaxHeap(arr);// 逐一交换堆顶元素（最大值）到数组末尾，并调整堆for (int i = arr.length - 1; i > 0; i--) {// 将堆顶元素与末尾元素交换int temp = arr[i];arr[i] = arr[0];arr[0] = temp;// 调整堆，使其重新成为最大堆（堆大小减1）heapAdjust(arr, 0, i);System.out.println("堆排序中间过程：" + Arrays.toString(arr));}}/*** heapAdjust* @param arr*/public static void buildMaxHeap(int[] arr) {// 从最后一个非叶子节点开始，从下至上，从右至左进行堆化for (int i = arr.length / 2 - 1; i >= 0; i--) {// 堆化heapAdjust(arr, i, arr.length);}}/*** 调整堆* @param arr* @param i* @param heapSize*/public static void heapAdjust(int[] arr, int i, int heapSize) {// 初始化最大值为当前节点int largest = i;// 左子节点int left = 2 * i + 1;// 右子节点int right = 2 * i + 2;// 如果左子节点大于当前最大节点if (left < heapSize && arr[left] > arr[largest]) {largest = left;}// 如果右子节点大于当前最大节点if (right < heapSize && arr[right] > arr[largest]) {largest = right;}// 如果最大节点不是当前节点，交换并继续调整if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapAdjust(arr, largest, heapSize);}}
  • 测试：
public class SortTest {public static void main(String[] args) {int[] arr6 = {5, 6, 2, 3, 1, 7, 4};System.out.println("原数组：" + Arrays.toString(arr6));heapSort6(arr6);System.out.println("堆排序后：" + Arrays.toString(arr6));}

在这里插入图片描述

7. 总结

算法平均时间复杂度空间复杂度稳定性适用场景
冒泡排序O(n²)O(1)稳定教学、小数据集
选择排序O(n²)O(1)不稳定简单实现但效率低
插入排序O(n²)O(1)稳定部分有序数组
快速排序O(n log n)O(log n)不稳定通用排序，性能优秀
归并排序O(nlog n)O(n)稳定大数据、需要稳定性
堆排序O(nlog n)O(1)稳定原地排序，无需额外空间

http://www.hkcw.cn/article/wTjyDJLHEY.shtml

相关文章

3.需求分析与测试用例设计方法

3.需求分析与测试用例设计方法

设计方法 测试点 定义: 测试时需要考虑的可测试方面&#xff0c;不同公司可能称为"检查点"或其它名称特点: 是需求分析的最后一个环节&#xff0c;用于解决"测哪里"和"怎么测"的问题举例说明: 如同打架时的各种招数&#xff0c;如直接约架、设…
阅读更多...
【PCB设计】STM32开发板——电源设计

【PCB设计】STM32开发板——电源设计

电源稳压器&#xff08;Power Regulator&#xff09;是一种在电源电压或者负载电流发生变化的时候&#xff0c;依然能够提供稳定输出电压的元件。 一、关于LDO电路 1.引入 小灯泡实验 2.LDO原理 3.LDO芯片结构框图 PNP型三极管&#xff0c;Ube上升&#xff0c;截至&#xff…
阅读更多...
BUUCTF[HCTF 2018]WarmUp 1题解

BUUCTF[HCTF 2018]WarmUp 1题解

BUUCTF[HCTF 2018]WarmUp 1题解 分析解题过程代码审计主体函数CHECK函数&#xff1a; 构造payload 总结 分析 启动靶机&#xff0c;进入网址&#xff0c;是一张滑稽的表情包&#xff1a; 程序化F12查看源码&#xff1a; 发现注释内容&#xff0c;访问 url:/source.php得到…
阅读更多...
如何使用DAXStudio将PowerBI与Excel连接

如何使用DAXStudio将PowerBI与Excel连接

如何使用DAXStudio将PowerBI与Excel连接 之前分享过一篇自动化文章&#xff1a;PowerBI链接EXCEL实现自动化报表&#xff0c;使用一个EXCEL宏工作薄将PowerBI与EXCEL连接起来&#xff0c;今天分享另一个方法&#xff1a;使用DAX Studio将PowerBI与EXCEL连接。 下面是使用DAX S…
阅读更多...
neo4j 5.19.0两种基于向量进行相似度查询的方式

neo4j 5.19.0两种基于向量进行相似度查询的方式

介绍 主要讲的是两种相似度查询 一种是创建向量索引&#xff0c;然后直接从索引的所有数据中进行相似度搜索&#xff0c;这种不支持基于自己查询的结果中进行相似度匹配另一种是自己调用向量方法生产相似度进行相似度搜索&#xff0c;这种可以基于自己的查询结果中进行相似度…
阅读更多...
中科院报道铁电液晶：从实验室突破到多场景应用展望

中科院报道铁电液晶：从实验室突破到多场景应用展望

2020年的时候&#xff0c;相信很多关注科技前沿的朋友都注意到&#xff0c;中国科学院一篇报道聚焦一项有望改写显示产业格局的新技术 —— 铁电液晶&#xff08;FeLC&#xff09;。这项被业内称为 "下一代显示核心材料" 的研究&#xff0c;究竟取得了哪些实质性进展…
阅读更多...
任务26：绘制1-12月各省份平均气温和预测可视化图形（折线

任务26：绘制1-12月各省份平均气温和预测可视化图形（折线

任务描述 知识点&#xff1a; DjangoECharts 重 点&#xff1a; DjangoECharts折线图 内 容&#xff1a; 绘制列表框&#xff0c;能够切换不同的省份根据ECharts官方示例&#xff0c;绘制ECharts折线图根据ECharts配置项手册&#xff0c;修改ECharts图形配置 任务指导…
阅读更多...
【Redis】Set 集合

【Redis】Set 集合

文章目录 常用命令saddsmemberssismemberscardspopsmovesrem 集合间操作sinter && sinterstoresunion && sunionstoresdiff && sdiffstore 内部编码应用场景 集合类型也是用于存储多个字符串类型的数据结构 集合中元素之间是 1. 无序的 2. 不允许重复的…
阅读更多...
python打卡训练营打卡记录day43

python打卡训练营打卡记录day43

复习日 作业&#xff1a; kaggle找到一个图像数据集&#xff0c;用cnn网络进行训练并且用grad-cam做可视化 进阶&#xff1a;并拆分成多个文件 数据集来源&#xff1a;Flowers Recognition 选择该数据集原因&#xff1a; 中等规模&#xff1a;4242张图片 - 训练快速但足够展示效…
阅读更多...
向量空间的练习题目

向量空间的练习题目

1.考虑 中的向量x1 和x2 求每一向量的长度 令x3x1x2,求x3的长度&#xff0c;它的长度与x1和x2的和有什么关系&#xff1f; 2.重复练习1&#xff0c;取向量 3.令C为复数集合&#xff0c;定义C上的加法为 (abi)(cdi)(ac)(bd)i 并定义标量乘法为对所有实数a (abi) a bi 证明&…
阅读更多...
Android Studio历史版本下载地址汇总

Android Studio历史版本下载地址汇总

Android Studio 下载文件归档 | Android Developers本页提供了各个 Android Studio 版本的下载归档文件。https://developer.android.google.cn/studio/archive?hlzh-cn
阅读更多...
SpringBoot-Thymeleaf

SpringBoot-Thymeleaf

大佬写的真好&#xff1a;Thymeleaf一篇就够了-阿里云开发者社区
阅读更多...
序列搜索策略

序列搜索策略

序列搜索策略 贪心搜索&#xff08;greedy search&#xff09; 在大语言模型中&#xff0c; 对于输出序列的每一时间步t′&#xff0c; 我们都将基于贪心搜索从Y中找到具有最高条件概率的词元&#xff0c;即&#xff1a; y t ′ argmax ⁡ y ∈ Y P ( y ∣ y 1 , … , y t ′…
阅读更多...
MG影视登录解锁永久VIP会员 v8.0 支持手机电视TV版影视直播软件

MG影视登录解锁永久VIP会员 v8.0 支持手机电视TV版影视直播软件

MG影视登录解锁永久VIP会员 v8.0 支持手机电视TV版影视直播软件 MG影视App电视版是一款资源丰富、免费便捷、且专为大屏优化的影视聚合应用&#xff0c;聚合海量资源&#xff0c;畅享电视直播&#xff0c;是您电视盒子和…
阅读更多...
【浏览器】无法连接到互联网解决方法

【浏览器】无法连接到互联网解决方法

Mac网络连接一切正常&#xff08;手机连接互联网能正常使用&#xff09; 但是涉及到网络界面就提示“无法连接到互联网”&#xff1a; 解决办法&#xff1a; 点击左上角→系统设置→网络→→位置→编辑位置→→新增一个即可 正常了!!
阅读更多...
【C语言预处理详解(下)】--#和##运算符，命名约定，命令行定义 ，#undef，条件编译，头文件的包含，嵌套文件包含，其他预处理指令

【C语言预处理详解(下)】--#和##运算符，命名约定，命令行定义 ，#undef，条件编译，头文件的包含，嵌套文件包含，其他预处理指令

目录 五.#和##运算符 5.1--#运算符 5.2--##运算符 六.命名约定&#xff0c;#undef&#xff0c;命令行定义 6.1--命名约定 6.2--#undef 6.3--命名行定义 七.条件编译 常见的条件编译指令&#xff1a; 1.普通的条件编译&#xff1a; 2.多个分支的条件编译(可以利用条…
阅读更多...
数据资产评估进阶：精读资产评估专家指引第9号——数据资产评估指导【附全文阅读】

数据资产评估进阶：精读资产评估专家指引第9号——数据资产评估指导【附全文阅读】

这篇文档是有关数据资产评估的专业报告&#xff0c;以下是文档中需要关注的重点内容&#xff1a; 1. 评估对象&#xff1a;文档中提到了数据资产评估的评估对象&#xff0c;即被评估数据资产。需要关注被评估数据资产的信息属性、法律属性、价值属性等&#xff0c;以及其特征对…
阅读更多...
btstack协议栈---ESP32底层逻辑分析

btstack协议栈---ESP32底层逻辑分析

目录 循环体 循环体中，怎么读取、处理数据 packet_handler 上面各层如何处理数据 谁触发了数据的传输？ 硬件相关的数据有4类 循环体 BTStack针对不同的运行环境，抽象出了对应的btstack_run_loop结构体，共成员为： 比如其中的execute成员很重要，它是一个循环，在循…
阅读更多...
碳中和新路径：铁电液晶屏如何破解高性能与节能矛盾？

碳中和新路径：铁电液晶屏如何破解高性能与节能矛盾？

一、显示技术困局&#xff1a;当 “高刷” 遭遇 “高耗” 在元宇宙、电竞产业蓬勃发展的当下&#xff0c;显示设备的刷新率与能耗成为行业痛点。传统液晶受 “边缘场效应” 制约&#xff0c;刷新率长期停滞在 300Hz 以下&#xff0c;动态画面拖影问题显著&#xff1b;同时&…
阅读更多...
408考研逐题详解：2009年第27题

408考研逐题详解：2009年第27题

2009年第27题 一个分段存储管理系统中&#xff0c;地址长度为 32 位&#xff0c;其中段号占 8 位&#xff0c;则最大段长是&#xff08; &#xff09; A. 2 8 2^8 28B \qquad B. 2 16 2^{16} 216B \qquad C. 2 24 2^{24} 224B \qquad D. 2 32 2^{32} 232B 解析 本题…
阅读更多...
推荐文章

Copyright @ 2022~2023