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

/* 直接插入排序算法 */
/* 
   1.首先将record分成两个表，一个是有序表：只含有一个元素，另一个是无序表：含record_size - 1个元素
   2.首先j = i -1找到有序表的表尾，从无序表取头节点record[i]，先保存在temp里面，然后依次从尾到头遍历有序表，
   有序表工作下标每次向前移动一位， 找到temp > record[j]的位置，或者已经到达有序表的表头减一（越界）j < 0 停止移动j工作下标，
   record[j + 1] = temp 完成本个节点的插入，i++无序表表头++。
   3.循环2步骤，直到无序表表头下标越界record数组，停止。
   */
int pkt_direct_insert_sort(int *record, int record_size)
{
    int i, j;           /* i是有序表的表尾，j是无序表的表头 */
    int temp;

    for (i = 1; i < record_size; i++) /* 无序表表头i到达数组的最后的后一位，已越界，停止循环 */
    {
        j = i - 1;              /* 计算有序表的尾节点下标 */
        temp = record[i];
        while (temp < record[j] && j >= 0)
        {
            record[j + 1] = record[j];  /* 向后移动一位，给temp腾位置 */       
            j--;
        }
        record[j + 1] = temp;   /* 插入temp */
    }
}

/* shell排序 */
int pkt_shell_sort(int *record, int record_size)
{
    int i, j;           /* i是有序表的表尾，j是无序表的表头 */
    int temp;
    int d;

    for (d = record_size / 2; d > 0; d /= 2)
    {
        for (i = d; i < record_size; i++) /* i无序表头到达数组的最后的后一位，已越界，停止循环 */
        {
            j = i - d;              /* 计算有序表的尾节点下标 */
            temp = record[i];
            while (temp < record[j] && j >= 0)
            {
                record[j + d] = record[j];  /* 向后移动一位，给temp腾位置 */       
                j -= d;
            }
            record[j + d] = temp;   /* 插入temp */  
        }
    }
}

5/* 一趟快速排序 */
int pkt_quick_pass(int *record, int i, int j)
{
    int temp;       /* 基准 */
    temp = record[i];       /* 基准 */

    while (i < j)
    {
        while (i < j && record[j] >= temp)  /* 从下界比较，在高的一边找小于temp的值的下标j */
        {
            j--;
        }
        if (i < j)              /* 证明由于 record[j] >= temp 条件不成立退出的while */
            record[i] = record[j]; /* 交换高一边的元素到低的一边去 */

        while (i < j && record[i] <= temp)  /* 从上界比较，在低的一边找大于temp的值的下标i */
        {
            i++;
        }
        if (i < j)
            record[j] = record[i]; /* 交换低一边的元素到高的一边去 */
    }

    record[i] = temp;        /* 此时肯定是 i == j，基准的位置i保存基准 */
    return i;                /* 返回本次比较的基准位置 */
}

/* 快速排序：递归实现 */
void pkt_quick_sort(int *record, int low, int high)
{
    int mid;        /* 基准 */
    
    if (low < high)
    {
        mid = pkt_quick_pass(record, low, high);  /* 一趟快速排序 */
        pkt_quick_sort(record, low, mid - 1); /* 基准左边快速排序 */
        pkt_quick_sort(record, mid + 1, high); /* 基准右边快速排序 */
    }
}

int main(int argc, char **argv)
{
    int arry[] = {1, 5, 0, 4, 3, 8, 9, 2, 7, 6};

    pkt_quick_sort(arry, 0, sizeof(arry) / sizeof(arry[0]) -1);

    for (int i = 0; i < sizeof(arry) / sizeof(arry[0]); i++)
    {
        printf("%d\n", arry[i]);
    }

    return 0;
}