频道栏目
首页 > 资讯 > C语言 > 正文

数据结构之插入排序和希尔排序实例讲解

17-12-04        来源:[db:作者]  
收藏   我要投稿

一、插入排序


<1>介绍:插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

<2>思路:
从第一个元素依次进行以下操作:对于当前元素可以认为当前元素之前的部分已经有序;取出当前位置的下一个元素作为要排序的值,在已经排序的元素序列中从后向前扫描,如果该元素(已排序)大于新元素,将该元素移到下一位置;直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置中;
分别把下标从0到数组元素个数-1的元素作为end,进行以上操作;每次循环的目的就是为了将当前tmp值放置在之前序列中该放的位置上,使得当前部分序列有序。

<3>实现:
void InsertSort(int* arr, int sz)
{
    for (int i = 0; i < sz - 1; i++)
    {
        int end = i;
        int tmp = arr[end + 1];

        while (end >= 0)
        {
            if (arr[end] > tmp)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            else
                break;
        }
        arr[end + 1] = tmp;
    }
}

<4>图示过程:

这里写图片描述


二、希尔排序


<1>介绍:希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
1、插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率;
2、但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。

<2>思路及排序效果:
①:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序;
②:然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

大致思路和插入排序相同,区别在于希尔排序可以给定一个gap值,也就是间隔,可以预先先将间隔gap的序列对应有序,再不断缩小gap值,到最后一趟依次比较。

这里写图片描述


<3>实现:
void ShellSort(int* arr, int sz)
{
    int gap = 3;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < sz - gap; i++)
        {
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0)
            {
                if (tmp < arr[end])
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                    break;
            }
            arr[end + gap] = tmp;
        }
    }

<4>图示过程:

这里写图片描述

相关TAG标签
上一篇:Apache默认端口80被占用导致无法启动服务问题
下一篇:展示数据使用:recyclerview,retrofit,greendao等
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站