数据结构教程--李春葆版（总结）之排序-插入排序

待我称王封你为后i 2022-01-05 11:13 126阅读 0赞

### **本文的主要内容来自数据结构教程--李春葆版，由“你是木头人”博主进行总结。** ###

### 插入排序 ###

**性质**：每次将一个待排序的元素，按其关键字大小插入到已经排好序的子表中的适当位置，直到全部元素插入完成为止。

### 直接插入排序 ###

//直接插入排序-稳定
    typedef struct
    {
    int key;
    }RecType;
    void InsertSort(RecType R[],int n)
    {
    int i,j;
    RecType tmp;
        for(i=1;i<n;i++)
        {
            tmp=R[i];
            j=i-1;
            while(j>=0&&tmp.key<R[j].key)
            {
                R[j+1]=R[j];
                j--;
            }
        R[j+1]=tmp;
        }
    }

**直接插入排序的图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70][]

### 折半插入排序 ###

//折半插入排序
    typedef struct
    {
    int key;
    }RecType;
    void InsertSort(RecType R[],int n)
    {
        int i,j,low,high,mid;
        RecType tmp;
             for(i=1;i<n;i++)
             {
                       tmp=R[i];
                       low=0;
                       high=i-1;
                       while(low<=high)
                       {
                       mid=(low+high)/2;
                       if(tmp.key<R[mid].key)
                                high=mid-1;
                       else
                                low=mid+1;
                       }
                      for(j=i-1;j>=high+1;j--)
                                R[j+1]=R[j];
                       R[high+1]=tmp;
             }
    }

**折半插入排序的图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1][]

### 希尔排序 ###

//希尔排序-不稳定
    typedef struct
    {
    int key;
    }RecType;
    void ShellSort(RecType R[],int n)
    {
             int i,j,gap;
             RecType tmp;
             gap=n/2;
             while(gap>0)
             {
                       for(i=gap;i<n;i++)
                       {
                                tmp=R[i];
                                j=i-gap;
                                while(j>=0&&tmp.key<R[i].key)
                                {
                                         R[j+gap]=R[j];
                                         j=j-gap;
                                }
                               R[j+gap]=tmp;
                       }
                       gap=gap/2;//减小增量
             }
    }

**希尔排序的图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70]: /images/20211229/b9872ac0b9fb4abeaf5e7b6ad2ae7377.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1]: /images/20211229/7d08b4d49a1c429387ec1353907c1604.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 2]: /images/20211229/b963144215554ba3b90d91e38ac6828b.png