入门到入土，Java学习 day16（算法1）

利用循环遍历来判断是否相等

二分查找/折半查找

前提条件：数组中的数据有序

每次排除一般的查找范围

用min,max,mid来处理，最大加最小除2，比较，然后得到在中间左边还是右边然后更新最大最小

public class Two {// 二分查找方法，返回目标值在数组中的索引，如果未找到则返回 -1public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {// 计算中间索引int mid = left + (right - left) / 2;if (arr[mid] == target) {// 找到目标值，返回中间索引return mid;} else if (arr[mid] < target) {// 目标值在右半部分，更新左边界left = mid + 1;} else {// 目标值在左半部分，更新右边界right = mid - 1;}}// 未找到目标值，返回 -1return -1;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13};int target = 7;// 调用二分查找方法int result = binarySearch(arr, target);if (result != -1) {System.out.println("目标值 " + target + " 在数组中的索引是: " + result);} else {System.out.println("目标值 " + target + " 不在数组中。");}}
}

插值查找

和二分查找差不多但是计算mid方式不同，前提是数组数据分布均匀

斐波那契查找

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

分块查找

原则：前一块中的最大数据，小于后一块中所有的数据；块数数量一般等于数组的个数开根号。

先确定要查找的元素在哪一块，然后在块内挨个查找

哈希查找

哈希查找是分块查找的进阶版，适用于数据一边添加一边查找的情况。

一般是数组 + 链表的结合体或者是数组+链表 + 红黑树的结合体

树表查找

二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

排序算法

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。该算法的名称来源于较小的元素会像"气泡"一样逐渐"浮"到列表的顶端。

比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。

交换位置：如果前一个元素比后一个元素大，则交换它们的位置。

重复遍历：对列表中的每一对相邻元素重复上述步骤，直到列表的末尾。这样，最大的元素会被"冒泡"到列表的最后。

缩小范围：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序基本思想是每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部数据排序完成。

初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个列表。

查找最小值：在未排序部分中查找最小的元素。

交换位置：将找到的最小元素与未排序部分的第一个元素交换位置。

更新范围：将未排序部分的起始位置向后移动一位，扩大已排序部分的范围。

重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理类似于整理扑克牌。

插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。

选择元素：从未排序部分中取出第一个元素。

插入到已排序部分：将该元素与已排序部分的元素从后向前依次比较，找到合适的位置插入。

重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

选择基准元素：从列表中选择一个元素作为基准（pivot）。选择方式可以是第一个元素、最后一个元素、中间元素或随机元素。

分区：将列表重新排列，使得所有小于基准元素的元素都在基准的左侧，所有大于基准元素的元素都在基准的右侧。基准元素的位置在分区完成后确定。

递归排序：对基准元素左侧和右侧的子列表分别递归地进行快速排序。

合并：由于分区操作是原地进行的，递归结束后整个列表已经有序。

希尔排序

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

选择增量序列：选择一个增量序列（gap sequence），用于将列表分成若干子列表。常见的增量序列有希尔增量（n/2, n/4, ..., 1）等。

分组插入排序：按照增量序列将列表分成若干子列表，对每个子列表进行插入排序。

缩小增量：逐步缩小增量，重复上述分组和排序过程，直到增量为 1。

最终排序：当增量为 1 时，对整个列表进行一次插入排序，完成排序。

归并排序

归并排序的核心思想是将一个大问题分解成若干个小问题，分别解决这些小问题，然后将结果合并起来，最终得到整个问题的解。具体到排序问题，归并排序的步骤如下：

分解（Divide）：将待排序的数组分成两个子数组，每个子数组包含大约一半的元素。

解决（Conquer）：递归地对每个子数组进行排序。

合并（Combine）：将两个已排序的子数组合并成一个有序的数组。

通过不断地分解和合并，最终整个数组将被排序。

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

创建一个堆 H[0……n-1]；

把堆首（最大值）和堆尾互换；

把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

计数排序

计数排序（Counting Sort）是一种非比较型的排序算法，适用于对整数或有限范围内的数据进行排序。它的核心思想是通过统计每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序的时间复杂度为 O(n + k)，其中 n 是待排序元素的数量，k 是数据的范围大小。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

统计频率：遍历待排序的列表，统计每个元素出现的次数，存储在一个计数数组中。

累加频率：将计数数组中的值累加，得到每个元素在排序后列表中的最后一个位置。

构建有序列表：遍历待排序的列表，根据计数数组中的位置信息，将元素放到正确的位置。

输出结果：将排序后的列表输出。

桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它将待排序的元素分配到若干个桶（Bucket）中，然后对每个桶中的元素进行排序，最后将所有桶中的元素按顺序合并。桶排序的核心思想是将数据分到有限数量的桶中，每个桶再分别排序（可以使用其他排序算法或递归地使用桶排序）。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量

使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

初始化桶：根据数据的范围和分布，创建若干个桶。

分配元素：遍历待排序的列表，将每个元素分配到对应的桶中。

排序每个桶：对每个桶中的元素进行排序（可以使用插入排序、快速排序等）。

合并桶：将所有桶中的元素按顺序合并，得到最终排序结果。

基数排序

基数排序（Radix Sort）是一种非比较型的排序算法，它通过逐位比较元素的每一位（从最低位到最高位）来实现排序。基数排序的核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。基数排序的时间复杂度为 O(n * k)，其中 n 是列表长度，k 是最大数字的位数。

确定最大位数：找到列表中最大数字的位数，确定需要排序的轮数。

按位排序：从最低位开始，依次对每一位进行排序（通常使用计数排序或桶排序作为子排序算法）。

合并结果：每一轮排序后，更新列表的顺序，直到所有位数排序完成。

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；

计数排序：每个桶只存储单一键值；

桶排序：每个桶存储一定范围的数值；