基本算法 | 计算机基础

8.4 基本算法

设置最大值为数据类型的最小值。
对一个数值进行比较，如果大于现有最大值，则保留较大的值为现有最大值。
循环比较每一个数值。

设置最小值为数据类型的最大值。
对一个数值进行比较，如果小于现有最小值，则保留较小的值为现有最小值。
循环比较每一个数值。

排序：根据数据的值对他们进行排列。
如果数据是无序的，需要花大量的时间去查找信息，并且下一次查找仍然要花费大量时间。

基本排序算法：

在选择排序中，数字列表分为两个子列表：已排序的和未排序的，通过一个假想的墙分隔开。
首先求未排序字列表中最小的元素，并把它和未排序列表中第1个元素进行交换。这样假想的墙向前移动1个元素。已排序列表中增加1个元素，未排序列表中减少1个元素。
循环进行这样的操作，直到进行到最后1个数字。

选择排序示例

原列表：23，78，45，8，32，56

选择排序的轮数比该列表中元素的个数少1。
使用两层循环，外层循环每次扫描时迭代1次，内层循环在未排序列表中求最小的元素。

时间复杂度： $O(n^2)$

在冒泡排序方法中，数字列表分为两个子列表：已排序的和未排序的。在未排序子列表中，最小的元素通过冒泡的方法选出来，并移到已排序子列表中。
当把最小的元素移到已排序列表后，墙向前移动1个元素，使得已排序元素个数增加1个，未排序元素个数减少1个。

冒泡排序举例

原列表：23，78，45，8，32，56

对于含有n个元素的列表，冒泡排序需要n-1轮来排序。
冒泡循环也使用两层循环。
通常在算法中包含一个指示器，如果在一轮中没有数据交换，那么说明顺序已经排好，结束算法。

时间复杂度： $O(n^2)$

在插入排序中，数字列表分为两个子列表：已排序的和未排序的。在每一轮中，把未排序子列表中的第一个元素转移到已排序子列表中，并且插入合适的位置。

插入排序举例

原列表：23，78，45，8，32，56

插入排序是最常用的排序算法之一。
插入排序同样需要n-1轮排序。

时间复杂度： $O(n^2)$

在列表中确定目标所在位置的算法。
在列表中，查找意味着给定一个值，并在包含该值的列表中找到第一个元素的位置。

对于列表有两种基本的查找方法：

顺序查找通常用来查找较小或者不常用的列表。
通常情况下，首先应将列表排序，然后使用折半查找进行查找。

顺序查找是从列表起始处开始查找，当找到目标元素或确认查找目标不在列表中时，查找过程结束。

时间复杂度： $O(n)$

顺序查找举例

折半查找是从一个列表的中间元素来测试，这样能够判别出目标在列表的前半部分还是后半部分。这样可以通过判断减少一半的列表。
重复这个过程指导查找到目标或者目标不在这个列表里。
折半查找需要用三个变量first，mid，last来确定查找范围。

时间复杂度： $O(logn)$

折半查找举例