InsertionSort（插入排序）原理及C++代码实现

插入排序是最常用的排序之一。

在输入规模较小的时候，插入排序的性能较好。

最好情况下插入排序的时间复杂度是O(n),平均情况则为O(n2)。

插入排序是稳定的排序算法之一。

基本思路为从第二个元素开始，依次插入前面已经排好序的序列，利用循环不变式很容易理解。

代码如下：（仅供参考）

 void InsertionSort(int * const begin, int * const end) {

     int i, j;

     int key;

     for (i = ; i < end - begin; ++i) {

         key = *(begin + i);

         for (j = i - ; j >=  && (*(begin + j) > key); --j) {

             *(begin + j + ) = *(begin + j);

         }

         *(begin + j + ) = key;

     }

 }

注：指针需要支持随机访问

巴特西

InsertionSort（插入排序）原理及C++代码实现

最新文章

热门文章