排序速度最快的算法
终极管理员 知识笔记 128阅读
快速排序算法时间复杂度是多少？
答：quick_sort (arr , p , par-1) // 将 [p , par-1] 作为待排序序列，重复进行分割 quick_sort (arr , par+1 , q) // 将 [par+1 , q] 作为待排序序列，重复进行分割 最坏情况下，快速排序算法的时间复杂度为 O (n 2) ，理想状态对应的时间复杂度为 O (nlogn) 。
快速排序算法的实现思路是什么？
答：快速排序算法的实现思路是： 从待排序序列中任选一个元素（假设为 pivot）作为中间元素，将所有比 pivot 小的元素移动到它的左边，所有比 pivot 大的元素移动到它的右边；
什么是排序算法？
答：因为 排序算法 的基本步骤就是比较两个元素的大小，至于这两个元素是整数，浮点数，还是其他什么有序集合，对于计算机而言并没有什么区别，因为数据在计算机内部都是用二进制数字表示的。 而不同 排序算法 的效率之所以有那么大的差异，是因为它们在设计比较方式上有明显的不同。
归并排序算法为什么这么快？
答：这个算法之所以快，是因为它充分利用了现实世界的待排序数据里面，有很多子串是已经排好序的不需要再重新排序，利用这个特性并且加上合适的合并规则可以更加高效的排序剩下的待排序序列。 当Timsort运行在部分排序好的数组里面的时候，需要的比较次数要远小于 n l o g n ，也是远小于相同情况下的归并排序算法需要的比较次数。 但是和其他的归并排序算法一样，最坏情况下的时间复杂度是 O ( n l o g n) 的水平。 但是在最坏的情况下，Timsort需要的临时存储空间只有 n / 2 ，在最好的情况下，需要的额外空间是常数级别的。 从各个方面都能够击败需要 O ( n) 空间和稳定 O ( n l o g n) 时间的归并算法。 OK！