十大排序算法之希尔排序

朴灿烈づ我的快乐病毒、 2024-04-18 09:20 70阅读 0赞

**例题：**  
对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序  
要求从小到大排列。

**介绍：**  
希尔排序是插入排序的优化版本，  
当数据量很大时，插入排序需要一个一个的进行查找比较比较耗时，  
我们可以用一种方式使其大致趋于从小到大的排序状态，  
然后对其进行精细化的排序处理，

**思路：**  
我们可以把一组大型数据分成几个区间，对每个区间里对应数字进行排序  
比如我们把a数组分为2个区间  
A区间：\{3,44,38,5,47,15,36,26\}  
B区间：\{27,2,46,4,19,50,48\}  
我们把A区间的第一个数与B区间的第一个数进行比较（插入排序）  
如果左大右小，即交换两个数的排列顺序  
这样如果用插入排序要进行8次交换操作，希尔排序只进行一次  
当数据上百万时，希尔排序可以一次移动几十万量级的距离

**阻碍：**  
虽然移动较快，但总是趋于从小到大的排序状态，  
并不是真正意义上的从小到大排序状态  
所以我们可以不断缩小区间的大小，用于完善我们的算法  
而区间与区间之间的交换用插入排序

**执行：**  
不断缩小分割区间，使数列逐步趋于稳定，直至完全稳定  
![在这里插入图片描述][20190904163433459.gif]  
使数组逐步趋于稳定

![在这里插入图片描述][20190904163518260.gif]  
**评价：**  
希尔排序极大的缩短了插入排序的时间复杂度  
时间复杂度O(nlog(n));  
开辟空间约为0；

**java代码**

import java.util.Arrays;
    
    public class 希尔排序 {
    	public static void main(String[] args) {
    		int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
    		//把区间按照每次缩小一半的速度进行
    		for (int d = a.length / 2; d > 0; d /= 2) {
    		//遍历一个区间，并在每个区间中找到对应位置的数
    			for (int x = 0; x < d; x++) {
    			//插入排序
    				for (int i = x + d; i < a.length; i += d) {
    					int t = a[i];
    					int j;
    					for (j = i - d; j >= 0 && a[j] > t; j -= d) {
    						a[j + d] = a[j];
    					}
    					a[j + d] = t;
    				}
    			}
    		}
    		System.out.println(Arrays.toString(a));
    	}
    }

[20190904163433459.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/010874b568f04476ab44a0fc063dcd46.gif
[20190904163518260.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8d8204afef534b3895973cac240611fd.gif