数据结构与算法-希尔排序

代码实现：

 1 //希尔排序
 2         public static void ShellSort(int[] arr)
 3         {
 4 
 5             for (int gap= arr.Length/2;  gap>0; gap=gap/2)
 6             {
 7                 for (int i = gap; i<arr.Length ; i++)
 8                 {
 9                     for (int j = i; j - gap >= 0; j -= gap)
10                     {
11                         if (arr[j] < arr[j - gap])
12                         {
13                             ExchangeLocation(arr, j, j - gap);
14                         }
15                     }
16                 }
17             }
18         }

根据优化后的间隔序列的代码实现

 1  //优化后希尔排序
 2         public static void OptimizedShellSort(int[] arr)
 3         {
 4             
 5             int h = 1;
 6 
 7             while (h < arr.Length / 3)
 8             {
 9                 h= 3*h + 1;
10             }
11 
12 
13             for (int gap = h; gap > 0; gap = (gap-1)/3)
14             {
15                 for (int i = gap; i < arr.Length; i++)
16                 {
17                     for (int j = i; j - gap >= 0; j -= gap)
18                     {
19                         if (arr[j] < arr[j - gap])
20                         {
21                             ExchangeLocation(arr, j, j - gap);
22                         }
23                     }
24                 }
25             }
26         }

 1  //优化后希尔排序2
 2         public static void OptimizedShellSort2(int[] arr)
 3         {
 4 
 5             int h = 1;
 6 
 7             while (h < arr.Length / 3)
 8             {
 9                 h = 3 * h + 1;
10             }
11 
12 
13             for (int gap = h; gap > 0; gap = (gap - 1) / 3)
14             {
15                 for (int i = gap; i < arr.Length; i++)
16                 {
17                     for (int j = i; j - gap >= 0; j -= gap)
18                     {
19                         int oriValue = arr[j];
20                         int curr_index = j;
21 
22                         if (oriValue < arr[j - gap])
23                         {
24                             arr[j] = arr[j - gap];
25                             curr_index = j - gap;
26                             //ExchangeLocation(arr, j, j - gap);
27                         }
28 
29                         arr[curr_index] = oriValue;
30                     }
31                 }
32             }
33         }