基本思想:在插入排序的基础上加入了分组策略,将数组序列分成若干子序列分别进行插入排序。

C#算法实现:

public static void ShellSort(int[] arr) 
{ 
	int n = arr.Length;
	int gap = n / 2;
	while (gap > 0) 
	{
		for (int i = gap; i < n; i++) 
		{ 
			int current = arr[i]; 
			int j = i; 
			while (j >= gap && arr[j - gap] > current)
			{ 
				arr[j] = arr[j - gap];
				j -= gap; 
			} 
				arr[j] = current; 
          } 
        gap /= 2; 
    }
}