#include <stdio.h>
#include <stdlib.h>

void Insert_Sort(int k[], int n);
void Binary_Insert_Sort(int k[], int n);
void Shell_Sort(int k[], int n);
int d[] = { 5,3,1 };
int main()
{
    int k[] = {50,26,38,80,70,90,8,30,40,20};
    Shell_Sort(k,10);
    printf("The sorted result: \n");
    for (int i = 0; i < 10; i++) {
        printf("%d ", k[i]);
    }
    printf("\n\n");
}

/*直接插入排序*/
void Insert_Sort(int k[], int n) {
    int temp,i,j;
    for (i = 1; i < n; i++) {
        if (k[i] < k[i - 1]) {
            temp = k[i];
            for (j = i - 1; temp < k[j] && j>=0; j--) {
                k[j + 1] = k[j];
            }
            k[j+1] = temp;
        }
    }
}
/*折半插入排序*/
void Binary_Insert_Sort(int k[], int n) {
    
    int middle;
    int i, j,temp;
    for (i = 1; i < n; i++) {
        int low = 0;
        int high = i - 1;
        temp = k[i];
        while (low <= high) {
            middle = (low + high) / 2;
            if (k[middle] < temp) {
                low = middle + 1;
            }
            else if(k[middle] > temp) {
                high = middle - 1;
            }
            else {
                break;
            }
        }
        for (j = i - 1; j > high; j--) {
            k[j + 1] = k[j];
        }
        k[high + 1] = temp;
    }
}
/*希尔排序*/
void Shell_Sort(int k[], int n) {
    int i, j, l, temp;
    for (i = 0; i < 3; i++) {
        for (j = d[i]; j < n; j++) {
            if (k[j] < k[j - d[i]]) {
                temp = k[j];
                for (l = j - d[i]; k[l] > temp; l-=d[i]) {
                    k[l + d[i]] = k[l];
                }
                k[l + d[i]] = temp;
            }
        }
    }
}