电子工程师技术服务社区
公告
登录
|
注册
首页
技术问答
厂商活动
正点原子
板卡试用
资源库
下载
文章
社区首页
文章
[Java] Java中的快速排序(二分排序)算法实现
分 享
扫描二维码分享
[Java] Java中的快速排序(二分排序)算法实现
Java
快速排序
二分排序
FanHua
关注
发布时间: 2022-01-13
丨
阅读: 312
快速排序由 C. A. R. Hoare(东尼霍尔,Charles Antony Richard Hoare)在 1960 年提出,之后又有许多人做了进一步的优化。该算法是冒泡排序的一种改进,同样也用到了元素交换,快速排序也是通过逐渐消除待排序的无序序列中逆序元素来实现排序的。 #算法思想 1. 拿到数组后,我们会将数组中的第一个元素(通常)作为基准元素,将比基准元素小的元素放到数组左边,比基准元素大的数组右边。 1. 为此,我们会从基准元素开始查找比基准元素大的数,同时从另外一边开始查找比基准元素小的数,当找到这样两个数时,将其交换顺序,这样数组中的数字会被基准数分割开来,以此类推,直到左边下标=右边下标。 1. 此时基准数并不在中间,所以我们需要将当前下标的数和基准数交换,这样就就完成了第一次排序。 1. 将排序后的数组根据基准数的位置拆开,再进行同样的操作(直接递归),直到left > right结束 1. 输出结果 #具体实现 ```java import java.util.Arrays; public class QuickSort { public static void quickSort(int[] arr, int left, int right) { if (left > right) { return; } // 获得基准数 int base = arr[left]; // 获得i和j,也就是最左边和最右边的索引 int i = left; int j = right; // 循环交换数字 while (i != j) { // 找到比基准数小的数和比基准数大的数 while (arr[j] >= base && i < j) { j--; } while (arr[i] <= base && i < j) { i++; } // 交换这两个数 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 交换基准数 arr[left] = arr[i]; arr[i] = base; // 递归继续对左右数组进行排序 quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); } public static void main(String[] args) { int[] arr = {6, 3, 7, 9, 5, 1, 4, 8}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } } ``` 交换结果 ``` [6, 3, 7, 9, 5, 1, 4, 8] base=6 [5, 3, 4, 1, 6, 9, 7, 8] base=5 [1, 3, 4, 5, 6, 9, 7, 8] base=1 [1, 3, 4, 5, 6, 9, 7, 8] [1, 3, 4, 5, 6, 9, 7, 8] base=3 [1, 3, 4, 5, 6, 9, 7, 8] [1, 3, 4, 5, 6, 9, 7, 8] base=4 [1, 3, 4, 5, 6, 9, 7, 8] [1, 3, 4, 5, 6, 9, 7, 8] [1, 3, 4, 5, 6, 9, 7, 8] [1, 3, 4, 5, 6, 9, 7, 8] base=9 [1, 3, 4, 5, 6, 8, 7, 9] base=8 [1, 3, 4, 5, 6, 7, 8, 9] base=7 [1, 3, 4, 5, 6, 7, 8, 9] [1, 3, 4, 5, 6, 7, 8, 9] [1, 3, 4, 5, 6, 7, 8, 9] [1, 3, 4, 5, 6, 7, 8, 9] [1, 3, 4, 5, 6, 7, 8, 9] ```
原创作品,未经权利人授权禁止转载。详情见
转载须知
。
举报文章
点赞
(
0
)
FanHua
关注
评论
(0)
登录后可评论,请
登录
或
注册
相关文章推荐
MK-米客方德推出工业级存储卡
Beetle ESP32 C3 蓝牙数据收发
Beetle ESP32 C3 wifi联网获取实时天气信息
开箱测评Beetle ESP32-C3 (RISC-V芯片)模块
正点原子数控电源DP100测评
DP100试用评测-----开箱+初体验
Beetle ESP32 C3环境搭建
【花雕体验】16 使用Beetle ESP32 C3控制8X32位WS2812硬屏之二
X
你的打赏是对原创作者最大的认可
请选择打赏IC币的数量,一经提交无法退回 !
100IC币
500IC币
1000IC币
自定义
IC币
确定
X
提交成功 ! 谢谢您的支持
返回
我要举报该内容理由
×
广告及垃圾信息
抄袭或未经授权
其它举报理由
请输入您举报的理由(50字以内)
取消
提交