常见排序及查找算法

内容引用自：
【数据结构和算法】十大经典排序算法（动图演示）

1.1、动图演示

• 遍历列表数据，共遍历length(列表)次，每一次的遍历都要从左到右进行两两比对，左边比右边小，那么值就调换，否则进行往后两位的比对值；
• 每遍历一次，可以得到一个最大值（第一次遍历时最大值，后面遍历得到的应该叫次最大值）

1.2、代码

2.1 、核心思想：

1. 在待排序的元素任取一个元素作为基准(通常选第一个元素(arr[left])，称为基准元素(pivot)，）
2. 将待排序的元素进行分块，比基准元素大的元素移动到基准元素的右侧，比基准元素小的移动到作左侧，从而一趟排序过程，就可以锁定基准元素的最终位置
3. 对左右两个分块重复以上步骤直到所有元素都是有序的（递归过程）

（选取pivot基准，双指针left和right分别指向第一个元素和最后一个元素，与基准进行比较，right比基准大就往左移动，否则和left位置的元素替换位置，left的往右移动，重复刚才工作，
直至双指针指向同一个位置，这样就把基准元素位置确定了，之后递归遍历基准元素的左右两边的元素即可实现排序；）
时间复杂度最好：o(nlogn) 当输入数组已经完全有序或几乎有序时最差o(n^2)
空间复杂度：最好：o(logn) 最差o(n)

2.2、静态图（来源：图解快速排序），动图不那么好理解：

2.3、代码：

2.4、结果：

3.1、核心思想

选择排序(Selection-sort)是一种简单直观的排序算法。
它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

3.2、动图演示

3.3、代码

4.1、核心思想

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

4.2、动图演示

4.3、代码

结果：

5.1、思想

来源：归并排序（Merge Sort）图解，归并排序算法-学到牛牛
归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法采用非常经典的分治法（分治法可以通俗的解释为:把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化），归并排序的思路很简单，速度呢，也仅此于快速排序

基本思路：

第一步：将序列中待排序数字分为若干组，每个数字分为一组。

第二步：将若干组两两合并，保证合并的组都是有序的。

第三步：重复第二步的操作，直到剩下最后一组即为有序数列。

详细步骤：

5.2、代码