排序算法###

最近打算重新看看算法的知识，之前上算法课的时候很多知识没有研究，考完试就忘掉了。排序算法是算法当中比较基础的问题，今天看到这的时候突然萌生了了一种算法可视化的想法，于是二话不说，就用代码撸了个效果出来。其中牵涉到的排序算法有冒泡排序、快速排序、插入排序、选择排序、希尔排序。

冒泡排序###

为啥叫冒泡排序呢？其实直接说也不太好说，等会上效果图就能很清楚直观地看出效果。比如下面这组数据要实现从小到大排序：
**12 35 99 18 76 **

1. 逐个扫描数字，比较相邻两个数字，如果左边比右边大的话就交换，这样第一趟扫描结束后，最大的数会被移到最右边。结果为：12 35 18 76 99
2. 第二趟扫描，由于最大的99已经在最后边了，只要在之前4个中继续使用这种方法找到这4个数中最大的就完成了。这样第二大的数字会被移到99的左边。结果为：**12 18 35 76 99 **
3. 同理继续扫描，直到未排序的只剩一个数字时，排序就搞定了。

图像中每个点的x坐标代表数组下标；y坐标是随机数字，即数组下标对应的数组值。比如一个之前那个数组12 18 35 76 99 可以转化成坐标(0,12)(1,18)(2,35)(4,76)(5,99)当然这个y坐标我在显示的时候都乘上了10，不然点全挤在一起了。以100个数据为例，最终效果如下：

冒泡排序

可以看到很多数据像泡泡一样在浮动，当我第一次看到这个效果时确实觉得这个算法名字与效果名副其实。

冒泡算法的几个改进：
1.增加标志位，排序过程中，未排序数据中局部已经有序，其实并不需要那么多次循环，而只需要几次交换就能达到目的。
2.一次冒两个元素，既然一趟扫描能找出最大的数，那么能否顺便找出最小的数呢？

选择排序###

选择排序与冒泡排序其实有共同点，大致思想是差不多的。举个栗子：**99 12 35 18 76 **

1. 第一次扫描，从左到右扫描，找出数组中最小值的下标，将这个数与第一个数交换，变成**12 99 35 18 76 **
2. 第二次扫描，从第二个数开始扫描（第一个已经排序），扫描后面4个数，找出最小值，与第二个数对换（如果最小值就是第二个那么不用对换）。变成**12 18 99 35 76 **，以此类推。

选择排序的可视化效果如下：

选择排序.gif

选择排序改进###

选择排序每次扫描只会找出最小值，同冒泡算法改进思想一样，是否可以一次扫描同时找出最大值与最小值呢？当然是可以的，只是需要注意的是：同时找出最大值与最小值意味着有两次交换，这就会出现这样的问题，举个栗子，如果在第一次扫描后找到最大值99和最小值12：12 76 18 35 99，第二次扫描时，找到最大值下标是1（76），找到最小值下标是2（18），如果先换最小值，那么会变成12 18 76 35 99，这时如果再换最大值，那么则会将下标为1（18）与下标为3（35）对换，那么变成了这样：12 35 76 18 99，看看，问题出来了吧。所以我在处理最小值交换的时候会判断一下最大值是否处于即将被交换的位置，如果是的话，交换之后要保存一下新的最大值的下标。
这种改进算法的可视化效果如下：

选择改进.gif

可以看到与选择排序相比，改进版从两边同时往中间排序，效率要比选择算法稍微快一些。

插入排序###

所谓插入排序，最大的特点就是，如果a是当前扫描的数字，那么a左边是已排序的数列，右边是未排序的数列。比如：12 18 35 85 76 99 83。76左边是有序（从小到大）的，76右边则是无序的，对于76来说，只要把76插入到左边的数列合适的位置中就可以了，变成12 18 35 76 85 99 83。然后便是对99进行同样的操作。

插入排序的可视化效果：

插入排序

可以明显看到排序过程中，左边一直是有序的，而右边则是无序的。

快速排序###

快速排序的特点就是递归的思想，对于一个数列，首先选择第一个数字作为基准，使用i和j两个游标，将基准数移到标准位置。所谓标准位置，就是基准数左边的数都小于等于它，右边的数都大于等于它（比如：12 18 35 76 76 99 83 79 86）。这样就把数列分成了两个部分，再分别对两个部分数列使用同样的方法，直到排序完成。

快速排序可视化效果图如下：

快速排序.gif

希尔排序###

哇QAQ，这个是最难理解的，说实话有点复杂，我不想敲了>_<，直接看这篇吧->希尔排序

可视化效果图如下：

希尔排序.gif

总结###

说实话，这么多排序算法，在没做这个图之前想完全区别还是有点小难度，但有了这样的可视化效果后，对算法的理解也更深了一步，还是有点小欣慰的。宿舍断电仍然坚持敲完了，给自己点个赞嘿嘿！