Java进阶(9)——冒泡排序、选择排序、二分法查找

常见的算法

冒泡排序、选择排序、二分法查找

• 冒泡排序（BubbleSort）的核心思想：重复比较n轮（n为数组的大小）。每一轮依次比较相邻的两个数，将小数放在前面，大数放在后面。

• 选择排序的核心思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

• 二分法查找：找到一个中间点，每次判断要找的数在中间点左边还是右边，循环查找直到找到或者没有该数为止。

冒泡排序

重复比较n轮（n为数组的大小）。每一轮依次比较相邻的两个数，将小数放在前面，大数放在后面。

  public void bubblesort(int[] a){
        for(int j = 0;j<a.length;j++){
            for(int i = 0;i<a.length - 1;i++){
                if(a[i] > a[i+1]){
                    int temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11

选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

public void selectsort(int[] a){
        for(int i = 0;i<a.length;i++){
            int tree = a[i];
            for(int j = i+1;j<a.length;j++){
                if(a[j] < tree){
                    a[i] = a[j];
                    a[j] = tree;
                    tree = a[i];
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

二分法查找

优化冒泡排序和选择排序

zip 0星 超过10%的资源 595KB

下载

找到一个中间点，每次判断要找的数在中间点左边还是右边，循环查找直到找到或者没有该数为止。

public void midfindid(int[] a,int id){
        int left = 0,right = a.length-1;
        int mid = 0;
        while(left <= right){
            mid = (right + left)/2;
            if(a[mid] == id){
                System.out.println("找到了" + id);
                return;
            }else if(a[mid] > id){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        System.out.println("没有找到id，可能是您的输入有误");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

完整代码

从以上简单的算法介绍继续细化如何写代码，首先从键盘获取数据，输入一个数组。冒泡排序需要重复n轮（n为数组的大小），每一轮都比较相邻的数，小在前，大在后，主要涉及替换的操作。选择排序设置第一个数为最小数，将剩下的数与其对比，小的替换为最小数，一轮之后得到最小的数放在第一个位置，剩下的数继续第二轮设置第二个数为起始最小数，如此重复即可。

import java.util.Scanner;

public class Sort {
    private static int n;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        n = s.nextInt();//无法从静态上下文引用非静态字段“n”
        System.out.println("请输入" +n+ "个数");
        int[] array = new int[n];
        Scanner sc = new Scanner(System.in);
        for(int i = 0;i<n;i++){
            array[i] = sc.nextInt();
        }
        Sort so = new Sort();
        //so.bubblesort(array);
        so.selectsort(array);
        //输出
        for(int i = 0;i<array.length;i++){
            System.out.println(array[i]);
        }
        so.midfindid(array,5);
    }
    public void bubblesort(int[] a){
        for(int j = 0;j<a.length;j++){
            for(int i = 0;i<a.length - 1;i++){
                if(a[i] > a[i+1]){
                    int temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                }
            }
        }
    }

    public void selectsort(int[] a){
        for(int i = 0;i<a.length;i++){
            int tree = a[i];
            for(int j = i+1;j<a.length;j++){
                if(a[j] < tree){
                    a[i] = a[j];
                    a[j] = tree;
                    tree = a[i];
                }
            }
        }
    }

    public void midfindid(int[] a,int id){
        int left = 0,right = a.length-1;
        int mid = 0;
        while(left <= right){
            mid = (right + left)/2;
            if(a[mid] == id){
                System.out.println("找到了" + id);
                return;
            }else if(a[mid] > id){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        System.out.println("没有找到id，可能是您的输入有误");
    }
}

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

输出

6
请输入6个数
3 1 5 2 7 4
1 2 3 4 5 7 找到了5
1
2
3
4

Arrays工具类

Arrays工具类的底层基本上就是排序算法和二分法查找算法。其次工具类都是final方法。

完整代码

import java.util.Arrays;
public class test {
    public static void main(String[] args) {
        int[] b = new int[]{1,7,4,2,8,3,9};
        Arrays.sort(b);
        for(int i = 0;i<b.length;i++){
            System.out.print(b[i] + " ");
        }
        int id = 2;
        int index = Arrays.binarySearch(b,id);
        if(index == -1){//binarySearch底层返回index = -1代表找不到
            System.out.println("该元素不存在");
        }
        else System.out.println(id+"的索引为"+index);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

输出
1 2 3 4 7 8 9 2的索引为1

学会了吗？