为什么插入排序比对排序数组进行快速排序要快 [英] Why is insertion sort faster than quick sort on a sorted array

问题描述

我正在将插入排序与快速排序进行比较.我已经弄清楚了为什么在几乎排序的数组上qsort变慢了，但是我无法弄清楚为什么插入排序这么快，为什么肯定还要比较数组中几乎一样多的元素?

I'm comparing insertion sort with a quicksort. I've figured out why the qsort is slower on an almost sorted array but I cant figure out why the insersion sort is so much quicker, surely it still has to compare nearly as many elements in the array?

推荐答案

在排序或近乎排序的数组上插入排序更快的原因是，当将元素插入到数组的排序部分时，它几乎不必移动根本没有任何元素.例如，如果数组的排序部分是1 2，下一个元素是3，则只需进行一次比较-2 < 3-确定不需要移动3完全没有.结果，对已排序数组的插入排序是线性时间，因为它只需要对每个元素进行一次比较.

The reason that insertion sort is faster on sorted or nearly-sorted arrays is that when it's inserting elements into the sorted portion of the array, it barely has to move any elements at all. For example, if the sorted portion of the array is 1 2 and the next element is 3, it only has to do one comparison -- 2 < 3 -- to determine that it doesn't need to move 3 at all. As a result, insertion sort on an already-sorted array is linear-time, since it only needs to do one comparison per element.

这篇关于为什么插入排序比对排序数组进行快速排序要快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！