排序算法--如何分析、评价一个排序算法的优劣
学习排序算法感觉有种回到高中做数学题的感觉,需要深入的理解这些排序算法,才能真正的掌握它。
如何评价、分析一个排序算法?
一)、排序算法的执行效率
如何来评估排序算法的执行效率呢
1、最好情况、最坏情况、平均情况的时间复杂度
对于要排序的数据,有的接近有序,有的完全无序,而排序数据的有序度会影响算法的执行时间,我们需要知道排序算法在不同数据下的性能表现
2、时间复杂度的系数、常量、低阶
时间复杂度是随规模n增长的变化趋势。但对于规模很小的数据,如:10,20个这样的数据,那么我们需要将这些因素考虑进来
3、比较次数和交换(或移动)次数
基于比较的排序算法,其执行过程会设计到两种操作:a、元素之间的比较。b、元素之间的交换或者移动。
二)、排序算法的内存消耗
算法的内存消耗可以通过空间复杂度来衡量。空间复杂度为O(1)的排序算法成为原地排序
三)、排序算法的稳定性
稳定性:如果待排序的序列中存在元素相等的数据元素,经过算法排序之后,相等元素之间原有的先后顺序不变。
如果相等元素经过排序后,其先后顺序没有发生了改变,那么称其为稳定排序算法
如果相等元素经过排序后,其先后顺序发生了改变,那么称其为不稳定排序算法
简而言之:我们可以通过时间复杂度,空间复杂度以及稳定性来衡量一个排序算法的优劣。但也要根据实际情况来决定,如果你不需要考虑内存消耗的话,也可以通过消耗内存,即提高空间复杂度来提升排序算法的执行效率。
本来想把排序算法放到一遍博客中学习,详述完的。想了一下,还是决定分为四篇来总结学习,接下来三篇分别是
时间复杂度为O()的排序算法:冒泡排序、插入排序、选择排序
时间复杂度为O()的排序算法:归并排序、快速排序
时间复杂度为O()的排序算法:桶排序、计数排序、基数排序
这里推荐两个网址,可以通过这两个网址观察排序算法的动态图,加深对排序算法的理解
https://mp.weixin.qq.com/s/HQg3BzzQfJXcWyltsgOfCQ
参考:数据结构与算法之美--王争