排序算法--如何分析、评价一个排序算法的优劣

排序算法--如何分析、评价一个排序算法的优劣

学习排序算法感觉有种回到高中做数学题的感觉,需要深入的理解这些排序算法,才能真正的掌握它。

 

如何评价、分析一个排序算法?

一)、排序算法的执行效率

如何来评估排序算法的执行效率呢

1、最好情况、最坏情况、平均情况的时间复杂度

     对于要排序的数据,有的接近有序,有的完全无序,而排序数据的有序度会影响算法的执行时间,我们需要知道排序算法在不同数据下的性能表现

2、时间复杂度的系数、常量、低阶

   时间复杂度是随规模n增长的变化趋势。但对于规模很小的数据,如:10,20个这样的数据,那么我们需要将这些因素考虑进来

3、比较次数和交换(或移动)次数

基于比较的排序算法,其执行过程会设计到两种操作:a、元素之间的比较。b、元素之间的交换或者移动。

二)、排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量。空间复杂度为O(1)的排序算法成为原地排序

三)、排序算法的稳定性

稳定性:如果待排序的序列中存在元素相等的数据元素,经过算法排序之后,相等元素之间原有的先后顺序不变。

如果相等元素经过排序后,其先后顺序没有发生了改变,那么称其为稳定排序算法

如果相等元素经过排序后,其先后顺序发生了改变,那么称其为不稳定排序算法

 

简而言之:我们可以通过时间复杂度空间复杂度以及稳定性来衡量一个排序算法的优劣。但也要根据实际情况来决定,如果你不需要考虑内存消耗的话,也可以通过消耗内存,即提高空间复杂度来提升排序算法的执行效率。

 

本来想把排序算法放到一遍博客中学习,详述完的。想了一下,还是决定分为四篇来总结学习,接下来三篇分别是

时间复杂度为O(排序算法--如何分析、评价一个排序算法的优劣排序算法--如何分析、评价一个排序算法的优劣)的排序算法:冒泡排序、插入排序、选择排序

时间复杂度为O(排序算法--如何分析、评价一个排序算法的优劣)的排序算法:归并排序、快速排序

时间复杂度为O(排序算法--如何分析、评价一个排序算法的优劣)的排序算法:桶排序、计数排序、基数排序

 

这里推荐两个网址,可以通过这两个网址观察排序算法的动态图,加深对排序算法的理解

https://mp.weixin.qq.com/s/HQg3BzzQfJXcWyltsgOfCQ

https://visualgo.net/en

 

参考:数据结构与算法之美--王争