选择、插入排序主要要点

选择、插入排序主要要点

回忆冒泡排序：

现在想想冒泡排序是不是很简单？

确定冒泡趟数；

确定冒泡次数，每完成一趟，有序区增加一个数，无序区减少一个数；

每天趟就像是在无序区中（没有排成升序），有一个指针从第一个数到无序区的最后一个数，两两之间比较，调整。循环嵌套就解决了。

接下来：我们来看一看选择排序：
大致过程：
我们是不是可以从一个列表中依次选择一个最小的数，挨个出数，然后把它排成一列就好。

首先，来看基础的选择排序（创建一个空列表来存依次最小的数，每存一个数就删除在原来的这个列表的位置，然后调整）

代码：

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

注意：这种选择排序的写法不是很好。首先，创建了两个列表，内存消耗太多;其次，要对原列表执行删除 调用min（）时间复杂度就O(n)了 ，还要删除原列表每次对应的最小值，改变元素的下标又是一次遍历。

选择排序
原理：

首先将列表的第一个数存下来，那么在它右边的数据是不是就可以叫做无序区了；

接着我们通过循环遍历的方法找到无序区的最小值，将那个在无序区中找到最小的数的下标赋值给有序区最右边的下标进行修改，每次选一个最小值，直到最后一个数（这个数已经是最大的了，就不需要在来一趟排序了）

注意：
一趟排序记录最小的数，放到第一个位置上；

再将排序记录的列表无序区最小的放在第二个位置上；

最重要的就是将i先赋值给min_ind先存起来 让min_ind得到最小数的下标，每趟后交换list[i]和list[min_ind]的值 min_ind的设置巧妙，作用：依次和无序区的数进行比较 得到最小数的小标。

code following:

 结果演示：

 选择排序算法的关键点：

依次求得最小的数；
有序区和无序区；

细节：

将有序区的最后一个下标（对应代码中的i）和无序区最小的数进行比较；

if找不到就和自己做交换，如果找到了就将j的下标赋给min_ind再将list[min_ind](真正的最小值)进行交换。

选择排序的时间复杂度：
两层循环,   O(n^2)

插入排序：

就像是我们打牌的时候握在手里排（3 4 8 9） 再摸一个5 我们会本能地将5插在4后面！

 细节解释:
分为手里的牌（有序区） 摸的牌（无序区），每次拿摸的牌和手里的牌比较；

如果手里的牌大就往后移，同时改变手里牌（往左指） 最后将摸到的牌填到移动了的牌的后面；

如果手里的牌小，就让摸得牌写到手里牌之前的位置；

总之：手里牌大玩往后面走，循环继续判断 再将摸得牌补起 （当检测到摸的牌比手里的牌大就结束循环）。

笔记：

 插入排序的时间复杂的依然是：O(n^2)!!!

冒泡选择插入时间时间复杂度都是：O(n^2)

你们的每一个赞都是我创作道路上最值得的收获，欢迎评论谢谢！