c/c++中折半查找与插入排序的例子

插入排序

找到 比要插入的数大的数组元素,并且是在数组中最小的元素，插入

#include <stdio.h>
void InsertionSort(int *a,int n);
int main(void)
{
    int i;
    int a[10]={2,4,6,8,0,1,5,9,7,3};
    InsertionSort(a,10);
    for(i=0;i<10;i++)
        printf("%d\n",a[i]);
    return 0;
}
 
void InsertionSort(int *a,int n)
{
   int in,out,temp;
   for(out=1;out<n;out++)
   {
    temp=a[out];//需要插入的元素
        in=out;
    while(in>0 && a[in-1]>=temp)
    {
           a[in]=a[in-1];
       in--;
    }
    a[in]=temp;//插入 需要插入的元素
   }
 
}
c++的版本

#include <iostream>
 
using namespace std;
 
template<class T>
void InsertionSort(T *a, int n);
 
template<class T>
void InsertionSort_2(T *a, int n);
 
template<class T>
void Insert(const T& e, T *a, int i);
 
int main()
{
    double x[] = {2.2, 4.5, 6.6, 8, 0, 1,3,5,7,9};
    int y[] = {0,2,4,6,8,0,1,3,5,7,9};
    InsertionSort(x,10);
    InsertionSort_2(y,10);
 
    for(int i=1;i<=10;++i)
        cout << y[i] << endl;
 
    return 0;
}
 
template<class T>
void InsertionSort(T *a, int n)
{
    int in, out;
    // 开始时out=0这个人已经出去了
    for(out=1;out<n;++out)
    {
        T temp = a[out];
        in = out;
        while(in>0 && a[in-1]>=temp)
        {
            a[in] = a[in-1];
            --in;
        }
        a[in] = temp;
    }
}
 
template<class T>
void InsertionSort_2(T *a, int n)
{
    //a[0]用来保存排序使用，不能保存原始数据
    for(int j=2; j<=n; ++j)
    {
        T temp = a[j];
        Insert(temp,a,j-1);
        //a[0] = temp;
        //int i = j-1;
        //while(temp <a[i])
        //{
        //  a[i+1] = a[i];
        //  i--;
        //}
        //a[i+1] = temp;
    }
}
 
template<class T>
void Insert(const T& e, T *a, int i)
{
    a[0] = e;
    while(e<a[i])
    {
        a[i+1] = a[i];
        i--;
    }
    a[i+1] = e;
}

折半查找

一：c语言版本 顺序线性查找 递归迭代查找

#include <stdio.h>
 
int binsearch(int x, int v[], int n);
 
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int 结果, num;
 
    num = 8;
 
    结果 = binsearch(num, arr, 10);
 
    if(结果<0)
        printf("没找到!\n");
    else
        printf("在arr[%d]找到%d\n", 结果, num);
 
    return 0;
}
 
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
 
    low = 0;
    high = n-1;
    while(low <= high) {
        mid = (low + high) / 2;
        if(x < v[mid])
            high = mid - 1;
        else if(x > v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

二：c语言递归查找

#include <stdio.h>
int BinarySearch(int *a,int x,int left,int right);
int main(void)
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    int num;
    int 结果;
    printf("请输入要查找的数:");
    scanf("%d",&num);
    结果=BinarySearch(a,num,0,9);
    if(结果<0)
        printf("没找到!\n");
    else
        printf("数组里第%d个元素的值等于%d.\n",结果+1,num);
    return 0;
}
 
int BinarySearch(int *a,int x,int left,int right)
{
    int middle;
    if(left<=right)
    {
        middle=(left+right)/2;
        if(a[middle]==x) return middle;
        else if(a[middle]<x) left=middle+1;
        else if(a[middle]>x) right=middle-1;
        return BinarySearch(a,x,left,right);
    }
    return -1;
}