排序可视化

选择排序

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