排序+查找算法初探

RT
Update on 2020/11/29

在一个等于号和两个等于号的问题上卡了特么十几分钟我靠！

//四种排序方法初探
//if害我！俩等于号表示判断！！
#include <stdio.h>
#include <string.h>
#define MAX_N 10
#define NUM_N 5
int Way1(int n[], int num);
int Way2(int n[], int num);
int Way3(int n[], int num);
int Way4(int n[], int num);
int prt(int n[],int num);
int main(void){
    int input[MAX_N]={55,33,66,44,88};
    int n1[MAX_N],n2[MAX_N],n3[MAX_N],n4[MAX_N];
    //直接给定5个数据
    int n=NUM_N;
    printf("Original Data:");
    prt(input,n);
    //Way1
    memcpy(n1,input,sizeof(input));
    Way1(n1,n);
    printf("Result 1:");
    prt(n1,n);

    //Way2
    memcpy(n2,input,sizeof(input));
    Way2(n2,n);
    printf("Result 2:");
    prt(n2,n);

    //Way3
    memcpy(n3,input,sizeof(input));
    Way2(n3,n);
    printf("Result 3:");
    prt(n3,n);

    //Way4
    memcpy(n4,input,sizeof(input));
    Way2(n4,n);
    printf("Result 4:");
    prt(n4,n);

    //Find
    //Where is 44?
    //对分
    int mid,low=0,high=NUM_N-1,location,flag=1;
    do{
        mid = (low+high) / 2;

        if(n1[mid] < 44){
            high = mid - 1;
        }else if(n1[mid] == 44){
            location = mid;
            break;
        }else{
            low = mid + 1;
        }

        //找不到是什么呢~
        if(low > high){
            flag = 0;
            printf("Not Found!");
        }

    }while(flag);
    printf("44 is on the %d floor.", location);
    return 0;
}

int Way1(int n[], int num){
    //交换法
    int i,j,temp;
    for(i=0;i<num;i++){
        for(j=i+1;j<num;j++){
            if(n[i] < n[j]){
                temp = n[i];
                n[i] = n[j];
                n[j] = temp;
            }
        }
    }
    return 0;
}

int Way2(int n[], int num){
    //选择法
    int i,j,max,temp;
    for(i=0;i<num;i++){
        max = i; //Key1:当前为最大
        //Key2:寻找MAX
        for(j=i+1;j<num;j++){
            if(n[max] < n[j]){
                max = j;
            }
        }

        //Key3:如果头不是最大则换之
        if(max != i){
            temp = n[i];
            n[i] = n[max];
            n[max] = temp;
        }
    }
    return 0;
}

int Way3(int n[], int num){
    //冒泡法
    //好像是两个两个一组来的...
    //对的！两个两个来，大的往后退！
    int i,j,temp;
    for(i=0;i<num-1;i++){
        for(j=0;j<num-1-i;j++){
            if(n[j]>n[j+1]){
                temp = n[j+1];
                n[j+1] = n[j];
                n[j] = temp;
            }
        }
    }
    return 0;
}

int Way4(int n[], int num){
    //插入法
    //码牌，哈哈
    //从第一个开始，挨边往后轮流，插到前面去！
    int i,j,temp;
    for(i=1;i<num;i++){
        for(j=i;j>=1;j--){
            if(n[j]<n[j-1]){
                temp = n[j];
                n[j] = n[j-1];
                n[j-1] = temp;
            }else{
                break;
            }
        }
    }
    return 0;
}

int prt(int n[], int num){
    int i;
    for(i=0;i<num;i++){
        printf("\t%d", n[i]);
    }
    printf("\n");
}

注意！
在冒泡法当中，两个变量的范围要注意！

第一层循环，要小于n-1，第二层循环，要小于n-1-i

解释：经历过第n-1次冒泡后，它的第二项就确定了！那么第一项也跟着确定了！
那么对于第二层而言，由于涉及到与j+1项的比较，如果小于n-i的话，那么在第一层循环的时候会读到第n+1项（下标为n）发生数组越界。

同理，在插入法当中，为了防止数组越界，我们要

第二轮循环j>=1，因为要读取j-1项。

那么查找呢？
由于找到的是序号，所以

记得最后输出的时候加一哟！

//把如下两个无序数组a和b从小到大排序后，在按照从小到大的顺序一次存放到新的数组中。
// int a[5]={9,78,33,12,23};
// int b[8]={1,34,63,10,5,94,39,27};
//**输出格式要求："%4d\n"，"%4d"
//程序运行示例为：
//   9
//  12
//  23
//  33
//  78
//   1
//   5
//  10
//  27
//  34
//  39
//  63
//  94
//   1   5   9  10  12  23  27  33  34  39  63  78  94
//

#include <stdio.h>
int SortXu(int src[], int n);
void PrintArray(int src[], int n,int mood);
int main(void){
    int a[5]={9,78,33,12,23};
    int b[8]={1,34,63,10,5,94,39,27};
    int c[13];
    //内排
    SortXu(a,5);
    SortXu(b,8);
    PrintArray(a,5,0);
    PrintArray(b,8,0);

    //It's time to show true Kongfu!
    int i,j=0,k=0;
    for(i=0;i<13;i++){
        if(a[j] > b[k]){
            c[i] = b[k];
            if(k < 7){
                k++;
            }
        }else{
            c[i] = a[j];
            if(j < 4){
                j++;
            }
        }
    }
    //Last item
    if(a[4]>b[7]){
        c[12] = a[4];
    }else{
        c[12] = b[7];
    }
    PrintArray(c,13,1);
    //Now I want to find where is 10 in the list.

    //2 fen way
//    int flag=0,low=0,high=12,mid=6;
//    do{
//        if(11 > c[mid]){
//            low = mid+1;
//            mid = (low+high) / 2;
//        }else if(11 < c[mid]){
//            high = mid-1;
//            mid = (low+high) / 2;
//        }else{
//            flag = 1;
//        }
//    }while(flag==0 && high >= low);

    //遍历way
    int itemxx = -1;
    for(i=0;i<13;i++){
        if(c[i] == 11){
            itemxx = i;
            break;
        }
    }


    if(itemxx == -1){
        printf("Fxxk！Not Found!");
    }else{
        printf("\n on the %d", itemxx+1);
    }



    return 0;
}

int SortXu(int src[], int n){
    //选择
    int i,j,minitem,temp;
    for(i=0;i<n;i++){
        minitem = i;

        for(j=i+1;j<n;j++){
            if(src[j] < src[minitem]){
                minitem = j;
            }
        }

        if(minitem != i){
            temp = src[i];
            src[i] = src[minitem];
            src[minitem] = temp;
        }
    }

    //偷袭我，18岁的小同志！
    //冒泡
//    int i,j,k,temp;
//    for(i=0;i<n-1;i++){
//        for(j=0;j<n-i-1;j++){
//            if(src[j]>src[j+1]){
//                temp = src[j];
//                src[j] = src[j+1];
//                src[j+1] = temp;
//            }
//        }
//    }

    //插入
//    int i,j,k,temp;
//    for(i=1;i<n;i++){
//        //based on this and going forward
//        for(j=i;j>0;j--){
//            //深切的体会以下
//            //这里不是要求你...先找到位子再换...
//            //慢慢往前墨迹墨迹
//            if(src[j-1]>src[j]){
//                temp = src[j-1];
//                src[j-1] = src[j];
//                src[j] = temp;
//            }
//        }
//    }
}

void PrintArray(int src[], int n,int mood){
    int i;
    for(i=0;i<n;i++){
        if(mood == 1){
            printf("%4d", src[i]);
        }else{
            printf("%4d\n", src[i]);
        }
    }
}