常见算法

选择排序

选择排序的思想

• 每轮选择当前位置，开始找出后面的较小值与该位置的值进行交换，知道与最后一个数比较完成，本轮结束；

  然后从后一个位置开始，依次比较第二个元素后面的值，直到最后一个比较完成，本轮结束

  一直重复比较，每次轮数结束后起始点递进1，反复执行直到起始点变成最后一个元素为止

image.png

选择排序的关键

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

代码

package com.java.sort_binarysearch;

import java.util.Arrays;

public class Test01 {
    public static void main(String[] args) {
        // 1.定义数组
        int[] arr = {5, 1, 3, 2};
        //           0  1  2  3

        // 2.定义一个循环控制选择几轮：arr.length - 1
        // 其中 i是起始值 j是被比较值
        for (int i = 0; i < arr.length; i++) {
            /*
            i = 0  j = 1 2 3
            i = 1  j = 2 3
            i = 2  j = 3
             */

            // 3. 定义内部循环，控制循环几次
            for (int j = i + 1; j < arr.length; j++) {
                // 当前位：arr[i]
                // 如果有比当前位更小的，则交换
                if (arr[i] > arr[j]) {  // 使用异或运算特性交换两个元素
                    arr[i] ^= arr[j];
                    arr[j] ^= arr[i];
                    arr[i] ^= arr[j];
                }

            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

二分查找

二分查找的思想

• 基本查找在数据量比较大的时候，从前往后查找的性能极差
• 二分查找性能好，前提是数据必须被排好序
• 二分查找就是每次查找砍掉一半的查找范围
• 二分查找正常的检索条件应该是：开始位置min<=结束位置max

代码

package com.java.sort_binarysearch;

public class Test02 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(binarySearch(arr, 3));
        System.out.println(binarySearch(arr, -43));

    }
    
    /**
     * 二分查找元素索引
     *
     * @return 索引 不存在返回-1
     */
    public static int binarySearch(int[] arr, int data) {
        // 1. 定义左边的位置和右边的位置
        int left = 0;
        int right = arr.length - 1;

        // 2. 开始循环，折半查询
        // 折叠条件：左边位置小于等于右边位置，最后一次折叠即两者相遇
        while (left <= right) {
            // 取中间索引
            int middleIndex = (left + right) / 2;   //不用关心中间值是否准确，大致即可，即11对折可以为5也可以为6，无所谓
            // 3. 判断当前中间位置的元素和要找的大小情况
            if (data > arr[middleIndex]) {
                // 3.1 往右找，左边值更新 = 中间索引 + 1
                left = middleIndex + 1;
            } else if (data < arr[middleIndex]) {
                // 3.2 往左找，右边位置更新 = 中间索引 - 1
                right = middleIndex - 1;
            } else {
                // 3.3 中间值正好是待查找值
                return middleIndex;
            }
        }
        // 4. 元素不在其中的情况
        return -1;  // 查无此元素
    }
}