当前位置：首页 > article >正文

数据结构——查找算法和排序算法

article 2025/3/3 17:22:05

1、查找算法

需求：封装一个函数，写出在一个整型数组中查找目标元素的算法，找到了返回该元素所在索引；找不到返回-1

1.1 顺序查找

问题：在一组数据中查找指定的元素
思路：按顺序遍历出来，一个一个对比

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int find_index(int* arr, int length, int val) {
   //顺序查找的时间复杂度：O(n)
   for (int i = 0;i < length;i++) {
       if (*(arr + i) == val) {
           return i;
       }
   }
   return -1;
}

int main() {
   printf("查找算法！\n");
   int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
   int res = find_index(arr, 10, 200);
   if (res == -1) {
       printf("没有此元素！\n");
   }else {
       printf("目标元素的索引为：%d\n", res);
   }
   return 0;
}

1.2 折半查找（二分查找）

前提条件：查找前数组必须是有序（默认的是从小到大）的
思路：每次进行对半分，判断目标元素是在中间元素的左边还是右边，以此类推

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int find_indexB(int* arr, int length, int val) {
   //顺序查找的时间复杂度：O(log2n)
   int min = 0, max = length - 1, mid = 0;
   do {
       mid = (min + max) / 2;
       if (val > arr[mid]) {
           //说明目标元素在右边
           min = mid + 1;
       }else if (val < arr[mid]) {
           //说明目标元素在左边
           min = mid - 1;
       }else {
           //找到了
           return mid;
       }
   } while (min <= max);
   return -1;
}

int main() {
   printf("查找算法！\n");
   int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
   int res = find_indexB(arr, 10, 9);
   if (res == -1) {
       printf("没有此元素！\n");
   }else {
       printf("目标元素的索引为：%d\n", res);
   }
   return 0;
}

2、排序算法

2.1 冒泡排序

问题：给一个整型数组进行排序
思路：每次比较相邻的两个数，左边>右边，大数右移（交换两个数的值）

核心步骤：
   数组长度：len
   比较的趟数i：len-1
   每趟比较的次数（不是定值）：len-1-i

#include <stdio.h>
void Bubblesort(int* arr, int len) {
   //外层循环决定趟数
   for (int i = 0;i < len - 1;i++) {
       //内层循环决定比较的次数
       for (int j = 0;j < len - 1 - i;j++) {
           if (arr[j] > arr[j + 1]) {
               int temp = 0;
               temp = arr[j];
               arr[j] = arr[j + 1];
               arr[j + 1] = temp;
           }
       }
   }
}
int main() {
   int arr[10] = { 5,7,3,6,4,5,5648,68,64,46 };
   Bubblesort(arr, 10);
   for (int i = 0;i < 10;i++) {
       printf("%d ", arr[i]);
   }
   return 0;
}

2.2 选择排序

思路：每次从待排序列中找到最小值，放到前面，直到找完

核心步骤：对于n个元素的数组
一共选择多少次：n次
每次查找的待排序列元素的索引的和最大值：最小值就是当前选择的次数；最大值就是数组的最大索引值

#include <stdio.h>

void select_sort(int* arr, int len) {
   int min = 0;
   for (int i = 0;i < len;i++) {
       for (int j = i; j < len; j++){
           if (arr[min] > arr[j]) {
               //交换位置
               int temp = arr[min];
               arr[min] = arr[j];
               arr[j] = temp;
           }
       }
       min++;
   }
}

int main() {
   int arr[10] = { 5,7,3,6,4,5,5648,68,64,46 };
   select_sort(arr, 10);
   for (int i = 0;i < 10;i++) {
       printf("%d ", arr[i]);
   }
   printf("\n");
   return 0;
}

2.3 插值排序

思路：在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序

但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止

#include <stdio.h>

//1、在待排的有序序列中插入目标元素
//2、假设待排序列的第0个元素是有序序列，再将后面的元素依次插入到这个有序序列中来
void insert_sort(int* arr, int len) {
   int i = 0; //假设待排序列的第0个元素是有序序列
   for (int i = 1;i < len;i++) {
       int end = i; //待插元素插入到目标元素的索引
       int temp = arr[i]; //待插元素
       while (end > 0) {
           if (arr[end - 1] > temp) {
               //交换位置
               arr[end] = arr[end - 1];
               end--;
           }else {
               break;
           }
       }
       arr[end] = temp; //将数据插入到有序序列
   }
}
int main() {
   int arr[10] = { 5,7,3,6,4,5,5648,68,64,46 };
   insert_sort(arr, 10);
   for (int i = 0;i < 10;i++) {
       printf("%d ", arr[i]);
   }
   printf("\n");
   return 0;
}