#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

/************************************************

 * 插入排序法

 * 第1次循环: 5, 3, 4, 6, 2, 1 -> 5, 5, 4, 6, 2, 1 -> 3, 5, 4, 6, 2, 1

 * 第2次循环: 3, 5, 4, 6, 2, 1 -> 3, 5, 5, 6, 2, 1 -> 3, 4, 5, 6, 2, 1

 * 第4次循环: 3, 4, 5, 6, 2, 1 -> 3, 3, 4, 5, 6, 1 -> 2, 3, 4, 5, 6, 1

 * 第5次循环: 2, 3, 4, 5, 6, 1 -> 2, 2, 3, 4, 5, 6 -> 1, 2, 3, 4, 5, 6

 ************************************************/

void insert_sort(int *arr, int n){

    int i = , j = , tmp = ;

    for( i = ; i < n; i++ ){

        if( arr[i-] > arr[i] ){

            tmp = arr[i];

            for( j = i - ; arr[j] > tmp && j >=  ; j-- ){

                arr[j+] = arr[j];

            }

            arr[j+] = tmp;

        }

        /*

        printf("the %d times iteration : ",i);

        for( int j = 0 ; j < n; j++ ){

            printf("%2d ",arr[j]);

        }

        printf("\n");

        */

    }

}

/************************************************

 * 快速排序法

 ************************************************/

int partition(int *arr, int low, int high){

    int tmp = arr[low];

    while( low < high ){

        while( low < high && arr[high]>= tmp ) high--;

        arr[low] = arr[high];

        while( low < high && arr[low] <= tmp ) low++;

        arr[high] = arr[low];

    }

    arr[low] = tmp;

    return low;

}

void q_sort(int *arr, int low, int high){

    int pivot = ;

    while( low < high ){

        pivot = partition( arr,low,high );    // 对arr一分为二

        q_sort( arr,low,pivot- );            // 低子表递归排序

        low = pivot + ;                    // 尾递归

    }

}

/************************************************

 * 2分归并排序

 ************************************************/

void merge_sort( int *arr,int *tmp,int s_idx,int m_idx,int e_idx){

    int i = s_idx, j = m_idx+, k = s_idx;

    while( i != m_idx+ && j != e_idx+ ){

        if( arr[i] < arr[j] ){

            tmp[k++] = arr[i++];

        }

        else{

            tmp[k++] = arr[j++];

        }

    }

    while( i != m_idx+ ){

        tmp[k++] = arr[i++];

    }

    while( j != e_idx+ ){

        tmp[k++] = arr[j++];

    }

    for( i = s_idx;i <= e_idx;i++ ){

        arr[i] = tmp[i];

    }

}

void m_sort(int *arr,int *tmp,int s_idx,int e_idx){

    if( s_idx < e_idx ){

        int mid = (s_idx + e_idx) / ;    // 将arr分为arr[0..mid]和arr[mid+1..n-1]

        m_sort( arr,tmp,s_idx,mid);        // 递归将arr[0..mid]归并为有序的tmp[0..mid]

        m_sort( arr,tmp,mid+,e_idx);    // 递归将arr[mid+1..n-1]归并为有序的tmp[mid+1..n-1]

        merge_sort( arr,tmp,s_idx,mid,e_idx);    // 将arr[0..mid]和arr[mid+1..n-1]归并到tmp[0..n-1]

    }

}

/************************************************

 * 反转序列

 ************************************************/

void reverse(int *arr, int n){

    int s_idx = , e_idx = n - ;

    int tmp = ;

    while( s_idx < e_idx ){

        tmp = arr[s_idx];

        arr[s_idx++] = arr[e_idx];

        arr[e_idx--] = tmp;

    }

}

void show_arr(int *arr, int n){

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

        printf("%2d ",arr[i]);

    }

    printf("\n");

}

/************************************************

 * 二分查找

 * 数组 1  2  3  4  5  6  查找 5

 *      |     |        |

 *    low    mid       high

 * 循环1次：

 *     1  2  3  4  5  6  查找 5

 *              |  |  |

 *             low mid high

 ************************************************/

bool binary_search(int *arr, int n, int key){

    if( NULL == arr ) return false;

    int low = , high = n - , mid = ;    // low为数组首位，high为数组末位

    while( low < high ){

        mid = low + (( high - low ) >> ); //防止溢出，移位也更高效。每次循环都要更新。

        if( key < arr[mid] ){            // 若关键字小于中值

            high = mid - ;                // 高下标调整到中下标小1

        }

        else if( key > arr[mid] ){        // 若关键字大于中值

            low = mid + ;                // 低下标调整到中下标加1

        }

        else{

            return true;

        }

    }

    return false;

}

int main(){

    int i = ;

    int arr[] = {, , , , , , };

    int len = sizeof(arr)/sizeof(arr[]);

    int tmp[len];

    m_sort(arr,tmp,,len-);

    printf("m_sort:\n");

    show_arr(arr,len);

    reverse(arr,len);

    insert_sort(arr,len);

    printf("insert_sort:\n");

    show_arr(arr,len);

    reverse(arr,len);

    q_sort(arr,,len-);

    printf("q_sort:\n");

    show_arr(arr,len);

    int key = ;

    printf("%d is%s in the arr\n",key,( binary_search(arr,len,key) ) ? "" : " not");

}