十大排序算法

1. 冒泡排序(Bubble Sort)

        冒泡排序重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来,直到整个数列有序。

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;// 外层循环控制排序的轮数for (int i = 0; i < n - 1; i++) {// 标记是否有元素交换,若没有则提前结束排序boolean swapped = false;// 内层循环比较相邻元素并交换for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j + 1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 如果没有发生交换,说明数组已经有序,提前退出if (!swapped) {break;}}}
}

2. 选择排序(Selection Sort)

        选择排序每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾,直到全部待排序的数据元素排完。

public class SelectionSort {public static void selectionSort(int[] arr) {int n = arr.length;// 外层循环控制当前要确定位置的元素索引for (int i = 0; i < n - 1; i++) {int minIndex = i;// 内层循环找到剩余元素中的最小值索引for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换当前元素和最小值元素if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}
}

3. 插入排序(Insertion Sort)

        插入排序通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

public class InsertionSort {public static void insertionSort(int[] arr) {int n = arr.length;// 从第二个元素开始,将其插入到前面已排序的序列中for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 将大于 key 的元素后移while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 插入 keyarr[j + 1] = key;}}
}

4. 希尔排序(Shell Sort)

        希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

public class ShellSort {public static void shellSort(int[] arr) {int n = arr.length;// 初始增量为数组长度的一半for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个分组进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}// 插入元素arr[j] = temp;}}}
}

5. 归并排序(Merge Sort)

        归并排序采用分治法,将已有序的子序列合并,得到完全有序的序列。

public class MergeSort {public static void mergeSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int[] temp = new int[arr.length];mergeSort(arr, 0, arr.length - 1, temp);}private static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2;// 递归排序左半部分mergeSort(arr, left, mid, temp);// 递归排序右半部分mergeSort(arr, mid + 1, right, temp);// 合并左右两部分merge(arr, left, mid, right, temp);}}private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;int j = mid + 1;int t = 0;// 比较左右两部分元素,将较小的放入临时数组while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[t++] = arr[i++];} else {temp[t++] = arr[j++];}}// 将左半部分剩余元素放入临时数组while (i <= mid) {temp[t++] = arr[i++];}// 将右半部分剩余元素放入临时数组while (j <= right) {temp[t++] = arr[j++];}t = 0;// 将临时数组元素复制回原数组while (left <= right) {arr[left++] = temp[t++];}}
}

6. 快速排序(Quick Sort)

        快速排序使用分治法,通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序。

public class QuickSort {public static void quickSort(int[] arr) {if (arr == null || arr.length < 2) {return;}quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int left, int right) {if (left < right) {int partitionIndex = partition(arr, left, right);// 递归排序左半部分quickSort(arr, left, partitionIndex - 1);// 递归排序右半部分quickSort(arr, partitionIndex + 1, right);}}private static int partition(int[] arr, int left, int right) {int pivot = arr[right];int i = left - 1;// 将小于 pivot 的元素交换到左边for (int j = left; j < right; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将 pivot 放到正确位置int temp = arr[i + 1];arr[i + 1] = arr[right];arr[right] = temp;return i + 1;}
}

7. 堆排序(Heap Sort)

        堆排序利用堆这种数据结构,将数组构建成最大堆,然后依次将堆顶元素与最后一个元素交换,并调整堆,直到整个数组有序。

public class HeapSort {public static void heapSort(int[] arr) {int n = arr.length;// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 一个个交换元素for (int i = n - 1; i > 0; i--) {// 将堆顶元素与当前未排序部分的最后一个元素交换int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整堆heapify(arr, i, 0);}}private static void heapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;// 找到左子节点、右子节点和根节点中的最大值if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根节点,则交换并继续调整if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}}
}

8. 计数排序(Counting Sort)

        计数排序是一种非比较排序算法,它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。

public class CountingSort {public static void countingSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int max = arr[0];int min = arr[0];// 找出数组中的最大值和最小值for (int num : arr) {if (num > max) {max = num;}if (num < min) {min = num;}}int range = max - min + 1;int[] count = new int[range];// 统计每个元素出现的次数for (int num : arr) {count[num - min]++;}int index = 0;// 将统计结果放回原数组for (int i = 0; i < range; i++) {while (count[i] > 0) {arr[index++] = i + min;count[i]--;}}}
}

9. 桶排序(Bucket Sort)

        桶排序将数组分到有限数量的桶子里,每个桶子再个别排序,最后将所有桶中的元素合并。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class BucketSort {public static void bucketSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int min = arr[0];int max = arr[0];// 找出数组中的最大值和最小值for (int num : arr) {if (num < min) {min = num;}if (num > max) {max = num;}}int bucketCount = (max - min) / arr.length + 1;List<List<Integer>> buckets = new ArrayList<>();// 初始化桶for (int i = 0; i < bucketCount; i++) {buckets.add(new ArrayList<>());}// 将元素放入对应的桶中for (int num : arr) {int bucketIndex = (num - min) / arr.length;buckets.get(bucketIndex).add(num);}int index = 0;// 对每个桶进行排序并合并结果for (List<Integer> bucket : buckets) {Collections.sort(bucket);for (int num : bucket) {arr[index++] = num;}}}
}

10. 基数排序(Radix Sort)

        排序是一种非比较型整数排序算法,它按每个位数分别比较,将整数按位数切割成不同的数字,然后进行排序。

public class RadixSort {public static void radixSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int max = arr[0];// 找出数组中的最大值for (int num : arr) {if (num > max) {max = num;}}// 对每一位进行计数排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortForRadix(arr, exp);}}private static void countingSortForRadix(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10];// 统计每个位上数字的出现次数for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}// 计算累积次数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 从后往前将元素放入输出数组for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 将输出数组复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}}
}

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

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

相关文章

stm32 L432KC(mbed)入门第一课

目录 一. 前言 二. 专栏意义 三. MS入门第一课 一. 前言 新的一年MS课程又开始了&#xff0c;同时也到了该专栏的第三个年头。在前两年中&#xff0c;该专栏帮助了很多第一次接触单片机的同学。其中&#xff0c;有的同学订阅专栏是为了更好的完成并且通过MS这门课程&#xf…

【Unity网络同步框架 - Nakama研究(二)】

Unity网络同步框架 - Nakama研究(二) 虽说官方文档和网站以及论坛建立的不错&#xff0c;而且还有中文翻译且质量也不错&#xff0c;但是总会遇到一些词不达意&#xff0c;说了但是依旧没懂的部分&#xff0c;甚至问AI也问不出什么东西&#xff0c;所以需要有一些比较明显的博客…

【Linux系统编程】信号

目录 1、信号1.1、什么是信号1.2、进程对信号的处理1.3、信号的生命周期1.4、信号处理流程1.5、信号的发送 2、kill()、raise()函数 发送信号3、alarm函数 闹钟信号4、pause函数 挂起信号、暂停5、singal 函数 捕获信号5.1、为什么返回值是上一次的处理方式5.2、练习 6、sigact…

git使用命令总结

文章目录 Git 复制创建提交步骤Git 全局设置:创建 git 仓库:已有仓库? 遇到问题解决办法&#xff1a;问题一先git pull一下&#xff0c;具体流程为以下几步&#xff1a; 详细步骤 Git 复制 git clone -b RobotModelSetting/develop https://gitlab.123/PROJECT/123.git创建提…

解锁 AI 核心:神经网络与机器学习知名算法全解析

引言​ 在人工智能蓬勃发展的当下&#xff0c;神经网络与机器学习算法作为核心驱动力&#xff0c;广泛应用于各个领域。了解这些知名算法&#xff0c;能让我们更好地把握 AI 技术的精髓。接下来&#xff0c;一同深入探寻。​ 机器学习知名算法​ 线性回归&#xff08;Linear…

基于SpringBoot + Vue 的房屋租赁系统

基于springboot的房屋租赁管理系统-带万字文档 SpringBootVue房屋租赁管理系统 送文档 本项目有前台和后台两部分、多角色模块、不同角色权限不一样 共分三种角色&#xff1a;用户、管理员、房东 管理员&#xff1a;个人中心、房屋类型管理、房屋信息管理、预约看房管理、合…

30天学习Java第六天——Object类

Object类 java.lang.Object时所有类的超类。Java中所有类都实现了这个类中的方法。 toString方法 将Java对象转换成字符串的表示形式。 public String toString() {return getClass().getName() "" Integer.toHexString(hashCode()); }默认实现是&#xff1a;完…

DeepSeek在金融行业应用

引言 随着人工智能技术的快速发展&#xff0c;DeepSeek作为一款国产大模型&#xff0c;凭借其强大的语义理解、逻辑推理和多模态处理能力&#xff0c;在金融行业迅速崭露头角。其低成本、高效率和开源特性使其成为金融机构智能化转型的重要工具。本文旨在分析DeepSeek在金融行业…

【Unity】 HTFramework框架(六十二)Agent编辑器通用智能体(AI Agent)

更新日期&#xff1a;2025年3月14日。 Github源码&#xff1a;[点我获取源码] Gitee源码&#xff1a;[点我获取源码] 索引 编辑器通用智能体AIAgent类Friday&#xff08;星期五&#xff09;启用智能体设置智能体类型开放智能体权限智能体交互资源优化批处理运行代码联网搜索休闲…

以太坊AI代理与PoS升级点燃3月市场热情,2025年能否再创新高?

币热网深度报道&#xff1a;以太坊AI代理与PoS升级引爆3月热潮&#xff0c;2025年能否再攀历史新高&#xff1f; 原文来源&#xff1a;币热网 - 区块链信息资讯平台 以太坊升级&#xff0c;市场热情高涨 近期&#xff0c;以太坊市场犹如被一股神秘力量点燃&#xff0c;掀起了…

【赵渝强老师】达梦数据库的目录结构

达梦数据库安装成功后&#xff0c;通过使用Linux的tree命令可以非常方便地查看DM 8的目录结构。 tree -L 1 -d /home/dmdba/dmdbms#输出的信息如下&#xff1a; /home/dmdba/dmdbms ├── bin 存放DM数据库的可执行文件&#xff0c;例如disql命令等。 ├── bin2 ├── d…

2025探索短剧行业新可能报告40+份汇总解读|附PDF下载

原文链接&#xff1a;https://tecdat.cn/?p41043 近年来&#xff0c;短剧以其紧凑的剧情、碎片化的观看体验&#xff0c;迅速吸引了大量用户。百度作为互联网巨头&#xff0c;在短剧领域积极布局。从早期建立行业专属模型冷启动&#xff0c;到如今构建完整的商业生态&#xf…

基于java(springboot+mybatis)汽车信息管理系统设计和实现以及文档

基于java(springbootmybatis)汽车信息管理系统设计和实现以及文档 &#x1f345; 作者主页 网顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承接各…

线程同步:多线程编程的核心机制

一、线程同步的意义 线程同步的主要目的是避免数据竞争、保证数据一致性、控制线程执行顺序&#xff0c;并提高程序的性能和稳定性。具体意义包括&#xff1a; ​避免数据竞争&#xff1a;防止多个线程同时修改共享资源&#xff0c;导致不可预测的行为。​保证数据一致性&…

Qt QML实现弹球消砖块小游戏

前言 弹球消砖块游戏想必大家都玩过&#xff0c;很简单的小游戏&#xff0c;通过移动挡板反弹下落的小球&#xff0c;然后撞击砖块将其消除。本文使用QML来简单实现这个小游戏。 效果图&#xff1a; 正文 代码目录结构如下&#xff1a; 首先是小球部分&#xff0c;逻辑比较麻…

Android自动化测试工具

细解自动化测试工具 Airtest-CSDN博客 以下是几种常见的Android应用自动化测试工具&#xff1a; Appium&#xff1a;支持多种编程语言&#xff0c;如Java、Python、Ruby、JavaScript等。可以用于Web应用程序和原生应用程序的自动化测试&#xff0c;并支持iOS和Android平台。E…

消息队列实现 Exactly Once,看 Pulsar 是怎样实现的。

大家好 &#xff0c;我是君哥。 在使用消息队列时&#xff0c;我们希望消息能够精准推送&#xff08;Exactly Once&#xff09;&#xff0c;不会丢失、也不会重复。Exactly Once 其实是很难实现的&#xff0c;Pulsar 这款消息中间件使用事务消息实现了 Exactly Once&#xff0…

Audacity的安装和使用

安装 下载地址&#xff1a;官方网站&#xff1a;Audacity 软件开源免费&#xff0c;但部分功能可能需要额外插件。 一.介绍 Audacity 是一款免费、开源的音频编辑软件&#xff0c;适用于Windows、macOS、Linux等操作系统。它支持多轨编辑、录音、音频效果处理、格式转换等功…

C++:类和对象(从底层编译开始)详解[前篇]

目录 一.inline内联的详细介绍 &#xff08;1&#xff09;为什么在调用内联函数时不需要建立栈帧&#xff1a; &#xff08;2&#xff09;为什么inline声明和定义分离到两个文件会产生链接错误&#xff0c;链接是什么&#xff0c;为什么没有函数地址&#xff1a; 二.类&…

【蓝桥】-动态规划-倒水

目录 一、问题描述​ 二、解题思路 三、完整代码 二维dp 使用滚动数组 一、问题描述 二、解题思路 一个变种的01背包问题&#xff1a; 不选该物品&#xff1a;获得固定收益 e 选择方案1&#xff1a;消耗体积 a&#xff0c;获得价值 b 选择方案2&#xff1a;消耗体积 c&…