算法杂记（算法学习）

简单排序：

冒泡排序

原理：

冒泡排序（Bubble Sort）是一种简单的排序算法。它的基本原理是通过反复比较相邻的元素，如果顺序错误就把它们交换过来，就像气泡在水中逐渐上浮一样，每一轮比较都会将当前最大（或最小）的元素 “浮” 到数组的一端。

具体实现步骤：

冒泡算法每次比较相邻的两个数据，每次比较一轮可以将一个数字排序完成，多次冒泡之后完成排序。

选择排序

原理：

1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引处的值为最小值，最后可以找到最小值所在的索引

2.交换第一个索引处和最小值所在的索引处的值。

具体实现步骤：

假设要对数组[5,4,3,2,1]进行排序。在第一轮排序中，需要在整个数组中找到最小的元素。通过比较，发现最小的元素是1。

然后将与数组的第一个元素进行交换，此时数组变为[1,4,3,2,5]。这样，第一轮排序就将最小的元素放到了数组的最前面。

按照同样的方法，在每一轮排序中，都从剩余的未排序元素中选择最小的元素，并将其与当前轮次未排序部分的第一个元素交换。经过n-1轮排序（n是数组的长度）后，数组就会完全有序。

冒泡排序和选择排序的对比：

我们提到的比较主要是从时间复杂度进行比较的：

冒泡排序：最坏和平均情况下时间复杂度为O(n2)。这是因为在比较次数和交换次数在最坏和平均情况下都是

n(n-1)/2，这是一个关于n的二次函数。最好情况下时间复杂度为O(n),当数组已经有序时，只需要进行一轮的比较，每次比较都不产生交换。

选择排序：时间复杂度始终为O(n2)。无论数组的初始顺序如何，比较次数总是n(n-1)/2，交换次数为n-1，整体的时间复杂度是关于n的二次函数。

二者的优缺点对比以及适用场景

二者的优点呢，都是比较容易实现，容易理解；同样缺点也相似：时间复杂度高，不适用于处理大量数据。

冒泡排序适用场景：

• 小规模数据排序：对于数据量较小的数组，如小于 100 个元素的情况，冒泡排序的性能下降不明显，代码简单的优势更加突出。例如，对一个班级学生的几次小测验成绩进行排序，或者对一个小型游戏中的排行榜进行简单排序等。

• 作为教学示例：由于其简单易懂的特性，非常适合用于教学排序算法的基本概念。在计算机科学的入门课程中，帮助学生理解排序的思想和循环、条件判断等基本编程结构的应用。

选择排序适用场景：

• 小规模数据排序且对稳定性要求不高：对于数据量较小（如小于 100 个元素），并且不关心相同元素相对位置是否改变的情况，选择排序可以作为一种简单的排序方法。例如，在一些简单的嵌入式系统或者对排序结果稳定性没有要求的小程序中，对少量数据进行排序。

• 简单硬件环境或对交换操作敏感的场景：如果在某些硬件设备上，数据交换操作的开销很大，而比较操作的开销相对较小，选择排序由于其相对较少的数据交换次数，可能会比其他一些排序算法更合适。不过这种场景相对比较少见。

插入排序

原理：

插入排序，主要就是将一组数分为已排序和未排序，每次将一个未排序的数倒叙与已插入的数进行比较，如果比最后一个数还小，则交换位置，如果比最后一个数大，就放在末尾。

时间复杂度：

O(n^2)

三种算法的对比：

每种算法的时间复杂度都是O(N^2)，都只适合进行少量数据的排序，大量数据的话会导致执行次数大幅度上升。

高级排序：

希尔排序(了解即可)：

希尔排序呢就是插入排序的进阶版

递归算法：

概念：定义方法时内部调用它本身。

作用：它通常把一个大型复杂的问题，层层转换为一个与原问题相似的，规模较小的问题来解决。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复的计算，大大地减少了程序的代码量。

如果递归的数据过大，那么会出现栈内存溢出的异常：StackOverflowError(栈内存溢出异常)。

归并算法：

概念：

• 归并算法（Merge Sort）是建立在归并操作上的一种有效的排序算法。它采用分治法（Divide and Conquer）的策略，将一个数组分成两个子数组，对每个子数组进行排序，然后将排好序的子数组合并成一个最终的排序数组。

每次填充进行对应指针比较，小的数据排在辅助数组（assist）对应的位置上，然后对小的数组的指针进行后移，直到两个数组的所有元素的数据比较完成。