Source: H.W. Lang Hochschule Flensburg [email protected] Impressum Datenschutz © Created: 29.01.1998 Updated: Hill sorting is one of the oldest sorting algorithms, named after its inventor D.L.Shell (1959) [She 59]. Although the algorithm is fast, easy to understand and easy to implement. However, its complexity analysis is much more complicated. (୨୧•͈ᴗ•͈)◞︎♡ The pink word was written by me.

@[toc]

Algorithm thought

The algorithm idea of Hill sorting is as follows:

  1. Store a sequence of data in a two-dimensional array
  2. Sort the columns of an array

The result is a partial sorting of the data. Repeat the process, but each time with a narrower array with fewer columns. In the last step, the array has only one column. At each step, the sequence that needs to be sorted increases (the number of columns gradually decreases, and the number of arrays contained in each column gradually increases) until the last step is completely sorted. However, because the sequence obtained in the previous steps has been basically ordered, there is a limit to the sort operations that can be performed in each step.

For example, sort 3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2. First, arrange it into an array of seven columns (left), and then sort those columns (right) :

3 7 9 0 5 1 6 3 3 2 0 5 1 5 8 4 2 0 6 1 5 → 7 4 4 0 6 1 6 7 3 4 9 9 8 2Copy the code

The larger data elements 8 and 9 are sorted to the end of their column, but a smaller number (such as 2 from the second to last column) is also at the end of the column. Next, divide the sequence into three columns and sort them again:

3 3 2 0 0 1 0 5 1 2 2 5 7 4 3 3 4 4 0 6 → 4 5 6 1 6 8 5 6 8 7 7 8 7 9 9 7 7 9 8 8 2 8 9Copy the code

Now, the sequence is basically in order. When you line them up in a column in the last step, just move 6, 8, and 9 to the right place.

Algorithm implementation

In fact, the sequence of data is not stored in a two-dimensional array, but in a one-dimensional array. For example, think of the data elements at positions 0, 5, 10, 15, and so on as the first column of an array with five columns. The “columns” that are indexed in this way do insertion sort for each column. This method has good performance. The following program sorts the array A from index position 0 to n-1 and stores the data in the array COLs. Therefore, the data is arranged in 1,391,76 columns in the first step and in one column in the last step. (Note that if the number of columns H is greater than the total number of data elements to be sorted, then basically nothing is done. In other words, at the first step, it is meaningless to assign the maximum number of columns to the data.

void shellsort (int[] a, int n)
{
    int i, j, k, h, v;
    int[] cols = {1391376.463792.198768.86961.33936.13776.4592.1968.861.336.112.48.21.7.3.1}
    for (k=0; k<16; k++)
    {
        h=cols[k];
        for (i=h; i<n; i++)
        {
            v=a[i];
            j=i;
            while(j>=h && a[j-h]>v) { a[j]=a[j-h]; j=j-h; } a[j]=v; }}}Copy the code

Algorithm analysis

The correctness of the algorithm lies in the last step (h = 1), in which the whole array is sorted by ordinary insertion. But since the data is through the previous steps (h = 3, 7, 21…) Presort, so the last step is only a few insert sort steps. The above h-sequence (hereafter referred to as the H-sequence) is just a way of taking increments, and in fact the performance of Hill sort depends on how the increments are taken.

background

A letter costs sixteen francs, a postcard eleven francs. But only three-franc and seven-franc stamps are available. Can I mail the letter and postcard? (Did the brothers send postcards? Before sending, the post office has already stipulated the postage according to the distance. When sending, you need to affix the stamps of the corresponding price to be sent. When there is no stamps of the corresponding denomination, you have to affix several stamps to make up the price. For example, if we send a letter by post for 1.2 yuan, you can put 3 40 fen stamps on it. Obviously, the problem is to represent the numbers 16 and 11 as linear combination K… 3+ L… 7K ·3 + L · 7K… 3+ L… 7, non-negative integer coefficients K and L. What natural numbers can be composed of integer multiples of 3 and 7? Which ones can’t?

Definition: Let g, H ∈INg, H \in INg,h∈ in. If F can be expressed as a linear combination of coefficients K f= K ×g+ L ×hf=k \times g+ L \times hf=k×g+ L ×h, then we say f is a linear combination of g and h, the coefficients K, L ∈IN0k, L \in IN_0k, L ∈IN0. Since 16 is a linear combination of 3 and 7, that is, 16=3×3+1×716=3 \times 3+1 \times 716=3×3+1×7, the envelope can be sent accurately.

Definition: let g, H ∈INg,h \in INg,h∈ in be mutually prime. N (g, h) N (g, h) N (g, h) represents the (finite) set of all natural numbers that are not a combination of g and h, and γ (g, h) γ (g, h) γ (g, h) represents the largest natural number of these numbers:

undefined