排序算法总结

　　排序算法是什么?有多少种?排序算法总结又是怎样?以下是留学网为您整理的排序算法总结，供您参考!

　　【排序算法总结】

　　排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。

　　排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。

　　稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。

　　以下来总结常用的排序算法，加深对排序的理解。

　　冒泡排序

　　原理

　　俩俩比较相邻记录的排序码，若发生逆序，则交换;有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

　　性能

　　时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。

　　优化

　　若初始序列就是排序好的，对于冒泡排序仍然还要比较O(N^2)次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。

　　代码

　　插入排序

　　原理

　　依次选择一个待排序的数据，插入到前边已排好序的序列中。

　　性能

　　时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。

　　优化

　　直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。

　　折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。

　　使用场景

　　当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

　　代码

　　希尔排序

　　原理

　　插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：

　　插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。

　　但插入排序在每次往前插入时只能将数据移动一位，效率比较低。

　　所以希尔排序的思想是：

　　先是取一个合适的gap

　　缩小间隔gap，例如去gap=ceil...