JAVA 常见算法（选择排序，二分查找）

JAVA 常见算法（选择排序，二分查找）

选择排序

---

选择排序的思想

• 每轮选择当前位置，开始找出后面的较小值与该位置交换

选择排序的关键

• 确定总共需要选择几轮：数组的长度-1
• 控制每轮从以前位置为基准，与后面元素选择几次

二分查找

• 二分查找性能好，二分查找的前提是必须是排好序的数据

总结

1. 数组的二分查找的实现步骤是怎样的？
   • 定义变量记录左边和右边位置
   • 使用while循环控制查询（条件是左边位置<=右边位置）
   • 循环内部获取中间索引
   • 判断当前要找的元素如果大于中间元素，左边位置=中间位置+1
   • 判断当前要找的元素如果小于中间元素，右边位置=中间位置-1
   • 判断当前要找的元素如果等于中间元素，返回当前中间元素索引

使用实例

import java.util.Arrays;

public class ArraysDemo {
    //目标：掌握快排与二分查找算法
    public static void main(String[] args) {
        int[] arr = new int[]{130, 39, 56, 43, 78, 98, 1};
        int[] arr1 = new int[]{130, 39, 56, 43, 78, 98, 1};
        fastSort(arr);
        bulletSort(arr1);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr1));
        System.out.println(binarySearch(arr, 43));

    }

    /**
     *二分查找算法
     * @param arr   源数组
     * @param date   需要查找的数据
     * @return   若数组中存在相应数据则返回对应索引，否则返回 -（应插入位置+1）
     */
    public static int binarySearch(int[] arr, int date){
        //定义左右索引
        int left = 0;
        int right = arr.length-1;

        //开始循环，进行二分查找
        while(left<=right){
            int middle = (left+right)/2;

            if(date>arr[middle]){
                //往右边查找
                left = middle + 1;
            }else if(datearr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 冒泡拍寻
     * @param arr 源数组
     */
    public static void bulletSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-(i+1); j++) {
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85