欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-10-26 10:53:46
一、插入排序 <1>介绍:插入排序(insertion sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相...

一、插入排序


<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>图示过程:

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