Hill | insert sort

#include <bits/stdc++.h>

using namespace std;

const int in = 0.000001;

const double PI = 3.1415926535;

#define inf 0x3f3f3f;

typedef long long ll;

const int N = 1e5 + 10;

int q[N];

void Shell_sort (int a[], int n)

{

    int d, i, j;

    for (d = n / 2; d >= 1; d /= 2)  // d Represents each increment , from n / 2   until d = 1      When d = 1 when   This is also known as insertion sorting , This is done to optimize the insertion sort , Avoid when the number of inserts is small , It will cause multiple backward shifts .

        for (i = d / 2; i < n; i ++)

        {

            if (a[i] < a[i - d])    // If a[i] Less than It corresponds to the previous hour of increment , Record a[i]

            {                    

                int x = a[i];

                for (j = i - d; j >= 0 && x < a[j]; j -= d)  //   Find smaller ones in incremental order

                {

                    a[j + d] = a[j];       // still a[i] < a[j] Move back to x Make room

                }

                a[j + d] = x;     // Finally insert x

            }

        }

   

}

int main ()

{

    int n;

    cin >> n;

    for (int i= 0; i < n; i ++) scanf ("%d", &q[i]);

    Shell_sort (q, n);

    for (int i = 0; i < n; i++)

    i != n - 1 ? printf("%d ", q[i]) : printf("%d", q[i]);

   

    return 0;

}