- /// <summary>
- /// 希尔排序 缩小增量排序
- /// 是直接插入排序的改进版
- /// 稳定性:不稳定
- /// 平均时间复杂度:O(Nlog2N),最坏情况下为O(N1.5)
- /// </summary>
- public static voidShellSort(int[] array)
- {
- intgap = array.Length /2;
- while(gap >0)
- {
- //直接插入排序
- for(inti =0; i < gap; i++)
- {
- for(intj = i + gap; j < array.Length; j += gap)
- {
- if(array[j] < array[j - gap])
- {
- inttemp = array[j];
- intk = j - gap;
- while(k >=0&& array[k] > temp)
- {
- array[k + gap] = array[k];
- k -= gap;
- }
- array[k + gap] = temp;
- }
- }
- }
- gap = gap /2;
- };
- }
来源: http://www.bubuko.com/infodetail-1953404.html