C语言实现查找、排序操作
现有一顺序表，表中元素分别为{51,38,79,22,91,105,33,52,16,112}，分别编写函数实现以下操作：
A、采用简单插入排序法实现对顺序表的排序，显示每一趟的排序结果；
B、采用简单冒泡排序法实现对顺序表的排序，显示每一趟的排序结果；
C、采用简单选择排序法实现对顺序表的排序，显示每一趟的排序结果；
D、编写顺序查找函数；
E、编写二分查找函数。
编写主函数main，依次完成：初始化顺序表 (调用顺序查找函数，在顺序表中查找关键字为52和关键字为36的元素，分别显示查找结果 (调用简单插入排序、简单冒泡排序、简单选择排序分别实现顺序表的排序，并显示结果 (调用二分查找函数，查找关键字为22的元素，显示查找结果。
# 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;
}
A. 插入排序
void insertion_sort(int arr[],int len){
for(int i=1;i<len;i++){
int key=arr[i];
int j=i-1;
while((j>=0) && (key<arr[j])){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
B. 冒泡排序
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
C, 选择排序
void swap(int *a,int *b) //交換兩個變數
{
int temp = *a;
*a = *b;
*b = temp;
}
void selection_sort(int arr[], int len)
{
int i,j;
for (i = 0 ; i < len - 1 ; i++)
{
int min = i;
for (j = i + 1; j < len; j++) //走訪未排序的元素
if (arr[j] < arr[min]) //找到目前最小值
min = j; //紀錄最小值
swap(&arr[min], &arr[i]); //做交換
}
}
完整代码
#include<stdio.h>
void insertion_sort(int arr[], int len) ; // 插入排序
void bubble_sort(int arr[], int len) ; // 冒泡排序
void swap(int *a, int *b); // 交换元素
void selection_sort(int arr[], int len) ; // 选择排序
void print_map(int arr[], int len, int n); // 打印 列表
int in_order_to_find(int arr[], int len, int num) ; // 顺序查找
int binary_search(int key, int a[], int n); // 二分查找
int main() {
int list[10] = {51, 38, 79, 22, 91, 105, 33, 52, 16, 112};
// 顺序找 52
int flag_52 = 0;
flag_52 = in_order_to_find(list, 10, 52);
if ( flag_52 >= 0 ) {
printf("顺序查找法找到52的下标为 %d \n", flag_52);
} else {
printf("没有找到 52 这个元素\n");
}
// 顺序找 36
int flag_36 = 0;
flag_36 = in_order_to_find(list, 10, 36);
if ( flag_36 >= 0 ) {
printf("顺序查找法找到36的下标为 %d \n", flag_36);
} else {
printf("没有找到 36 这个元素\n");
}
// 插入排序
int list_1[10] = {51, 38, 79, 22, 91, 105, 33, 52, 16, 112};
insertion_sort(list_1, 10);
// 冒泡排序
int list_2[10] = {51, 38, 79, 22, 91, 105, 33, 52, 16, 112};
bubble_sort(list_2, 10);
// 选择排序
int list_3[10] = {51, 38, 79, 22, 91, 105, 33, 52, 16, 112};
selection_sort(list_3,10);
// 二分找 22
binary_search(22,list_3,10);
}
void insertion_sort(int arr[], int len) {
printf("插入排序:\n");
for (int i = 1; i < len; i++) {
int key = arr[i];
int j = i - 1;
while ((j >= 0) && (key < arr[j])) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
print_map(arr, len, i);
}
}
void bubble_sort(int arr[], int len) {
printf("冒泡排序\n");
int i, j, temp, flag = 1;
for (i = 0; i < len - 1; i++) {
for (j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
print_map(arr, len, flag++);
}
}
}
}
void swap(int *a, int *b) { //交換兩個變數
int temp = *a;
*a = *b;
*b = temp;
}
void selection_sort(int arr[], int len) {
printf("选择排序\n");
int i, j;
for (i = 0 ; i < len - 1 ; i++) {
int min = i;
for (j = i + 1; j < len; j++) //走訪未排序的元素
if (arr[j] < arr[min]) //找到目前最小值
min = j; //紀錄最小值
swap(&arr[min], &arr[i]); //做交換
}
}
void print_map(int arr[], int len, int n) {
if ( n > 0 ) {
printf("第%d趟的结果 ：", n);
}
for ( int i = 0 ; i < len ; i++ ) {
printf("%d ", arr[i]);
}
printf("\n");
}
int in_order_to_find(int arr[], int len, int num) {
// 顺序查找
for ( int i = 0 ; i < len ; i++ ) {
if ( arr[i] == num ) {
return i;
}
}
// 没有找到
return -1;
}
int binary_search(int key, int a[], int n) {
// 二分查找
int low, high, mid, count = 0, count1 = 0;
low = 0;
high = n - 1;
while (low < high) { //査找范围不为0时执行循环体语句
count++; //count记录査找次数
mid = (low + high) / 2; //求中间位置
if (key < a[mid]) //key小于中间值时
high = mid - 1; //确定左子表范围
else if (key > a[mid]) //key 大于中间值时
low = mid + 1; //确定右子表范围
else if (key == a[mid]) { //当key等于中间值时，证明查找成功
printf("查找成功!\n 查找 %d 次! 元素 %d 的下标为 %d ", count, key, mid); //输出査找次数及所査找元素在数组中的位置
count1++; //count1记录查找成功次数
break;
}
}
if (count1 == 0) //判断是否查找失敗
printf("查找元素 %d 失敗!",key); //査找失敗输出no found
return 0;
}
- 建议你看下这篇博客👉 ：C语言解决排序问题