Java实现十大排序算法

article/2025/10/13 3:36:23

Java实现十大排序算法

十大排序算法分别为：选择排序、冒泡排序、插入排序、快速排序、归并排序、堆排序、希尔排序、桶排序、计数排序、基数排序。

本篇只是为了方便我在代码中直接复制调用，因此原理和思想解释的并不清楚，想看原理的朋友可以参考这篇文章：Java实现十大排序算法_木梓沐丶的博客-CSDN博客，有原理和图解，写的超好。

十大排序算法的对比

image-20221226231724153

十大排序算法记忆法

《忆排序，面试我最强》 – 马士兵

选泡插， （选择、冒泡、插入）

快归堆希桶计基， （快速、归并、堆、希尔、桶、计数、基数）

恩方恩老恩一三， （选泡插复杂度是n2，快归希是nlogn，希尔是n1.3）

对恩加K恩乘K, （桶计是n+k，基是n*k）

不稳稳稳不稳稳, （选、泡、插、快、归）

不稳不稳稳稳稳! （堆、希、桶、计、基）

1、选择排序（SelectionSort）

思想：每次选择一个当前未排序部分中最小的，放在最前面的位置

代码：

private static void sort (int[] arr){int minPos;for (int i = 0; i < arr.length; i++){minPos = i;for (int j = i+1; j < arr.length; j++){if (arr[j] < arr[minPos]){minPos = j;}           }swap(arr,i,minPos);}
}private static void swap (int[] arr,int i,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

2、冒泡排序（BubbleSort）

思想：依次循环比较相邻两个数的大小，这样每次循环过后最大的那个数就到了数组尾

代码：

private static void sort(int[] arr){for (int end = arr.length-1; end > 0; end--){for (int i = 0; i < end; i++) {if (arr[i] > arr[i+1]){swap(arr,i,i+1);}}}
}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

3、插入排序（InsertSort）

思想：将数组中的数据从第二位开始向前找到合适的位置插入，有点类似向前的冒泡排序

代码：

private static void sort(int[] arr){for (int i = 1; i < arr.length; i++) {int j = i;while (j > 0 && arr[j] < arr[j-1]){swap(arr,j,j-1);j--;}}
}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

4、希尔排序（ShellSort）

思想：改进版的插入排序，首先设置一个间隔，插入排序相同间隔的每组数据，之后缩小间隔，直至间隔缩小为1

代码：

private static void sort(int[] arr){int h = 1;while (h <= arr.length/3){h = h*3 +1;}for (int gap = h; gap > 0; gap = (gap-1)/3 ){for (int i = gap; i < arr.length; i++){int j = i;while (j >= gap && arr[j] < arr[j-gap]){swap(arr,j,j-gap);j -= gap;}}}
}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

5、归并排序（MergeSort）

思想：递归合并两个小的有序数组，先将原数组分成两个小数组，对这两个小数组分别排序使其有序，之后合并这两个小数组，整体来说就是一直拆分源数组为两个数组，给左侧数组排序，给右侧数组排序，合并左右数组。适用于对象排序。

代码：

//数组，左边界下标，右边界下标 (arr,0,arr.length-1)
private static void sort(int[] arr,int left,int right){     if (left == right){return;}int mid = left + (right - left) / 2;sort(arr,left,mid);sort(arr,mid+1,right);merge(arr,left,mid+1,right);
}//数组，第一个数组的起始下标，第二个数组的起始下标，右边界
private static void merge(int[] arr, int left, int right, int rightBound){     int mid = right - 1;int i = left, j = right, k = 0;int[] temp = new int[rightBound - left + 1];while (i <= mid && j <= rightBound){temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];}while (i <= mid){temp[k++] = arr[i++];}while (j <= rightBound){temp[k++] = arr[j++];}//排完序的结果在temp数组里，因此要替换到arr数组中//变量分别为，源数组，源数组的起始位置，目的数组，目的数组的起始位置，要复制的长度System.arraycopy(temp, 0, arr, left, temp.length);
}

6、快速排序（QuickSort）

Java中Arrays.sort()用的是更强大的双轴快排！

思想：常见的实现方式就是首先挑选一个基准点，也称为轴，在轴的左侧找比轴大的，在轴的右侧找比轴小的，找到后进行交换，之后在轴的左侧部分和右侧部分继续执行相同操作。

代码：

//数组，左边界下标，右边界下标 sort(arr,0,arr.length-1)
private static void sort(int[] arr,int left,int right){     if (left >= right){return;}int mid = partition(arr, left, right);sort(arr,left,mid-1);sort(arr,mid+1,right);
}//每次以最右侧的数为轴
private static int partition(int[] arr,int leftBound,int rightBound){int left = leftBound,right = rightBound - 1,pivot = arr[rightBound];while (left <= right){while (left <= right && arr[left] <= pivot){left++;}while (left <= right && arr[right] > pivot){right--;}if (left < right){swap(arr,left,right);}}swap(arr,left,rightBound);return left;
}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

7、计数排序（CountSort）

思想：首先设置一个包含所有范围数据的数组count，count[i]代表i这个数据出现了多少次，最后从起始位置遍历时count[i]等于几，就在数组中追加几个i。计数排序是一种特殊的桶排序，适用于量大但是范围小的数据排序，比如高考成绩排名。

代码：

private static void sort(int[] arr){int k = 0;if (arr == null || arr.length < 2) {return ;}int[] count = new int[101];for (int i = 0; i < arr.length; i++) {count[arr[i]]++;}for (int i = 0; i < count.length; i++) {while (count[i]-- > 0){arr[k++] = i;}}
}

8、基数排序（BaseSort）

思想：从个位开始，循环其中最大的数的位次，每次根据位上的数进行排序。基数排序是一种特殊的桶排序，其中第二次更新count的值后count[m]代表余数<=m的数有多少个。

代码：

public static void sort(int[] arr){if (arr == null || arr.length < 2) {return;}int[] result = new int[arr.length];int[] count = new int[10];int max = Arrays.stream(arr).max().getAsInt();int flag = String.valueOf(max).length();for (int i = 0; i < flag; i++) {int division = (int)Math.pow(10,i);for (int j = 0; j < arr.length; j++) {count[ arr[j] / division % 10]++;}for (int m = 1; m < count.length; m++){count[m] = count[m] + count[m-1];}for (int n = arr.length-1; n >= 0; n--){result[--count[arr[n] / division % 10]] = arr[n];}System.arraycopy(result,0,arr,0,arr.length);Arrays.fill(count,0);}
}

9、桶排序（BucketSort）

思想：找到这个数组中的最小值和最大值，在最小值和最大值间建立多个桶，把数据放在对应桶中，对每个桶中的数据进行排序，排序完成后按照桶的范围大小进行顺序合并。实际生产中并不常用，原因是时间和空间不可兼得。

代码：

public static void sort(int[] arr){List[] buckets = new ArrayList[10];for (int i = 0; i < buckets.length; i++) {buckets[i] = new ArrayList<Integer>();}for (int i = 0; i < arr.length; i++) {buckets[arr[i]/10].add(arr[i]);}for (int i = 0; i < buckets.length; i++) {buckets[i].sort(null);}int k = 0;for (int i = 0; i < buckets.length; i++) {if (buckets[i].size() > 0){for (int j = 0; j < buckets[i].size(); j++) {arr[k++] = (int)buckets[i].get(j);}}}
}

10、堆排序（HeapSort）

思想：堆是一个数据结构，堆里面有两个特殊形式，分别是大顶堆和小顶堆，大顶堆的首元素是数组中最大的，就可以利用这个特性，将数组首先形成一个大顶堆，接着交换起始位置和终止位置的值，这样终止位置就是数组中最大的值了。然后把起始位置到终止位置-1的元素再次形成一个大顶堆，重复执行上述操作，最终排序完成。

代码：

private static void sort(int[] arr){for(int i = arr.length/2 - 1; i >= 0; i--){adjustHeap(arr,i,arr.length);}for(int j = arr.length - 1; j > 0; j--){swap(arr,0,j);adjustHeap(arr,0,j);}
}//实际上就是对于每一个节点，比较其与其子节点中最大的那个数，并将最大的那个数交换到节点位置
private static void adjustHeap(int[] arr,int i,int length){int temp = arr[i];for(int k = i*2+1; k < length; k = k*2+1){if( k+1 < length && arr[k] < arr[k+1] ){k++;}if( arr[k] > temp ){arr[i] = arr[k];i = k;}else{break;}}arr[i] = temp;
}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

http://chatgpt.dhexx.cn/article/NFJfQPMe.shtml

相关文章

十大排序算法（C++版）

十大排序算法（C++版）

十大排序算法 前言一、插入排序二、希尔排序三、冒泡排序四、快速排序五、选择排序六、归并排序七、堆排序八、计数排序九、桶排序十、基数排序总结 前言 什么是排序&#xff1f; 排序&#xff1a;将一组杂乱无章的数据按一定规律顺次排列起来。即&#xff0c;将无序序列排成一…
阅读更多...
十大排序算法详解

十大排序算法详解

十大排序算法详解 参考程序员必知必会的十大排序算法详解 引言 对于排序的分类&#xff0c;可以将排序算法分为两大类&#xff1a;基于比较和非比较的算法。 基于比较的排序算法可以细分为&#xff1a; 基于交换类&#xff1a;冒泡排序、快速排序基于插入类&#xff1a;直接插入…
阅读更多...
JS 实现十大排序算法

JS 实现十大排序算法

文章目录 前言零、十大排序一、冒泡排序&#xff08;bubbleSort&#xff09;二、选择排序&#xff08;selectionSort&#xff09;三、插入排序&#xff08;insertSort&#xff09;四、希尔排序&#xff08;shellSort&#xff09;五、归并排序&#xff08;mergeSort&#xff09;…
阅读更多...
十大经典排序算法Java版（动图演示）

十大经典排序算法Java版（动图演示）

文章目录 0 排序算法说明0.1 内部排序和外部排序0.2 比较类排序和非比较类排序0.3 关于时间复杂度0.4 关于稳定性0.5 名词解释&#xff1a; 1 交换排序——冒泡排序&#xff08;Bubble Sort&#xff09;1.1 什么时候最快1.2 什么时候最慢1.3 算法步骤1.4 动图演示1.5 Java实现 …
阅读更多...
html之如何让button按钮居中

html之如何让button按钮居中

解决措施&#xff1a;使用center或者div的align属性 示例代码&#xff1a; <html> <body><center><button onClick"clickme()">hit me</button></center><script>function clickme(){alert("123");} </scr…
阅读更多...
HTML中让表单和提交按钮居中的方法

HTML中让表单和提交按钮居中的方法

表单&#xff1a; form{ width: 500px; /*设置宽度&#xff0c;方便使其居中*/ margin: 40px auto auto auto; /*上右下左*/ font-size: 25px; 提交按钮&#xff1a;div的align属性 <div align"center"><button onClick"clickme()">提交…
阅读更多...
android中的Button按钮居中（水平垂直中）

android中的Button按钮居中（水平垂直中）

今天发现一个很怪异的事 Android Studio中居然一个简单的按钮水品垂直居中都写不出来 下图为理想效果&#xff1a; 可是当我写原始出代码的时候&#xff08;如下&#xff09;&#xff1a; <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android&quo…
阅读更多...
Vue组件居中：文字居中，按钮居中，图片居中等，如何实现在容器中居中

Vue组件居中：文字居中，按钮居中，图片居中等，如何实现在容器中居中

Vue实现组件在容器中居中显示的办法 本文用实验的方法理解各种方法实现居中的效果。 实现水平居中的样式主要有&#xff1a;text-align: center&#xff0c; margin: auto。 当然还有别的方式也可以实现&#xff0c;也会写在下面。 用三个同样的div来控制变量法看效果&#xf…
阅读更多...
Contact form 7 提交按钮居中，怎么设置submit button居中显示

Contact form 7 提交按钮居中，怎么设置submit button居中显示

Contact form 7 提交按钮居中&#xff0c;怎么设置submit button居中显示 前言 最近公司在做网站&#xff0c;毫无疑问用的是wordpress程序&#xff0c;然后就用到了contact form 7这个插件。单是这个插件的按钮始终无法居中显示&#xff0c;查了很多教程有的让改主题&#x…
阅读更多...
tkinter 让按钮居中显示

tkinter 让按钮居中显示

def ask(self, title, text, btn_comfirm_name"确定", btn_cancel_name"取消", wraplength400):self.master.title(title)tk.Label(self.middle, texttext, bg"#ffffff", wraplengthwraplength,justify"left").pack(pady15)self.botto…
阅读更多...
html表单中按钮居中,Ant design StepsForm中如何使底部按钮居中

html表单中按钮居中,Ant design StepsForm中如何使底部按钮居中

如图所示，当前有一个StepsForm表单，代码如下(基本就是官网的示例修改的)const Demo: React.FC = () => {const Option = [ {key: 1, value: 111, label: 个人 }, {key: 2, value: 222, label: 合作 }, ] const waitTime = (time: number = 100) => {return new Promise…
阅读更多...
layui使按钮居中_button按钮居中的方法

layui使按钮居中_button按钮居中的方法

今天在写页面时&#xff0c;发现给button按钮设置居中时&#xff0c;css页面写了text-align"center"&#xff0c;但是不起作用&#xff0c;用了display属性也无作用&#xff0c;试了好多次发现要给button按钮添加个p&#xff0c;然后让p居中就可以了。以下写个test来…
阅读更多...
Android IMS 语音通话 vs 视频通话 vs 视频彩铃

Android IMS 语音通话 vs 视频通话 vs 视频彩铃

背景 以下内容基于Android P code。 主要差异 视频通话比语音通话主要是多了判断是否为视频通话&#xff0c;及视频的显示和传输。如下&#xff1a; video call 视频界面显示控制 界面通过IVideoProvider控制camera的显示并设置TextureView等&#xff0c;Ims service通过IV…
阅读更多...
Unity 语音和视频通话快速解决方案——声网 SDK接入指南（Android）

Unity 语音和视频通话快速解决方案——声网 SDK接入指南（Android）

Unity 语音和视频通话快速解决方案——声网 SDK接入指南&#xff08;Android&#xff09; 文章目录 Unity 语音和视频通话快速解决方案——声网 SDK接入指南&#xff08;Android&#xff09;一、前言二、后台创建应用三、获取 SDK四、接入 Agora Voice 语音 SDK1. 导入工程2. 搭…
阅读更多...
技术分享| 小程序实现音视频通话

技术分享| 小程序实现音视频通话

上一期我们把前期准备工作做完了&#xff0c;这一期就带大家实现音视频通话&#xff01; sdk 二次封装 为了更好的区分功能&#xff0c;我分成了六个 js 文件 config.js 音视频与呼叫邀请配置 store.js 实现音视频通话的变量 rtc.js 音视频逻辑封装 live-code.js 微信推拉…
阅读更多...
快速开放，推荐一个视频通话sdk agora

快速开放，推荐一个视频通话sdk agora

1&#xff0c;agora 推荐一个做实时视频的sdk。 做互联网公司&#xff0c;要快速做出自己的稳定的产品。 视频&#xff0c;语音聊天还是有一定的门槛的。 http://cn.agora.io/ 做互联网的要的就是要快速 2&#xff0c;每个月还有免费的流量 上线后每月10000分钟免费。这个…
阅读更多...
基于linphone android sdk 的voip语音、视频通话 教程三、视频通话

基于linphone android sdk 的voip语音、视频通话 教程三、视频通话

如果觉得下面的麻烦可以直接到https://item.taobao.com/item.htm?id587133228080获取源码。源码功能性更好、更完善。 想测试apk请加群261074724 最新的sdk4教程地址 https://blog.csdn.net/Java_lilin/article/details/84842314 前面两篇介绍了注册、拨打、接听等 参考地…
阅读更多...
Web项目引入Agora SDK实现视频通话功能

Web项目引入Agora SDK实现视频通话功能

零、前言 简介&#xff1a;声网Agora。一个专注移动端的高清实时通话云服务解决方案。 &#xff08;1&#xff09;声网Agora成立于2013年&#xff0c;是实时音视频云行业开创者和全球领先的专业PaaS服务商。开发者只需简单调用Agora API&#xff0c;30分钟即可在应用内构建多种…
阅读更多...
Android之 集成音视频通话

Android之 集成音视频通话

一&#xff0c;背景 1.1 最近接收一个即时通讯二开项目&#xff0c;即时通讯部分用的XMPP协议&#xff0c;音视频则是集成的国外的开源免费库jitsi-meet-sdk-2.4.0-4.aar&#xff0c;是基于WebRTC的开源框架。但客户想要微信那种页面的排版&#xff0c;后来经研究jitsi是不能修…
阅读更多...
Unity实战篇 | 接入 声网SDK 实现 视频通话——自己动手做一个 视频通话

Unity实战篇 | 接入 声网SDK 实现 视频通话——自己动手做一个 视频通话

目录 🐱‍🏍前言🎂Unity 接入 声网SDK 实现 音视频通话第1️⃣步，创建声网应用第2️⃣步，获取相应的SDK第3️⃣步，将SDK接入Unity中第4️⃣步：搭建一个测试场景，编写测试代码第5️⃣步：视频通话API第6️⃣步：视频通话 效果测试🎂案例下载链接🎨总结🐱‍🏍
阅读更多...
推荐文章

Copyright @ 2022~2023