算法简单介绍【Python实现】

，1、排序算法

排序算法的稳定性，简单来说讲的是相同元素的位置排序完成后次序是否被打乱，若不打乱那么就是稳定的

常见的排序算法有冒泡排序、选择排序、插入排序、希尔排序、快速排序、并归排序

(1)冒泡排序：默认从下到大排序。水滚之后会从底下往上冒泡。冒泡排序的核心也是如此，从第一个开始，从左往右比较并进行移动，就像冒泡一样。所以一轮过后，最右边的就是最大值。

时间复杂度

代码实现，一共N个元素

外层循环是冒泡次数【循环次数j】：n-1次，每循环一次左边即列表中最大值，循环n-1次，n-1个元素即是有序的，即n个元素就是有序的

内层循环是从左到右比较元素的次数【元素索引i，从0开始】,n个乱序的元素需要比较n-1次。所以结合外层循环每次循环完成后嘴右边的元素即是最大值，即是有序的，即还剩下n-j个乱序元素，所以内存循环变量是n-j-1

优化：如果序列是有序的直接退出，最理想情况时间复杂度n

(2)选择排序：默认从小到大排序

选择排序：就是在乱序的序列中选择一个最小值，把这个找到的最小元素放到最左边的过程

时间复杂度

代码实现：

外层循环：找最小值的次数，同上还是进行n-1次。

内层循环：元素比较次数。共有n个未排序的元素，内层循环做的事是从n个元素中获取最小值把它放到最左边

（3）插入算法

插入算法的核心是构造有序序列，选择排序是选择最小值，而插入算法从左到右遍历每个元素，并把它插入到正确位置使得元素排列有序

时间复杂度

代码实现

外层循环：外层循环是遍历元素，每遍历一次，在有序序列中插入一个值。原始有序序列只有一个元素，遍历n-1次都插入n-1个值。即整个序列有序

内层循环：内层循环是拿要插入的元素与已经有序的序列进行比较并插入

插入算法的代码实现2【优化版】

【注】在已经有序的序列中，while循环体里面的if语句判断的是最后一个元素即最大值，所以if条件不满足里面的 语句都没执行，直接执行else后面的语句。即复杂度是1.所以对于升序排列的有序序列时间复杂度是o(n)

(4)希尔排序

希尔排序：将一个长序列打断，分成多个子序列，然后分别对子序列进行排序的反复过程。最后将子序列合成一个序列即完成了排序。那么问题来了，如何打断呢。大家知道range函数吧，它里面有个步长的概念。这里也一样按步长根据下标取元素进行分组，直到把所有元素都分到子序列中，对子序列排序，然后合并成长序列。然后改变步长重复此过程

简单理解：希尔排序其实就是插入排序，普通的插入排序插入元素的间隔是1，希尔排序排序插入间隔是由程序控制。

后

时间复杂度：

【注】最坏时间复杂度即gap取1的时候

代码实现

方式1：

外层循环：表示要排序的元素

内层循环：表示向已经有序的队列插入元素，不同的是现在有序的序列不是一个，而是多个子序列。

方式2：内层循环采用while循环，终止条件是元素索引等于0则停止，这种方式理解比较简单。不用计算内层循环遍历的时候有多少元素是有序的

（5）快速排序：查看排序算法之快速排序

（6）归并排序：查看排序算法之归并排序

2、搜索算法

搜索的几种常见算法：

顺序查找：指的是我们平常的查找算法，就是常见的通过遍历集合中所有查找

二分法查找

【注】待查找的序列是有序的，序列是存在索引的。所以二分查找只能用于有序的顺序表

错误代码

修正后代码如下，递归调用的时候要设置函数返回值

时间复杂度

二分查找时间复杂度

二叉树查找

哈希查找