排序算法-希尔排序

    希尔排序是插入排序的一种改进版本，通过将整个序列按一定间隔分组，对每个分组进行插入排序，然后逐渐减小间隔，直到间隔为1，最后对整个序列进行一次插入排序。希尔排序的核心思想是利用插入排序对近乎有序的序列进行排序，以提高插入排序的效率。

思路：

1. 设定一个增量值（通常是序列长度的一半），并进行分组。
2. 对每个分组进行插入排序。
3. 逐渐减小增量值，重复步骤1和2，直到增量值为1。
4. 最后对整个序列进行一次插入排序。

class Solution {
    public int[] sortArray(int[] nums) {
        int n=nums.length;
        for(int gap=n/2;gap>0;gap/=2){
            for(int i=gap;i<n;i++){
                for(int j=i-gap;j>=0&&nums[j]>nums[j+gap];j=j-gap){
                    swap(nums,j,j+gap);
                }
            }
        }
        return nums;
    }

    public void swap(int[] arr, int a,int b){
       int temp=arr[a];
		arr[a]=arr[b];
		arr[b]=temp;
    }
    
}