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

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

#### 文章目录 ####

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

### 常见算法 ###

#### 选择排序 ####

**选择排序的思想**:

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

![在这里插入图片描述][4cfcdcb8807d49e2ab2e9cb99c1e9dbd.png_pic_center]

> 最终结果: 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));
    }

--------------------

#### 冒泡排序 ####

**冒泡排序思想**:

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

![在这里插入图片描述][1ee2a60be712476cbb33105bc162102f.png_pic_center]

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

> 和选择排序一样 :
> 
> 确定共需要几轮: `数组长度 - 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));
    }

#### 二分查找 ####

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

**二分查找**:

> 二分查询性能好，但是二分查找有一个前提是: 必须是排好序的数据。
> 
> 二分查找, 顾名思义从中间位置开始查找, 比较要查找的数是大于还是小于中间位置的数, 再从满足条件的区间中继续进行二分查找

![在这里插入图片描述][79e58bba39484979b25ee4b7aa03708d.png_pic_center]  
![在这里插入图片描述][8c117074d89e43e1a5a4ff1f46680b6f.png_pic_center]

**示例代码**:

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
> 
> 判断当前要找的元素如果等于中间元素，返回当前中间元素索引。

[4cfcdcb8807d49e2ab2e9cb99c1e9dbd.png_pic_center]: https://img-blog.csdnimg.cn/4cfcdcb8807d49e2ab2e9cb99c1e9dbd.png#pic_center
[1ee2a60be712476cbb33105bc162102f.png_pic_center]: https://img-blog.csdnimg.cn/1ee2a60be712476cbb33105bc162102f.png#pic_center
[79e58bba39484979b25ee4b7aa03708d.png_pic_center]: https://img-blog.csdnimg.cn/79e58bba39484979b25ee4b7aa03708d.png#pic_center
[8c117074d89e43e1a5a4ff1f46680b6f.png_pic_center]: https://img-blog.csdnimg.cn/8c117074d89e43e1a5a4ff1f46680b6f.png#pic_center