为什么插入排序比对排序数组进行快速排序要快

本文介绍了为什么插入排序比对排序数组进行快速排序要快的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在将插入排序与快速排序进行比较.我已经弄清楚了为什么在几乎排序的数组上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.