C语言实现插入排序和二分查找

刺骨的言语ヽ痛彻心扉 2023-03-14 10:51 2阅读 0赞

#include <iostream>
    using namespace std;
    
    // 输出数组
    void printAll(int *arr,int len){ 
        int i;
        for(i=0; i<len; i++){ 
            cout<< arr[i] << "\t";
        }
        cout<<endl;
    }
    
    // 插入排序
    void insertSort(int *arr,int len){ 
        for(int i=1; i<len; i++){ 
            int temp = arr[i];
            int j = 0;
            for(j=i-1; j>=0; j--){ 
                if(arr[j]>temp){ 
                    // 向后移位
                    arr[j+1] = arr[j];
                }else{ 
                    break;
                }
            }
            // 发生了交换
            if(arr[i]!=temp){ 
                arr[++j]=temp;
            }
        }
    }
    
    // 二分查找
    // 应用二分查找 的前提是必须是有序数组
    int binarySearch(int *arr, int len ,int x){ 
        // 初始化上下限
        int low = 0;
        int high = len-1;
    
        while(low<=high){ 
            int mid = (low+high)/2;
            cout<< "mid=" << mid <<endl;
            if(arr[mid]>x){ 
                high=mid-1;
            }else if(arr[mid]<x){ 
                low=mid+1;
            }else{ 
                return mid;
            }
        }
    
        return -1;
    }
    
    int main()
    { 
        int arr[]={ 12,-6,45,2,2,9,435,0,34};
        // 计算数组长度
        int len = sizeof(arr)/sizeof(int);
    
        cout<<"原数组如下："<<endl;
        printAll(arr,len);
    
        insertSort(arr,len);
    
        cout<<"排序后数组如下："<<endl;
        printAll(arr,len);
    
        int x=2;
        int index = binarySearch(arr,len,x);
    
        if(index != -1){ 
            cout<< x << "的索引为：" << index <<endl;
        }else{ 
            cout<< x << "不在此数组中!" <<endl;
        }
        return 0;
    }