java排序算法之希尔排序

谁借莪１个温暖的怀抱￠ 2023-10-18 14:23 97阅读 0赞

**希尔排序相对插入排序来说更加高效，是时间复杂度突破T(n\*n)的另一种高效的简单排序，希尔排序的执行流程可描述为：**

*  一组无序的数列，选择一个增量，即gap = arr.length/2,以此增量为标的，进行第一趟数据分组与排序，然后缩小增量，继续以gap = gap/2的方式进行分组和排序，
 *  每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

### 以下即为排序的过程演示图， ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]

下面我们用代码来实现希尔排序，

public class ShellSort {
    	
    	public static void main(String[] args) {
    		
    		int[] arr = {1,8,3,7,6,5,9,4,2};
    		
    		System.out.println("排序前:" + Arrays.toString(arr) + "\r");
    		
    		System.out.println("排序后:" + Arrays.toString(sortShell(arr)));
    	}
    	
    	public static int[] sortShell(int[] arr){
    		
    		int length = arr.length;
    		int temp;
    		int gap = length/2;
    		
    		while (gap > 0){	//当组合为单个数时候就没有继续分组的必要了
    			for(int i=gap;i<arr.length;i++){
    				int preIndex = i - gap;							//某一组数据中的前一个数，假如此时为0
    				temp = arr[i];									//假如为 arr[5]
    				while(preIndex >= 0 && arr[preIndex] > temp){   //arr[1] > arr[5]
    					arr[preIndex+gap] = arr[preIndex];
    					preIndex-=gap;
    				}
    				arr[preIndex+gap] = temp;
    				
    			}
    			gap/=2;
    		}
    		return arr;
    	}
    
    }

运行main函数，得到结果，  
![在这里插入图片描述][20190213224418651.png]

简单分析一下希尔排序的性能，可以得出如下结论：  
最好的情况下，T(n) = O(nlog2 n)  
最坏情况：T(n) = O(nlog2 n)  
平均情况：T(n) = O(nlog2 n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190213223908124.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[20190213224418651.png]: https://img-blog.csdnimg.cn/20190213224418651.png