C语言实现查找、排序操作

Question

现有一顺序表，表中元素分别为{51,38,79,22,91,105,33,52,16,112}，分别编写函数实现以下操作：
A、采用简单插入排序法实现对顺序表的排序，显示每一趟的排序结果；
B、采用简单冒泡排序法实现对顺序表的排序，显示每一趟的排序结果；
C、采用简单选择排序法实现对顺序表的排序，显示每一趟的排序结果；
D、编写顺序查找函数；
E、编写二分查找函数。
编写主函数main，依次完成：初始化顺序表 (调用顺序查找函数，在顺序表中查找关键字为52和关键字为36的元素，分别显示查找结果 (调用简单插入排序、简单冒泡排序、简单选择排序分别实现顺序表的排序，并显示结果 (调用二分查找函数，查找关键字为22的元素，显示查找结果。

Answer 1

# include<stdio.h>
//冒泡排序
void BubbleSort(int* arr, int n)
{   
    int i,count=1;
    int end = n;
    while (end)
    {
        int flag = 0;
        for (int i = 1; i < end; ++i)
        {
            if (arr[i - 1] > arr[i])
            {
                int tem = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = tem;
                flag = 1;
            }
        }
        if (flag == 0)
        {
            break;
        }
        --end;
        //输出每一趟的结果
    printf("第%d趟排序：",count++);
    for(i=0;i<n;i++)
     {
       printf("%d  ",arr[i]);
     }
     printf("\n");
    }
}

//插入排序
void InsertSort(int* arr, int n)
{ 
    int k,count=1;
    for (int i = 0; i < n - 1; ++i)
    {
        //记录有序序列最后一个元素的下标
        int end = i;
        //待插入的元素
        int tem = arr[end + 1];
        //单趟排
        while (end >= 0)
        {
            //比插入的数大就向后移
            if (tem < arr[end])
            {
                arr[end + 1] = arr[end];
                end--;
            }
            //比插入的数小，跳出循环
            else
            {
                break;
            }
        }
        //tem放到比插入的数小的数的后面
        arr[end  + 1] = tem;
        //代码执行到此位置有两种情况:
        //1.待插入元素找到应插入位置（break跳出循环到此）
        //2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
         //输出每一趟的结果
         printf("第%d趟排序：",count++);
         for(k=0;k<n;k++)
          {
            printf("%d  ",arr[k]);
          }
          printf("\n");
    }
}
//选择排序
void selectSort(int array[] , int size)
{
    int i,j,k,min,temp,count=1;
    //需要的主循环趟数比实际的数据个数少1
    for(i = 0; i < size - 1;i++)
    {
        min = i;
        for(j = i + 1; j < size; j++ )
        {
            if(array[j] < array[min])
            {
                min = j;
            }
        }
        if(min != i)
        {
            temp = array[min];
            array[min] = array[i];
            array[i] = temp;
        }
        printf("第%d趟排序：",count++);
         for(k=0;k<size;k++)
          {
            printf("%d  ",array[k]);
          }
          printf("\n");
    }
}
// 顺序查找
int Search_Sq01(int *num, int len, int key)
{
    int i;
    for(i = 1; i <= len; i++)
    { 
        if (num[i] == key)
        {
            return i;
        }
    }
    return -1;
}
int Binary_search(int arr[],int key,int n)
{
    
    int low = 0;    //定义low为0号元素
    int high = n - 1; //定义high为下标最大的元素
    int mid;        //数组中间元素的下标
    
    while (low <= high)        //只要低号位元素小于或等于高号位元素，说明还没查找到元素，循环继续
    {
        mid = (low + high) / 2;        //中间元素下标定义
        if (arr[mid] < key)        //当所查找的元素比中间值大，说明要查找的元素在右半区，
        {    
            low = mid + 1;        //key在右半区，改变low的值
        }
        else if (arr[mid] > key) //当所查找的元素比中间值小，说明要查找的元素在左半区，
        {
            high = mid - 1;        //key在左半区，改变high的值
        }
        else                    //如果前面两个条件都不满足，说明已经找到key 满足条件 key==mid  返回mid
        {
            return mid;        
        }
    }
    return -1;    //当跳出循环还没有返回值，说明没找到想要的元素，返回-1
}

 

int main(){
    int i;
    int index;
int arr1[10]={51,38,79,22,91,105,33,52,16,112};

//冒泡排序
printf("冒泡排序：\n");
BubbleSort(arr1, 10);
printf("\n");
//插入排序
printf("插入排序：\n");
InsertSort(arr1, 10);
printf("\n");
//选择排序
printf("选择排序：\n");
selectSort(arr1,10);
printf("\n");
// 顺序查找

index=Search_Sq01(arr1,10,52);
printf("顺序查找52的index:%d\n",index);
index=Search_Sq01(arr1,10,36);
printf("\n");
if(index==-1){printf("没有该元素\n");}
else{printf("顺序查找36的index:%d\n",index);}
//二分查找，只能是排序后的数组，
printf("\n");
index=Binary_search(arr1,22,10);
if(index==-1){printf("没有该元素\n");}
else{printf("二分查找22的index:%d\n",index);}
    return 0;
}