java版十大排序经典算法:完整代码(2)
快速排序
简单解释: 快速排序就是每次找一个基点(第一个元素),然后两个哨兵,一个从最前面往后走,一个从最后面往前面走,如果后面那个哨兵找到了一个比基点大的数停下来,前面那个哨兵找到比基点大的数停下来,然后交换两个哨兵找到的数,如果找不到最后两个哨兵就会碰到一起就结束,最后交换基点和哨兵相遇的地方的元素,然后就将一个序列分为比基点小的一部分和比基点大的一部分,然后递归左半部分和右半部分,最后的结果就是有序的了。
完整代码:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: QuickSort * @Description: 快速排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:32 */ public class QuickSort { //快速排序 public static void quickSort(int[] arr) { quickSort(arr, true); } public static void quickSort(int[] arr, boolean ascending) { if (ascending) { quickSort(arr, 0, arr.length - 1, true); } else { quickSort(arr, 0, arr.length - 1, false); } } public static void quickSort(int[] arr, int begin, int end, boolean ascending) { if (ascending) quickSort(arr, begin, end); else quickSortDescending(arr, begin, end); } //快排序升序 -- 默认 public static void quickSort(int[] arr, int begin, int end) { if (begin > end) { //结束条件 return; } int base = arr[begin]; int i = begin, j = end; while (i < j) { // 两个哨兵(i左边,j右边)没有相遇 while (arr[j] >= base && i < j) { //哨兵j没找到比base小的 j--; } while (arr[i] <= base && i < j) { //哨兵i没找到比base大的 i++; } if (i < j) { //如果满足条件则交换 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //最后将基准为与i和j相等位置的数字交换 arr[begin] = arr[i]; arr[i] = base; quickSort(arr, begin, i - 1); //递归调用左半数组 quickSort(arr, i + 1, end); //递归调用右半数组 } //快排序降序 public static void quickSortDescending(int[] arr, int begin, int end) { if (begin > end) { //结束条件 return; } int base = arr[begin]; int i = begin, j = end; while (i < j) { // 两个哨兵(i左边,j右边)没有相遇 while (arr[j] <= base && i < j) { //哨兵j没找到比base大的 j--; } while (arr[i] >= base && i < j) { //哨兵i没找到比base小的 i++; } if (i < j) { //如果满足条件则交换 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //最后将基准为与i和j相等位置的数字交换 arr[begin] = arr[i]; arr[i] = base; quickSortDescending(arr, begin, i - 1); //递归调用左半数组 quickSortDescending(arr, i + 1, end); //递归调用右半数组 } }
直接选择排序
简单解释: 数组分为已排序部分(前面)和待排序序列(后面) 第一次肯定所有的数都是待排序的 从待排序的序列中找到最大或最小的那个元素,放到前面的已排序部分,然后一直找,不断缩小待排序的范围,直到所有的数都是已排序的了
完整代码:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: SelectSort * @Description: 选择排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:33 */ public class SelectSort { //直接选择排序 public static void selectSort(int[] arr, boolean ascending) { for (int i = 0; i < arr.length; i++) { int m = i; //最小值或最小值的下标 for (int j = i + 1; j < arr.length; j++) { if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) { m = j; //找到待排序的数中最小或最大的那个数,记录下标 } } //交换位置 int temp = arr[i]; arr[i] = arr[m]; arr[m] = temp; } } public static void selectSort(int[] arr) { selectSort(arr, true); } }
堆排序
先理解下大顶堆和小顶堆,看图
大顶堆,双亲结点的值比每一个孩子结点的值都要大。根结点值最大
小顶堆,双亲结点的值比每一个孩子结点的值都要小。根结点值最小
简单解释: 构建好大顶堆或小顶堆结构,这样最上面的就是最大值或最小值,那么我们取出堆顶元素,然后重新构建结构,一直取,一直重新构建,那么最后达到排序的效果了。
完整代码:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: HeapSort * @Description: 堆排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:34 */ public class HeapSort { //堆排序 public static void heapSort(int[] arr) { //对传入的数组进行建立堆,这里默认建立大顶堆,进行升序排列 heapSort(arr, true); } public static void heapSort(int[] arr, boolean maxheap) { //1.构建大顶堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { //从第一个非叶子结点从下至上,从右至左调整结构 sift(arr, i, arr.length , maxheap); } //2.调整堆结构+交换堆顶元素与末尾元素 for (int j = arr.length - 1; j > 0; j--) { //现在的数组第一个就是根结点,最小值所在,进行交换,把它放到最右边 int temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; //重新建立堆 sift(arr, 0, j , maxheap); //重新对堆进行调整 } } //建立堆的方法 /** * 私有方法,只允许被堆排序调用 * * @param arr 要排序数组 * @param parent 当前的双亲节点 * @param len 数组长度 * @param maxheap 是否建立大顶堆 */ private static void sift(int[] arr, int parent, int len, boolean maxheap) { int value = arr[parent]; //先取出当前元素i for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) { //从parent结点的左子结点开始,也就是2*parent+1处开始 if (child+1 < len && (maxheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1])) { //如果左子结点小于右子结点,child指向右子结点 child++; //右孩子如果比左孩子大,我们就将现在的孩子换到右孩子 } //判断是否符合大顶堆的特性, 如果右孩子大于双亲,自然左孩子也大于双亲,符合 //如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) if (maxheap ? value < arr[child] : value > arr[child]) { arr[parent]=arr[child]; parent = child; } else {//如果不是,说明已经符合我们的要求了。 break; } } arr[parent] =value; //将value值放到最终的位置 } }
总结
本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注猪先飞的更多内容!
相关文章
- 这篇文章主要介绍了如何利用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
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29