出国留学网排序算法总结

出国留学网专题频道排序算法总结栏目,提供与排序算法总结相关的所有资讯,希望我们所做的能让您感到满意!

排序算法总结

 

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

  【排序算法总结】

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

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

  稳定性:让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的,当有俩个相等键值的记录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...