数据结构与算法笔记：二
数据结构与算法笔记：三（大结局） | Zippera’s blog
#Sorting
- Comparison Sorting
- Bubble Sort: 从头到尾，两两比较，若>，则交换，再往后比较；实际上就是传递大个，从头往后，遇到大个就让大个往后走，直到最大的挪到最后面。然后从头开始第二遍，一直到倒数第二个…每一次遍历，确定队尾部分的一个元素。
- Selection Sort: 有一个 min 指针，先指向第一个，然后依次与后面的比较，如果>，则 min 挪到该出，再继续往后比较，直到最后，然后把 min 处和开始处交换，这样就得到了第一个最小的。第二次，从第二个开始，重复上述过程。每一次遍历，确定队首部分的一个元素。
- Insertion Sort： 从头到尾，依次把当前元素插入到前面合适的位置，插入时从后往前比较，前面的部分已经有序，但不是最终结果。这样，走到最后，就排序成功了。
- Shell Sort：希尔排序，第一次以 d1为步长对列表分段，每个片段里对应元组排序；第二次以 d2（<d1）为步长…最后一次以1为步长。维基百科的分组表示形式也很直观容易理解。
- Merge Sort：归并排序，排序的操作为：1-2，3-4，1-4；5-6，7-8，5-8；1-8；9-10，11-12。。。也就是说，从左到右，把2个排好，再来2个，拍前4个；后面再找4个，像前面一样递归排序；然后合并这8个，再找8个，像前面一样递归排序。。。
- Quck Sort：快速排序，稍微复杂，这篇文章给出一个直观的描述，叫「挖坑填数+分治法」非常好。首先让 i 指向第一个，j 指向最后一个，挖走第一个数存在 X；从 j 开始向左找到一个小于 X 的数，挖走放在刚才的坑，形成新坑；从 i 开始向右找到一个大于 X 的数，挖走放在上一个坑，形成新坑，再从 j 开始向左找。。。直到i 和 j 相遇，把 X 放在最后一个坑中。这时左边都比 X 小，右边都比 X 大。这样，我们就用 X 把原问题划分了一下，左边和右边。第二次就用同样的方法分治 X 左边的和 X 右边的，用递归调用方法。如图：
Bucket Sort：桶排序。先创建一个同样大小的数组，把待排序数组中的数 Hash（Open Hash） 到这个数组， 形成的新数组中从左到右是有序的，每个位置的链表也是有序的。第二步是从左到右遍历，把元素都放回去。这种方法特别快，但耗空间。截图如下，非常直观：
Counting Sort：计数排序，很有技巧很好玩。这篇文章讲的很好理解：整个过程分为拉选票和入桶两个过程。投票完毕是这样的：
待排数组[ 6 2 4 1 5 9 ]
票箱数组[ 4 1 2 0 3 5 ]
带排数组中每个元素，比如6，要拉票，所有小于我的都给我投票，所以一共4票。其他元素依次拉票，票箱数组显示了最终拉到的票数。第二步就是入桶：
入桶后 [ 1 2 4 5 6 9 ]
6有4票，入的是4号桶；2有1票，入的是1号桶，以此类推。
（有重复数字怎么处理，日后再研究）Radix Sort：基数排序，按照个位数用上述计数排序方法（或其他稳定排序方法）排好，在此基础上按照十位数排序，依次类推。
Heap Sort：堆排序，利用小顶堆的特点进行排序。在堆调整的过程中同时对数组中的元素调整顺序。堆调整完毕，数组就排序完毕了。如图：
这阵子复习准备考试，时间比较紧，少写一点。