TongHui的博客 - 算法题
type: channel
link: https://tonghui.domcer.com/index.php/category/%E7%AE%97%E6%B3%95%E9%A2%98/
description: 刷过的算法题
items: 冒泡排序、选择排序和查找算法

冒泡排序、选择排序和查找算法
type: item
date: 2021-05-16T17:23:00+08:00
description: 1.1 认识算法算法是解决某个实际问题的过程和方法。比如百度地图给你规划路径，计算最优路径的过程就需要用到算法。再比如你在抖音上刷视频时，它会根据你的喜好给你推荐你喜欢看的视频，这里也需要用到算法。作为java程序员，我们日常几乎用不到算法，只需要学习几种常见的基础算法就可以了。而且Java语言本身就内置了一些基础算法给我们使用，实际上自己也不会去写这些算法。我们为什么要学习算法呢？算法可以锻炼我们的编程思维。1.2 冒泡排序(重要)接下来，我们学习一种算法叫排序算法，它可以价格无序的整数，排列成从小到大的形式（升序），或者从大到小的形式（降序）学习算法我们先要搞清楚算法的流程，然后再去“推敲“如何写代码。（注意，我这里用的次是推敲，也就是说算法这样的代码并不是一次成型的，是需要反复修改才能写好的**）。先来学习冒泡排序，先来介绍一下，冒泡排序的流程冒泡排序核心思路：每次将相邻的两个元素继续比较 如下图所示： 第一轮比较 3次 第二轮比较 2次 第三轮比较 1次public class Test1 { public static void main(String[] args) { // 1、准备一个数组 int[] arr = {5, 2, 3, 1}; // 2、定义一个循环控制排几轮 for (int i = 0; i < arr.length - 1; i++) { // i = 0 1 2 【5， 2， 3， 1】 次数 // i = 0 第一轮 0 1 2 3 // i = 1 第二轮 0 1 2 // i = 2 第三轮 0 1 // 3、定义一个循环控制每轮比较几次。 for (int j = 0; j < arr.length - i - 1; j++) { // 判断当前位置的元素值，是否大于后一个位置处的元素值，如果大则交换。 if(arr[j] > arr[j+1]){ int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } System.out.println(Arrays.toString(arr)); } } 选择排序我们先分析选择排序算法的流程：选择排序的核心思路是，每一轮选定一个固定的元素，和其他的每一个元素进行比较；经过几轮比较之后，每一个元素都能比较到了。接下来，按照选择排序的流程编写代码ublic class Test2 { public static void main(String[] args) { // 1、准备好一个数组 int[] arr = {5, 1, 3, 2}; // 0 1 2 3 // 2、控制选择几轮 for (int i = 0; i < arr.length - 1; 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++) { // 判断当前位置是否大于后面位置处的元素值，若大于则交换。 if(arr[i] > arr[j]){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } System.out.println(Arrays.toString(arr)); } }查找算法1.3 查找算法接下来，我们学习一个查找算法叫做二分查找。在学习二分查找之前，我们先来说一下基本查找，从基本查找的弊端，我们再引入二分查找，这样我们的学习也会更加丝滑一下。先聊一聊基本查找：假设我们要查找的元素是81，如果是基本查找的话，只能从0索引开始一个一个往后找，但是如果元素比较多，你要查找的元素比较靠后的话，这样查找的此处就比较多。性能比较差。再讲二分查找：二分查找的主要特点是，每次查找能排除一般元素，这样效率明显提高。但是二分查找要求比较苛刻，它要求元素必须是有序的，否则不能进行二分查找。二分查找的核心思路第1步：先定义两个变量，分别记录开始索引(left)和结束索引(right) 第2步：计算中间位置的索引，mid = (left+right)/2; 第3步：每次查找中间mid位置的元素，和目标元素key进行比较 如果中间位置元素比目标元素小，那就说明mid前面的元素都比目标元素小 此时：left = mid+1 如果中间位置元素比目标元素大，那说明mid后面的元素都比目标元素大 此时：right = mid-1 如果中间位置元素和目标元素相等，那说明mid就是我们要找的位置 此时：把mid返回 注意：一搬查找一次肯定是不够的，所以需要把第1步和第…