Java中常见的算法 - 冒泡排序 - 选择排序

Java中常见的算法 - 冒泡排序 - 选择排序 - 二分查找

忘是亡心i 2023-09-26 11:38 110阅读 0赞

文章目录

- 常见算法
- - 选择排序
  - 冒泡排序
  - 二分查找

常见算法

选择排序

选择排序的思想:

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

在这里插入图片描述

最终结果: 1 2 3 5

选择排序的关键:

确定总共需要选择几轮：

在上面例子中, 我们发现四个数字需要比较三轮;

第一轮: i = 0
第二轮: i = 1
第三轮: i = 2

可以得到确定轮数是: i < 数组的长度 - 1

控制每轮交换的次数: 控制每轮从以前位置为基准，与后面元素选择几次。

控制每轮次数我们可以用另一个变量 j 控制; 当 i = 0时, 表示进行第一轮比较, j 的值设置为 i + 1, 那么可以得到交换次数是: j < 数组的长度
当i = 0时表示第一轮, j = 1, j < 4(数组的长度)

第一轮第一次比较: j = 1
第一轮第二次比较: j = 2
第一轮第三次比较: j = 3

示例代码:

public static void main(String[] args) {
    // 定义数组
    int[] arr = {
    10, 20, 0, 25, 90, 55, 30};
    // 选择排序
    int num = 0;
    for (int i = 0; i < arr.length - 1; i++) {
     // 表示循环进行多少轮
        for (int j = i + 1; j < arr.length; j++) {
     // 表示每轮比较多少次
            if (arr[i] > arr[j]) {
     // 用i确定要比较的数组元素, j确定被比较的数组元素
                num = arr[i];
                arr[i] = arr[j];
                arr[j] = num;
            }
        }
    }
    // 输出数组内容
    System.out.println(Arrays.toString(arr));
}

冒泡排序

冒泡排序思想:

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

在这里插入图片描述

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

和选择排序一样 :

确定共需要几轮: 数组长度 - 1

确定每轮需要的次数: j = i + 1 < 数组长度

示例代码:

public static void main(String[] args) {
    // 定义数组
    int[] arr = {
    10, 0, 2, 8};
    // 冒泡排序
    int num = 0;
    for (int i = 0; i < arr.length - 1; i++) {
     // 控制循环多少次(进行多少轮)
        for (int j = i; j < arr.length - (i + 1); j++) {
     // 控制每轮比较多少次
            if (arr[j] > arr[j + 1]) {
                num = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = num;
            }
        }
    }
    // 输出数组
    System.out.println(Arrays.toString(arr));
}

二分查找

基本查找的弊端: 在数据量特别大的时候，基本查找从前往后寻找的性能是很差的

二分查找:

二分查询性能好，但是二分查找有一个前提是: 必须是排好序的数据。

二分查找, 顾名思义从中间位置开始查找, 比较要查找的数是大于还是小于中间位置的数, 再从满足条件的区间中继续进行二分查找

在这里插入图片描述

示例代码:

public class Sorting3 {
    public static void main(String[] args) {
        // 定义数组
        int[] arr = {
    10, 20, 25, 30, 38, 42, 49, 55, 58};
        // 调用定义的二分查找的方法
        System.out.println(binarySearch(arr, 55)); // 7
        System.out.println(binarySearch(arr, 120)); // -1
    }
    /**
     * 定义二分查找的方法
     * @param arr 排序的数组
     * @param num 要找的数组
     * @return 存在返回该元素索引, 不存在返回-1
     */
    public static int binarySearch(int[] arr, int num) {
        int min = 0;
        int max = arr.length - 1;
        while (min <= max) {
            int mid = (min + max) / 2;
            if (num == arr[mid]) {
                return mid;
            } else if (num > arr[mid]) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return -1;
    }
}

小结: 数组的二分查找的实现步骤

定义变量记录左边和右边位置。

使用while循环控制查询（条件是左边位置<=右边位置）

循环内部获取中间元素索引

判断当前要找的元素如果大于中间元素，左边位置=中间索引+1

判断当前要找的元素如果小于中间元素，右边位置=中间索引-1

判断当前要找的元素如果等于中间元素，返回当前中间元素索引。