Java：常见算法

认识算法

什么是算法？

• 解决某个实际问题的过程和方法

学习算法的技巧

1. 先搞清楚算法的流程
2. 直接去推敲如何写代码

排序算法

冒泡排序

• 每次从数组中找出最大值放在数组的后面去。

实现冒泡排序的关键步骤分析

• 确认总共需要做几轮：数组的长度-1
• 每轮比较几次：

• ?当前位置大于后一个位置则交换数据

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        // 准备一个数组
        int[] arr = new int[]{2,6,3,1};
        // 定义一个循环控制排几轮
        for (int i = 0; i < arr.length - 1; i++) {
            // 定义一个循环控制每轮排几次
            for (int j = 0; j < arr.length - i - 1; j++) {
                int code = 0;
                // 判断当前位置的元素值是否大于后一个元素的值，如果大于则交换
                if (arr[j] > arr[j+1]){
                    code = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = code;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

选择排序

选择排序的关键

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

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        // 准备一个数组
        int[] arr = new int[]{5,1,3,2 };
        // 定义一个循环控制排几轮
        for (int i = 0; i < arr.length - 1; i++) {
            // 定义一个循环控制每轮排几次
            for (int j = i+1; j < arr.length; j++) {
                // 判断当前位置的元素值是否大于后一个元素的值，如果大于则交换
                if (arr[i] > arr[j]){
                    int code = arr[i];
                    arr[i] = arr[j];
                    arr[j] = code;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

查找算法?

基本查找/顺序查找

注意：在数据量特别大的时候，基本查找这种从前往后挨个查找的形式，性能是很差的。

二分查找（折半查找）

• 前提条件：数组中的数据必须是有序的
• 核心思想：每次排除一半的数据，查询数据的性能明显提高极多。

结论：二分查找正常的折半条件应该是开始位置left <= 结束位置right。

public class Test {
    public static void main(String[] args) {
        // 准备一个数组
        int[] arr = new int[]{7,23,79,81,103,127,131,147};
        System.out.println(binarySearch(arr, 81));
    }

    public static int binarySearch(int[] arr,int data){
        // 定于两个变量，一个在左边位置，一个在右边位置
        int left = 0;
        int right = arr.length - 1;

        // 定义一个循环控制折半
        while (left <= right){
            // 每次折半，都算出中间位置的索引
            int middle = (left+right)/2;
            // 判断当前要找的元素值与中间位置处的元素值的大小情况
            if (data < arr[middle]){
                // 往左边找，截至位置（右边位置） = 中间位置 - 1
                right = middle - 1;
            }else if (data > arr[middle]){
                // 往右边找，截至位置（左边位置） = 中间位置 + 1
                right = middle - 1;
            }else {
                // 中间位置处的元素值，正好等于我们要找的元素值
                return middle;
            }
        }
        return -1; //-1特殊结果，就代表没有找到！数组中不存在
    }
}