几种排序算法的比较
1.分类:
非线性时间比较类排序:通过比较来决定元素间的相对位置关系,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。
线性时间比较类排序:不通过比较来决定元素间的相对位置关系,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间比较类排序。
2.复杂度
3.算法相关概念
稳定:如果arr[i] = arr[j],i < j,排序后arr[i],arr[j]位置没变化。
不稳定:如果arr[i] = arr[j],i < j,排序后arr[i],arr[j]位置可能发生变化。
时间复杂度:对排序数列的总的操作(比较/赋值等)次数。
空间复杂度:算法在计算机运行过程中所需要存储内存空间的度量。