• 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 !