Java:冒泡排序 | 二分查找
2018-10-29 15:32:53来源:博客园 阅读 ()
2018-10-29 20:16:46
冒泡排序
例子(对数字排序):
假设有这样一组数字:32, 8, 128, 2, 64
现在对其进行冒泡排序(*表示下次比较的开始数字):
32>8? ture: 将32和8调换位置 8, 32*, 128, 2, 64;
32>128? false:保持原位置不动 8, 32, 128*, 2, 64;
128>2 ? true: 将128和2调换位置 8, 32, 2, 128*, 64;
128>64 ? true:将128和64调换位置 8, 32, 2, 64, 128*;
经过以上步骤,最大数128浮出水面。
现在找出剩余数字 8, 32, 2, 64 中的最大数:
8>32? false: 保持原位置不动 8, 32*, 2, 64;
32>2 ? ture: 将32和2调换位置 8, 2, 32*, 64;
32>64? false: 保持原位置不动 8, 2, 32, 64*;
经过以上步骤,最大数64浮出水面。
...
由此一步步比较,即可得到排序后的结果: 2, 8, 32, 64, 128
程序实现如下:
//形式参数intArr表示要排序的数组
1 public static int[] bubbleSort(int[] intArr) {
2 if (intArr == null)
3 return null; // 当传进来的数组为null时返回null
4 int len = intArr.length; // 定义len表示数组的长度
5 if (len < 2)
6 return intArr; // 当数组长度小于2时直接返回该数组,此时无需排序
7
8 while (len > 1) {
9 for (int i = 0; i < len - 1; i++) {
10 // if语句表示如果前一个数大于后一个数,则交换位置,否则什么也不做
11 if (intArr[i] > intArr[i + 1]) {
12 int temp = intArr[i];
13 intArr[i] = intArr[i + 1];
14 intArr[i + 1] = temp;
15 }
16 }
17 len -= 1; // 经过一个循环的比较,已经得出了本次循环的最大值,把它放在索引最大处,接下来比较除最大索引处之外的数的最大值,依次循环...
18 }
19 return intArr;
20 }
二分查找
例子(对上述排序好的数字进行查找):
有如下排序好的数字:2, 8, 32, 64, 128
索引值分别为 0, 1, 2, 3, 4
如何查找数字 2 的索引呢?
取中间索引 2 处的值 32 , 32<2 ? false,说明数值2的索引在索引2的前面;
取索引0和索引2的中间索引值1,索引1处的值为8, 8<2 ? false,说明数值2的索引在索引1的前面;
...
依次取值比较即可得到数值2的索引为1;
程序实现如下:
参数表示在数组intArr中查找值value所在的索引
1 public static int binarySearch(int value, int[] intArr) {
2 int low = 0; // low表示最小索引
3 int high = intArr.length - 1; // len表示最大索引
4
5 while (high >= low) {
6 // 0 1 2 3 4 5 中间索引指2;
7 // 0 1 2 3 4 中间索引则为2
8 int mid = (low+high) >>> 1; // mid表示len无符号右移一位,最高位补0,即除以2
9 int midVal = intArr[mid]; // midVal表示数组中间索引处值
10
11 if (midVal < value)
12 low = mid + 1;
13 else if (midVal > value)
14 high = mid - 1;
15 else
16 return mid; // 当要查找的值找到时返回其索引
17 }
18 return -1; // 当要查找的值未找到时返回-1
19 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash