选择排序
select.gif
插入排序
insert.gif
归并排序
mergeSort.gif
快速排序
最基础的快排
每次确定数组的第一个元素作为基准值，然后通过比较和交换，基准值左面的元素都小于基准值，基准值右面的元素都大于基准值（这样基准值所处的位置即为排好序他应该待着的位置），然后，将数组分为三部分，即，基准值左面，基准值，基准值右面，分别进行左右递归，处理剩下的元素。
quickSort.gif
随机基准值快速排序
上面的排序对于处理无序的数组非常好，但是有很多问题，如果排序数据本身就是趋于有序的，因为每次都是选取当前数组的第一个元素作为基准值，该基准值的位置在没有进行排序之前就处于合适的位置，即，左面的元素小于基准值，右面的元素大于基准值，导致每次进行比较和交换的时候都是遍历整个数组，将时间复杂度拖至O(n)^2.
quickSort1.gif
解决办法
每次通过一个随机数作为基准值的索引下标，然后将该值和数组的第一个元素交换为值即可。
quickSort2.gif
二路快速排序
如果排序的数据大致相同，快速排序算法又会退化到O(n^2)。
quickSort3.gif
解决办法
image.png
image.png
为了避免频繁的交换，在基准值的后面和数组的最后一个位置分别戳一个指针i,j，i指针向后遍历，直到找到大于等于基准值的位置，j指针像前遍历找到小于基准值的位置，然后i,j指针交换各自的元素，i,j继续遍历直到i>j，交换j和基准值的位置。完成一次排序
quickSort4.gif
三路快速排序
二路快速排序虽然可以解决重复元素的问题，但是仍然还是对重复的元素有相同的处理，为了不再频繁的处理相同的元素，算法再次改进。
三路排序的主要思路是将和基准值的相同的元素归置到一块。下次进行分割数据的时候，不再处理和基准值相同的元素。
image.png
image.png
quickSort5.gif
三路快排测试普通用例
quickSort6.gif
堆排序
heap.gif
代码详见github
网友评论