C++——排序与查找C++程序

Question

排序与查找
1、利用前面学习的随机数函数，自动生成10个1~100之间不重复的正整数，并存入一个数组中。
2、写一个插入排序函数，对上述存入数组的数排序，并输出排序结果。
3、写一个折半查找（二分查找）函数，在排完序后的数组上进行数据查找，并显示查找结果。

Answer 1

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <algorithm>

using namespace std;

typedef unsigned int UINT;

void printfVer(vector<UINT> ver)
{
    std::cout << "********* printf start **********" << endl;
    for(size_t i=0;i < ver.size();i++)
    {
        std::cout << ver[i] << endl;
    }
    std::cout << "********** printf end ***********" << endl;

}

void insertsort(vector<UINT> &ver)
{
      for (size_t i=1;i < ver.size();i++)
      {
         UINT key = ver[i];
         int j = i-1;
         while (j >= 0 && ver[j] > key) //与一个的进行比较，小的话就交换
         {
              ver[j+1] = ver[j];//交换
              j--;//下标往前移动
          }
          ver[j+1] = key;//不比前一个小，就不进行交换
      }
}

int search(const vector<UINT> &ver,int i,int j,UINT x){
    int mid;
    mid = (i+j)/2;
    if(i > j) return -1;
    if(ver[mid] == x) return mid;
    if(ver[mid] > x) return search(ver,i,mid-1,x);
    else return search(ver,mid+1,j,x);
}

int main()
{
    vector<UINT> ver;
    ver.clear();

    srand((UINT)time(NULL));
    while (1) {
        UINT temp = rand()%100+1;
        vector<UINT>::iterator iter;
        iter = std::find(ver.begin(), ver.end(), temp);
        if(iter == ver.end())
        {
            //std::cout << "not found and push_back it: " << temp << endl;
            ver.push_back(temp);
        }
        else
        {
          //  std::cout << "found and neglect it: " << temp <<  endl;
        }

        if(ver.size() == 10)
            break;
    }

    printfVer(ver);
    insertsort(ver);
    printfVer(ver);

    int findIdx = search(ver,0,ver.size()-1, 80);
    std::cout << findIdx << endl;
    if(findIdx != -1)
    {
        std::cout << ver[findIdx] << endl;
    }

    return 0;
}