- 1. 实现排序算法——希尔排序
- 2. 12345678910115284961103117希尔排序
- 3. 3528428549611010196311771132134611958710第一趟排序的结果：希尔排序
- 4. 421346119587101234567891011以间隔d=3取元素分组，对各组排序：以间隔d=2取元素分组：第一组： 2 3 6 5 11 10第二组 ： 1 4 7 9 8 Next…希尔排序
- 5. 52 3 5 6 10 11 1 4 7 8 9 对各组排序：2 1 3 4 5 7 6 8 11 9 10 希尔排序
- 6. 62 1 3 4 5 7 6 8 11 9 10 以间隔d=1取元素，进行终极排序！=直接插入排序……1 2 3 4 5 6 7 8 9 10 11希尔排序
- 7. 方法总结：☆以d=3取元素分成三组，对各小组进行直接插入 排序； ☆三合一，第一趟完成☆以d=2取元素分成两组，对各小组进行直接插入排序☆二合一，第二趟完成☆以d=1取元素分组,完成
- 8. 程序实现（一）：
using System;
namespace forpractice
{
class Program
{
public static void ShellSort(int[] R,int d1,int d2,int d3)
{
int d, i, j, temp;
int[] increment = {d1 ,d2 ,d3 };
for (int m = 0; m < increment.Length; m++)
{
d = increment[m];
for (i = d; i < R.Length; i++)
{
- 9. if (R[i] <= R[i - d])
{
temp = R[i]; j = i - d;
do
{
R[j + d] = R[j];
j = j - d;
} while (j >= 0 && temp <= R[j]);
R[j + d] = temp;
}
}
}
foreach (int elem in R)
Console.Write(elem + " ");
}程序实现（一）：
- 10. static void Main(string[] args)
{
while (true)
{
Console.WriteLine("Enter the increment array:");
int d1 = int.Parse(Console.ReadLine());
int d2 = int.Parse(Console.ReadLine());
int d3 = int.Parse(Console.ReadLine());
int[] R = { 5, 9, 3, 2, 6, 11, 8, 1, 7, 4, 10 };
Console.WriteLine(“排序结果:");
Program.ShellSort(R, d1, d2, d3);
Console.WriteLine("\n\n");
}
}
}
}程序实现（一）：
- 11. ☆增量序列尚未有一种固定的取法，本例中的增量3,2,1也不是唯一的。增量序列的选取原则：☆应使增量序列中的值没有除1之外的公因子，即避免相互形成倍数关系,如 8，4，2。☆最后一个增量值必须等于1。
- 12. 程序实现（二）：
public class Program
{
public static void ShellSort(int[] myarray)
{
int d;
for (d = 1; d <= myarray.Length / 9; d = 3 * d + 1) ;
Console.WriteLine(d);
for (; d > 0; d /= 3)
{
for (int i = d + 1; i <= myarray.Length; i += d)
{
int t = myarray[i - 1];
int j = i;
while ((j > d) && (myarray[j - d - 1] > t))
{
myarray[j - 1] = myarray[j - d - 1];
j -= d;
}
myarray[j - 1] = t;
}
}
}
- 13. public static void Main()
{
int[] myarrary = new int[] { 5,9,3,2,6,11,8,1,7,4,10 };
Program.ShellSort(myarrary);
foreach (int result in myarrary)
Console.Write(result +" ");
Console.ReadKey();
}
}程序实现（二）：
- 14. 评价：随d的不同而不同。1971年James Peterson和David L. Russell 在大量实验的基础上推导出希尔排序的时间复杂度为O(n1.3)，另一种说法O(n1.25-1.6n1.25).时间复杂度：正确性：依赖于直接插入排序。
- 15. Thank You !
