C# Hill sort

C#Hill Sorting

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class ShellSorter  
    {  
        public static int[] Sort(int[] a)  
        {  
            ShellSort(a);  
            return  a;  
        }  
        public static void ShellSort(int[] myArray)  
        {  
            int i, j, increment;  
            int temp;  
            for (increment = myArray.Length / 2; increment > 0; increment /= 2)  
            {  
                for (i = increment; i < myArray.Length; i++)  
                {  
                    temp = myArray[i];  
                    for (j = i; j >= increment; j -= increment)  
                    {  
                        if (temp < myArray[j - increment])  
                            myArray[j] = myArray[j - increment];  
                        else  
                            break;  
                    }  
                    myArray[j] = temp;  
                }  
            }  
        }  
    }  
}

Hill sorting is an improvement on the direct insertion sorting algorithm. Its main idea is to first divide the entire sorted sequence into several subsequences, and perform direct insertion sorting on the subsequences. , and then perform a direct insertion sort on all the arrays when they are basically in order. This is used to form a new ordered sequence. The general division method is that the distance between two elements is d=n/2, n/4, n/8...and so on.
1. Basic idea:
Divide the entire data elements to be sorted into several groups, and use the direct insertion method to sort the data elements in the same group; the number of groups is gradually reduced, and when all data elements are completed The sorting process ends after sorting within a group.
2. Skills:
The composition of the group is not simply "divided segment by segment", but the records separated by a certain increment dk are formed into a group, and the increment dk is shortened step by step (for example, 5 is taken in sequence, 3,1) until dk=1.
3. Advantages:
If the elements with small key values ​​can be moved forward quickly, and if the sequence is basically in order, then direct insertion sorting can be used, and the time efficiency will be much higher.

Example one:

Example two:

##Flowchart

For the insertion sort algorithm, if the original data is in order, then the data does not need to be moved, and the efficiency of the insertion sort algorithm is Mainly consumed in the movement of data. Therefore, it can be seen that if the data itself is ordered or basically ordered, then the efficiency will be improved.

The above is the content of C# and Hill sorting. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!