Java 常见排序算法代码分享
更新时间:2022年3月23日 14:37 点击:275 作者:多氯环己烷
汇总:
1. 冒泡排序
每轮循环确定最值;
public void bubbleSort(int[] nums){ int temp; boolean isSort = false; //优化,发现排序好就退出 for (int i = 0; i < nums.length-1; i++) { for (int j = 0; j < nums.length-1-i; j++) { //每次排序后能确定较大值 if(nums[j] > nums[j+1]){ isSort = true; temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; } } if(!isSort){ return; } else { isSort = false; } } }
2. 选择排序
每次选出最值,再交换到边上;
public void selectSort(int[] nums){ for (int i = 0; i < nums.length-1; i++) { int index = i; int minNum = nums[i]; for (int j = i+1; j < nums.length; j++) { if(nums[j] < minNum){ minNum = nums[j]; index = j; } } if(index != i){ nums[index] = nums[i]; nums[i] = minNum; } } }
3. 插入排序
对循环的每个数找到属于自己的位置插入;
public void insertionSort(int[] nums){ for (int i = 1; i < nums.length; i++) { int j = i; int insertNum = nums[i]; while(j-1 >= 0 && nums[j-1] > insertNum){ nums[j] = nums[j-1]; j--; } nums[j] = insertNum; } }
4. 快速排序
选一个基本值,小于它的放一边,大于它的放另一边;
public void quickSortDfs(int[] nums, int left, int right){ if(left > right){ return; } int l = left; int r = right; int baseNum = nums[left]; while(l < r){ //必须右边先走 while(nums[r] >= baseNum && l < r){ r--; } while(nums[l] <= baseNum && l < r){ l++; } int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; } nums[left] = nums[l]; nums[l] = baseNum; quickSortDfs(nums, left, r-1); quickSortDfs(nums, l+1, right); }
5. 归并排序
分治算法;
//归 public void mergeSortDfs(int[] nums, int l, int r){ if(l >= r){ return; } int m = (l+r)/2; mergeSortDfs(nums, l, m); mergeSortDfs(nums, m+1, r); merge(nums, l, m, r); } //并 private void merge(int[] nums, int left, int mid, int right){ int[] temp = new int[right-left+1]; int l = left; int m = mid+1; int i = 0; while(l <= mid && m <= right){ if(nums[l] < nums[m]){ temp[i++] = nums[l++]; } else { temp[i++] = nums[m++]; } } while(l <= mid){ temp[i++] = nums[l++]; } while(m <= right){ temp[i++] = nums[m++]; } System.arraycopy(temp, 0, nums, left, temp.length); }
6. 希尔排序
引入步长减少数字交换次数提高效率;
6.1 希尔-冒泡排序(慢)
public void shellBubbleSort(int[] nums){ for (int step = nums.length/2; step > 0 ; step /= 2) { for (int i = step; i < nums.length; i++) { for (int j = i-step; j >= 0; j -= step) { if(nums[j] > nums[j+step]){ int temp = nums[j]; nums[j] = nums[j+step]; nums[j+step] = temp; } } } } }
6.2 希尔-插入排序(快)
public void shellInsertSort(int[] nums){ for (int step = nums.length/2; step > 0; step /= 2) { for (int i = step; i < nums.length; i++) { int j = i; int insertNum = nums[i]; while(j-step >= 0 && nums[j-step] > insertNum){ nums[j] = nums[j-step]; j-=step; } nums[j] = insertNum; } } }
7. 堆排序
大顶堆实现升序,每次将最大值移到堆的最后一个位置上;
public void heapSort2(int[] nums) { for(int i = nums.length/2-1; i >= 0; i--){ sift(nums, i, nums.length); } for (int i = nums.length-1; i > 0; i--) { int temp = nums[0]; nums[0] = nums[i]; nums[i] = temp; sift(nums, 0, i); } } private void sift(int[] nums, int parent, int len) { int value = nums[parent]; for (int child = 2*parent +1; child < len; child = child*2 +1) { if(child+1 < len && nums[child+1] > nums[child]){ child++; } if(nums[child] > value){ nums[parent] = nums[child]; parent = child; } else { break; } } nums[parent] = value; }
8. 计数排序
按顺序统计每个数出现次数;
public void countSort(int[] nums){ int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int num : nums){ max = Math.max(max, num); min = Math.min(min, num); } int[] countMap = new int[max-min+1]; for(int num : nums){ countMap[num-min]++; } int i = 0; int j = 0; while(i < nums.length && j < countMap.length){ if(countMap[j] > 0){ nums[i] = j+min; i++; countMap[j]--; } else { j++; } } }
9. 桶排序
类似计数排序,不同点在于统计的是某个区间(桶)里的数;
public void bucketSort(int[] nums){ int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int num : nums){ max = Math.max(max, num); min = Math.min(min, num); } int bucketCount = (max-min)/nums.length+1; List<List<Integer>> bucketList = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketList.add(new ArrayList<>()); } for(int num : nums){ int index = (num-min)/nums.length; bucketList.get(index).add(num); } for(List<Integer> bucket : bucketList){ Collections.sort(bucket); } int j = 0; for(List<Integer> bucket : bucketList){ for(int num : bucket){ nums[j] = num; j++; } } }
10. 基数排序
按个、十、百位依次归类排序;
public void radixSort(int[] nums){ int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int num : nums) { min = Math.min(min, num); max = Math.max(max, num); } for (int i = 0; i < nums.length; i++) { nums[i] -= min; } max -= min; int maxLen = (max+"").length(); int[][] bucket = new int[nums.length][10]; int[] bucketCount = new int[10]; for (int i = 0, n = 1; i < maxLen; i++, n*=10) { for (int num : nums) { int digitVal = num / n % 10; bucket[bucketCount[digitVal]][digitVal] = num; bucketCount[digitVal]++; } int index = 0; for (int j = 0; j < bucketCount.length; j++) { if(bucketCount[j] > 0){ for (int k = 0; k < bucketCount[j]; k++) { nums[index] = bucket[k][j]; index++; } } bucketCount[j] = 0; } } for (int i = 0; i < nums.length; i++) { nums[i] += min; } }
11. 使用集合或 API
11.1 优先队列
public void priorityQueueSort(int[] nums){ PriorityQueue<Integer> queue = new PriorityQueue<>(); for(int num : nums){ queue.offer(num); } for (int i = 0; i < nums.length; i++) { nums[i] = queue.poll(); } }
11.2 Java API
public void arraysApiSort(int[] nums){ Arrays.sort(nums); }
到此这篇关于Java 常见排序算法代码分享的文章就介绍到这了,更多相关Java 常见排序算法内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.51cto.com/dlhjw/5136864
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29