数据结构——希尔排序

落日映苍穹つ 2023-06-21 03:51 2阅读 0赞

## 希尔排序 ##

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

## 算法步骤 ##

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

来源：https://github.com/hustcc/JS-Sorting-Algorithm

## 算法演示 ##

![format_png][]

## 排序动画过程解释 ##

首先，选择增量 gap = 10/2 ，缩小增量继续以 gap = gap/2 的方式

初始增量为 gap = 10/2 = 5，整个数组分成了 5 组

按颜色划分为【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0 】

对这分开的 5 组分别使用

上节所讲的插入排序

结果可以发现，这五组中的相对小元素都被调到前面了

缩小增量 gap = 5/2 = 2，整个数组分成了 2 组

【 3 , 1 , 0 , 9 , 7  】，【 5 , 6 , 8 , 4 , 2  】

对这分开的 2 组分别使用上节所讲的插入排序

此时整个数组的有序性是很明显的

再缩小增量 gap = 2/2 = 1，整个数组分成了 1 组

【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0  】

此时，只需要对以上数列进行简单的微调，不需要大量的移动操作即可完成整个数组的排序。

例：

用希尔排序将序列\{10,18,4,3,6,12,1,9,15,8 \} 增量5,3,1；

d=5 后 \{10,1,4,3,6,12,18,9,15,8 \}  
d=3 后 \{3,1,4,8,6,12,10,9,15,18 \}  
d=1后 \{1,3,4,6,8, 9 ,10,12,15,18 \}  
d=1是将全部分为一组,再排序

## 代码实现： ##

/***************************************************************************
     *  @file       Shell_sort.cpp
     *  @author     Shawn
     *  @date       7  Jan 2019
     *  @remark     7  Jan 2019
     *  @theme      Shell Sort
     ***************************************************************************/
    # include<iostream>
    using namespace std;
    void shellsort(int[], int);
    
    int main()
    {
        int array [] = {55,2,6,4,32,12,9,73,26,37};
    
        int len = sizeof(array) / sizeof(int);
    
        cout<<"输入的原始序列:  ";
        for(int i=0; i<len; i++) // 输出原序列
            cout<<array[i]<<",";
        cout<<endl<<endl;
    
        cout<<"  ----希尔排序开始---- " << endl;
        shellsort(array,len); // 调用排序函数
        return 0;
    }
    
    void shellsort(int a[], int size)
    {
        int i, j, gap;
    	for (gap = size / 2; gap > 0; gap /= 2) // 每次的增量，递减趋势
    		{
    			for (i = gap; i < size; i++) //每次增量下，进行几组插入排序，如第一步就是（从12，9，73，26，37）5次
    				for (j = i ; j -gap >= 0 && a[j-gap] > a[j]; j -= gap)// 每个元素组中进行直接插入排序，看例子
    					swap(a[j-gap], a[j]); //如果增量为2时他的插入查询操作下标为：
    										//（2-0，3-1/ 4-2-0，5-3-1/ 6-4-2-0，7-5-3-1/ 8-6-4-2-0，9-7-5-3-1）
            	for(int k=0; k<size; k++) // 输出每轮排序结果
                	cout<<a[k]<<",";
            	cout<<endl;
    		}
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTBmMDRmOGI2YWVjMDk3YmI_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy85NTAvZm9ybWF0L3dlYnA?x-oss-process=image/format,png