排序算法小结

1.插入排序：直接插入排序，二分插入排序，希尔排序。

直接插入排序：直接插入排序就是将未排好序的元素向已经排好序的序列中插入。开始时只有一个元素是有序的，即第一个元素a[0]，然后把第二个元素插入，在有序序列中寻找自己的位置。

二分插入排序：可以看到插入排序的时间代价主要消耗在比较次数太多以及节点的移位上。二分插入排序就是在寻找待排序元素的正确插入位置时采用二分查找的方法来查找，因为已经排好序的序列是有序的。但是时间复杂度仍然是n的平方。

希尔排序：二分插入排序通过减少比较的次数来提高排序效率，希尔排序通过减少移动次数来提高排序效率。希尔排序的思想主要是：先比较那些离得稍远些的元素，如果稍远的元素违背了排序的次序，就根据普通插入排序排列这些元素。然后在减小间距，直到排序的间距为1.使所有的元素都有序。他的时间复杂度是优于n的平方的。

2.选择排序：直接选择排序，堆排序。
直接选择排序：就是在所有的序列中选出最小的元素，然后选出第二小的元素，以此类推，所有的序列都变得有序。时间复杂度是n的平方。

堆排序：在优先队列中我们使用了最大化堆（完全二叉树的父节点比两个子节点都要大，但是子节点之间没有大小关系）。第一步将待排序元素创建成为一棵最大化堆或者最小化堆，第二步依次将树根删除就可以得到有序序列。时间复杂度为nlog(n)。

3。交换排序：冒泡排序，快排
冒泡：将一个元素和它旁边的元素比较，如果比它大，就交换，这样经过一轮冒泡，最大或者最小的元素被放到了最后，当然，如果经过那一轮排序发现没有元素移动，就可以判断这个序列已经是有序的，从而可以终止排序。
快排：选择一个元素作为中间元素，然后将其他的元素跟它比较，比它大的放到后面，比它小的放到前面，从而就找到了中间这个元素的最终位置。使用递归的方式再对其前面和后面的元数据排序。如果中间的元素选择的好，可以使排序的时间复杂度很好。