#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//打印数组
void printNum(int *e,int n);
int search_Seq(int *num,int n,int x);
int search_Bin(int *num,int n,int x);
void sort_Buble(int *num,int n);
void sort_Buble2(int *num,int n);
void selectSort(int *num,int n);

void sort_Quick();
void swap(int *a,int *b){
    int t;
    //(t=*a,*a=*b,*b=t);
    t=*a;
    *a=*b;
    *b=t;
}
int main(void) {
    printf("Hello World\n");
    int n,*e;
    srand(time(NULL));
    printf("请输入一个数，将生成n大的数组\n");
    scanf("%d",&n);
    e=(int*)malloc(n*sizeof(int));
    for(int i=0;i<n;i++){
        e[i]=rand()%21;
    }
    printf("下面1为随机生成的数组\n");
    printNum(e,n);
    if(0==1){
        printf("顺序查找如下\n");
        printf("输入查找的数值\n");
        int x;
        scanf("%d",&x);
        if(search_Seq(e,n,x)){
            printf("顺序查找成功\n");
        }else{
            printf("顺序查找失败\n");

        }
    }
    if(1==1){
        selectSort(e,n);
        printf("折半查找如下\n");
        printf("输入查找的数值\n");
        int x;
        scanf("%d",&x);
        if(search_Bin(e,n,x)){
            printf("折半查找成功\n");
        }else{
            printf("折半查找失败\n");

        }
    }

    if(0==1){
        printf("冒泡排序如下\n");
        sort_Buble2(e,n);
        printf("下面为操作后的数组\n");
        printNum(e,n);
    }
    if(0==1){
        printf("选择排序如下\n");
        selectSort(e,n);
        printf("下面为操作后的数组\n");
        printNum(e,n);

    }


    return 0;
}
void printNum(int *e,int n){
    for(int i=0;i<n;i++){
        printf("%d ",e[i]);
    }
    printf("\n");
}
//王道的不推荐
void sort_Buble(int *num,int n){
    for(int i=0;i<n-1;i++){
        int flag=0;
        for(int j=n-1;j>i;j--){
            if (num[j-1]<num[j]) {
                swap(&num[j-1], &num[j]);
                flag=1;
            }
        }
        if(!flag)
            return;
    }
}
//flag 可略,推荐
void sort_Buble2(int *num,int n){
    for(int i=0;i<n-1;i++){
        //标识符 如果有序就直接
        int flag=0;
        //原来是j从0到n-2 依次比较（一共n-1轮）
        //优化原因 每次最大值都已经移到最后面了 可以稍微减少几次，
        //减少的次数就是i的大小 于是条件为j<n-1-i;
        for(int j=0;j<n-1-i;j++)
            if(num[j]>num[j+1]){
                swap(&num[j],&num[j+1]);
                flag=1;//判断 如果为0 的话，就是没有交换，表有序，结束
            }
        if(!flag)
            return;
    }
}
//简单选择排序
void selectSort(int *num,int n){
    //找出最小的，从0到n-1 ，1到n-1，2到n-1 ~~~n-2到n-1(指下标)
    //一共n-1轮，所以i是0到n-2
    for(int i=0;i<n-1;i++){
        //表示下标轮，再重置为i
        int min=i;
        //i跟i+1比较
        for(int j=i+1;j<n;j++){
            if(num[j]<num[min])
                min=j;
        }
        //如果min没变，就说明就是最小的了
        //否则就交换最小值
        if(min!=i){
            swap(&num[min],&num[i]);
        }
    }
}
void sort_Quick(){

}
int search_Seq(int *num,int n,int x){
    for(int i=0;i<n;i++)
        if(num[i]==x)
            return 1;
    return 0;
}
//前提是已经排序过的 加快速度
int search_Bin(int *num,int n,int x){
    int low=0,high=n-1;//下标
    //low>high结束循环
    while (low<=high) {
        int mid=(low+high)/2;
        //中间值恰好为mid值 ，放回
        if(num[mid]==x)
            return mid;
            //比中间值小
        else if (num[mid]>x){
            //最大值移到中间前一个位置（方便结束循环，
            //如果就是 high=mid 会陷入死循环
            high=mid-1;
        }else{
            //同理
            low=mid+1;
        }
    }
    return 0;
}