插入排序(上):直接插入排序,插入排序直接插入

2019-11-07 作者:计算机教程   |   浏览(167)

插入排序(上):直接插入排序,插入排序直接插入

  1. 思想

直接排序法, 可以分为两个部分, 一部分是有序的, 一部分是无序的.

图片 1

从这个图上, 应该是能看清楚直接插入排序的思想了.

将无序部分的第一个与有序部分进行比较.

从有序部分的后面向前面比较, 然后不断地挪动有序部分的数据的位置

static void InsertSort(List<int> list)
{
    for (int i = 1; i < list.Count; i  )
    {
        int temp = list[i];
        int j = i;
        while (j >= 1 && temp < list[j - 1])
        {
            list[j] = list[j - 1];
            j--;
        }
        list[j] = temp;
    }
}

 

  1. 复杂度

直接插入排序的最好情况下, 时间复杂度为O(n), 最坏情况下, 复杂度为O(n2);

证明见:

插入排序及其复杂度分析

 

  1. 直接插入排序vs快速排序

图片 2

 

http://www.bkjia.com/C_jc/1204690.htmlwww.bkjia.comtruehttp://www.bkjia.com/C_jc/1204690.htmlTechArticle插入排序(上):直接插入排序,插入排序直接插入 1. 思想 直接排序法, 可以分为两个部分, 一部分是有序的, 一部分是无序的. 从这个图上, 应...

本文由www.2003.com发布于计算机教程,转载请注明出处:插入排序(上):直接插入排序,插入排序直接插入

关键词: