冒泡排序
算法
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
实例
1 public static void main(String[] args) {
2
3
4 // 初始化数组并赋值
5 int[] values = {6, 1, 3, 2, 9, 0, 7, 4, 5, 8};
6
7 // 进行从小到大排序
8 bubbleSort(values);
9
10 // 打印排序后结果
11 System.out.println(Arrays.toString(values));
12
13 }
14
15
16 /**
17 * 冒泡排序
18 *
19 * @param values 传入的排序数组
20 */
21 private static void bubbleSort(int[] values) {
22
23 int temp;
24
25 for (int i = 0; i < values.length; i++) {
26 for (int j = 0; j < values.length - 1 - i; j++) {
27 if (values[j] > values[j + 1]) {
28 temp = values[j];
29 values[j] = values[j + 1];
30 values[j + 1] = temp;
31 }
32 }
33 }
34 }
存在问题
- 当数组数据本身有序的时候,走遍历就会很浪费资源
- 初始化状态下,有序数列是空的
- 判断每一趟是否发生了数组元素的交换，如果没有发生，则说明此时数组已经有序，无需再进行后续趟数的比较了。此时可以中止比较
优化
- 添加标识位判别
1 // 初始化数组并赋值
2 int[] values = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
3
4 // 进行从小到大排序
5 bubbleSort(values);
6
7 // 打印排序后结果
8 System.out.println(Arrays.toString(values));
9
10 }
11
12
13 /**
14 * 冒泡排序
15 *
16 * @param values 传入的排序数组
17 */
18 private static void bubbleSort(int[] values) {
19
20 int temp;
21
22 for (int i = 0; i < values.length; i++) {
23
24 // 定义一个布尔类型的变量，标记数组是否已达到有序状态
25 boolean flag = true;
26 for (int j = 0; j < values.length - 1 - i; j++) {
27 if (values[j] > values[j + 1]) {
28 temp = values[j];
29 values[j] = values[j + 1];
30 values[j + 1] = temp;
31
32 //本趟发生了交换，表明该数组在本趟处于无序状态，需要继续比较；
33 flag = false;
34 }
35 }
36
37 //根据标记量的值判断数组是否有序，如果有序，则退出；无序，则继续循环。
38 if (flag) {
39 break;
40 }
41
42 }
43 }
二分查找
算法
- 设数组中的元素从小到大有序地存放在数组(array)中，首先将给定值key与数组中间位置上元素的关键码(key)比较，如果相等，则检索成功
- 否则，若key小，则在数组前半部分中继续进行二分法检索
- 若key大，则在数组后半部分中继续进行二分法检索
- 这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败
实例
1 public static void main(String[] args) {
2
3 int[] arr = {30, 20, 50, 10, 80, 9, 7, 12, 100, 40, 8};
4 // 所要查找的数
5 int searchWord = 20;
6 //二分法查找之前，一定要对数组元素排序
7 Arrays.sort(arr);
8 System.out.println(Arrays.toString(arr));
9 System.out.println(searchWord + "元素的索引：" + binarySearch(arr, searchWord));
10
11 }
12
13
14 /**
15 * 二分查找
16 *
17 * @param array 传入数组
18 * @param value 角标位置
19 * @return 查到的数据 位置
20 */
21 public static int binarySearch(int[] array, int value) {
22 int low = 0;
23 int high = array.length - 1;
24 while (low <= high) {
25 int middle = (low + high) / 2;
26 if (value == array[middle]) {
27
28 //返回查询到的索引位置
29 return middle;
30 }
31 if (value > array[middle]) {
32 low = middle + 1;
33 }
34 if (value < array[middle]) {
35 high = middle - 1;
36 }
37 }
38
39 //上面循环完毕，说明未找到，返回-1
40 return -1;
41 }