数据结构之插入排序与希尔排序

本是古典何须时尚 2022-08-06 17:05 187阅读 0赞

**1.直接插入排序**  
直接插入排序是一种最简单的排序算法，它的基本操作是将一个记录插入到已经排序好的序列中，从而得到一个新的有序表。直接插入排序算法原理如下图所示：  
![这里写图片描述][20150207175336688]  
直接插入排序算法如下：

void InsertSort(int arr[],int length)
    {
       int key,j;
       for(int i=1;i<length;++i)
       {
           key=arr[i];  //记录标志;
    
           j=i-1;
    
           //循环比较并且交换相邻的两个数;
           while (j>=0&&arr[j]>key)
           {
               arr[j+1]=arr[j];
    
               j=j-1;
           }
           arr[j+1]=key;
       }
    }

插入排序的算法复杂度分析：从空间的角度来看，它需要一个记录的辅助空间，从时间的角度上来看，排序的基本操作：比较两个关键字的大小和移动记录。从算法中可以看出，for循环的次数取决于待插入关键字与前面i-1个关键字的关系。在整个排序过程中，当待排序的序列中记录按关键字按从小到大正序排列时，只需进行n-1次比较，比较次数达到最小值，记录不需要进行移动。反之，当待排序的序列是按逆序进行排列时，总的比较次数达到了最大值（n+2）（n-1）/2。记录移动的次数也达到了最大值（n+4）（n-1）/2。我们可以取最小值和最大值的平均值，则比较次数和移动记录次数约为n^2/4。因此，直接插入排序的算法复杂度为O（n^2）插入排序中相同的元素排序前后的位置不会发生改变，因此直接插入排序是一种稳定的排序方式。

**2.希尔排序**  
希尔排序又称”缩小增量排序“它也属于插入排序类方法，但在时间效率上较前述直接插入排序方法有较大的改进。在进行插入排序时，如果全部是正序时，其时间复杂度为O（n）。  
因此，如果待记录序列”基本有序“时，直接插入排序的效率可大大提高。希尔排序的基本思想：先将整个待排记录序列分割成为若干了子序列分别进行插入排序，待整个序列”基本有序“时，再对全体记录进行一次直接插入排序。希尔排序的过程如下图：  
![这里写图片描述][20150207174813984]

希尔排序的算法思路：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。  
希尔排序算法描述如下：

void ShellSort(int arr[],int length)
    {
        int gap; //选择希尔排序的步长;
    
        //计算出希尔排序的次数;
        for (gap = length / 2; gap > 0; gap = gap / 2)
        {
            //进行gap次排序;
            for (int i = 0; i < gap; i++)
            {
                //一次插入排序;
                for (int j = i + gap; j < length; j = j + gap)
                {
                    if (arr[j] < arr[j - gap])
                    {
                        int temp = arr[j];
                        int k = j - gap;
    
                        while (k>=0&&arr[k]>temp)
                        {
                            arr[k + gap] = arr[k];
                            k = k - gap;
                        }
                        arr[k + gap] = temp;
                    }
                }
            }
        }
    }

希尔排序的算法复杂度计算是一个复杂的过程，到目前为止还未找到一种最好的”增量“序列函数。平均情况下希尔排序的算法复杂度为O（n^1.3）由于在希尔排序中会根据增量来进行局部排序，因此相同的元素在希尔排序前后位置会发生改变，因此希尔排序是一种不稳定的排序。

**3.总结**  
排序算法是算法的基础，只有多了解算法的基础，才会对算法有更深的了解，本篇博客主要是为了更加深入的了解排序算法中的插入排序，如果有什么不妥之处，望大家多多指教。

[20150207175336688]: /images/20220805/e0ead56f68ca422d84e84926914e40c0.png
[20150207174813984]: /images/20220805/1fa520fec22b4d08bbe4425f730b669f.png