08-8.2.2 希尔排序

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

思想

先追求表中元素部分有序，再逐渐逼近全局有序

算法实现

// 希尔排序  
void ShellSort(int A[], int n){  
    int d, i, j;  
    // A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for (d = n / 2; d >= 1; d /= 2)  // 步长变化
    {        
	    for (i = d+1; i <= n; ++i)  
        {            
	        if(A[i] < A[i-d])  // 需要将A[i]插入有序增量子表
            {                
	            A[0] = A[i];  // 暂存在A[0]
                for (j = i-d; j >= 1 && A[0] < A[j]; j -= d)  
                {                    
	                A[j+d] = A[j];  // 记录后移，查找插入的位置
                }                
                A[j+d] = A[0];  // 插入
            }        
        }    
    }
}

希尔排序仅适用于顺序表