/**
 * @file        testsqlist.c
 * @brief       顺序表实现排序
 *              
 * @author      UncleBb
 * @version     0.0.0.1
 * @date        2021/12/10
 */

#include <stdio.h>
#define MAX_LEN 20

struct ARRAY_LIST{
    int index;
    int data[MAX_LEN];
};

struct SHELL_DL{
    int dl[MAX_LEN];
    int len;
};

void init(struct ARRAY_LIST *arr){

    if(NULL == arr){
        return;
    }
    arr->index = 0;

}

//用于直接插入排序的初始化，带哨兵
void init2(struct ARRAY_LIST *arr){

    if(NULL == arr){
        return;
    }
    arr->index = 1;
    arr->data[0] = NULL;

}

void InitBl(struct SHELL_DL *dl){
    dl->len = 3;
    dl->dl[0] = 3;
    dl->dl[1] = 2;
    dl->dl[2] = 1;
}

void add(struct ARRAY_LIST *arr,int value){

    if(arr->index == MAX_LEN){
        printf("顺序表已满，无法插入!\n");
        return;
    }
    arr->data[arr->index] = value;
    arr->index ++;

}

void out(struct ARRAY_LIST *arr){

    int i;
    i = 0;
    while (i < arr->index)
    {
        printf("%d ",arr->data[i]);
        i++;
    }
    printf("\n");

}

//冒泡排序
void BubbleSort(struct ARRAY_LIST *arr){
    
    int i,j;
    int temp;
    printf("元素个数：%d\n",arr->index);

    for(i = 0; i < arr->index; i++){
        for(j = 0; j < arr->index-1-i; j++){
            if(arr->data[j] < arr->data[j+1]){
                temp = arr->data[j];
                arr->data[j] = arr->data[j+1];
                arr->data[j+1] = temp;
            }
        }
    }

}

//直接插入排序，使用哨兵
void InsertSort(struct ARRAY_LIST *arr){

    int i,j;

    for(i = 2; i < arr->index; i++){
        if(arr->data[i] < arr->data[i-1]){
            //此时需要将其插入有序表
            //1、首先复制哨兵
            arr->data[0] = arr->data[i];
            
            for(j = i-1; arr->data[0] < arr->data[j]; j--){
                //２、后移，找到哨兵插入的正确位置
                arr->data[j+1] = arr->data[j];
            }

            //３、插入哨兵
            arr->data[j+1] = arr->data[0];
        }
    }
    
}

//希尔插入排序，dl为每次的步长
void ShellInsert(struct ARRAY_LIST *arr,int dl){

    int i,j;

    for(i = dl+1 ; i < arr->index; i++){
        if(arr->data[i] < arr->data[i-dl]){
            //此时需要将其插入有序表
            //1、首先复制哨兵
            arr->data[0] = arr->data[i];
            
            for(j = i-dl; arr->data[0] < arr->data[j]; j=j-dl){
                //２、后移，找到哨兵插入的正确位置
                arr->data[j+dl] = arr->data[j];
            }

            //３、插入哨兵
            arr->data[j+dl] = arr->data[0];
        }
    }
}

//希尔排序，就是直接插入加了个步长
void ShellSort(struct ARRAY_LIST *arr,struct SHELL_DL *dl){

    int i;

    for(i = 0; i < dl->len; i++){
        ShellInsert(arr,dl->dl[i]);
    }

}

int main(){

    struct ARRAY_LIST arr;
    struct SHELL_DL dl;

    init2(&arr);

    add(&arr,5);
    add(&arr,3);
    add(&arr,4);
    add(&arr,1);
    add(&arr,10);
    add(&arr,21);
    add(&arr,13);
    add(&arr,14);

    printf("排序前：");
    out(&arr);

    // InsertSort(&arr);
    InitBl(&dl);

    ShellSort(&arr,&dl);

    printf("排序后：");
    out(&arr);
    
}