系列文章目录
深入浅出，408数据结构之顺序表操作详解深入理解链表：从头插法到删除操作，408考研必备！
文章目录
系列文章目录前言1、查找算法1.1 顺序查找1.1.1 在数组中进行顺序查找1.1.2 在链表中进行顺序查找
1.2 二分查找
2、排序算法2.1 冒泡排序2.1.1 数组2.1.2 链表
2.2 选择排序2.3 插入排序2.4 快速排序
总结
前言
在学习数据结构和考研中，查找算法和排序算法是基础而重要的概念。它们在解决问题和优化程序性能方面起着至关重要的作用。本文将深入探讨各种查找和排序算法，帮助您更好地理解和运用它们。
1、查找算法
1.1 顺序查找
顺序查找是一种简单直观的查找方法，它逐个比较待查找元素和数据结构中的每个元素。在实际应用中，顺序查找可以应用于数组和链表等数据结构中。
1.1.1 在数组中进行顺序查找
代码如下：
#include
//算法思路：在循环内进行条件判断
bool basicSearch(int arr[], int len, int num) {
int i;
for (i = 0; i < len; i++) {
if (arr[i] == num) {
return true;
}
}
return false;
}
int main() {
int arr[] = { 131, 127, 147, 81, 103, 23, 7, 79 };
int num = 81;
int len = sizeof(arr) / sizeof(arr[0]);//算出数组的长度
bool ret;
ret=basicSearch(arr, len, num);
if (ret == true) {
printf("找到数值%d", num);
}
else {
printf("未找到数值");
}
}
1.1.2 在链表中进行顺序查找
代码如下：
#include
#include
typedef int Elemtype;
typedef struct LNode {
Elemtype data;
struct LNode* next;
}LNode, * LinkList;
void list_tail_insert(LinkList& L) {
L = (LinkList)malloc(sizeof(LNode));
Elemtype x;
scanf("%d", &x);
LinkList r = L;
LinkList s;
while (x != 9999) {
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
}
void print_list(LinkList L) {
L = L->next;
while (L != NULL) {
printf("%3d", L->data);
L = L->next;
}
printf("\n");
}
//算法思路：定义一个指向链表尾的指针，循环内进行条件判断，找出符合条件的结点
LinkList basicSearch(LinkList L, int num) {
LinkList r = L->next;
while (r != NULL) {
if (r->data == num) {
return r;
}
r = r->next;
}
return NULL;
}
int main() {
LinkList L;
list_tail_insert(L);
print_list(L);
int num = 4;
LinkList result;
result = basicSearch(L, num);
if (result != NULL) {
printf("该数值%d已找到\n", result->data);
}
else {
printf("该数值未找到\n");
}
return 0;
}
1.2 二分查找
二分查找是一种高效的查找算法，适用于有序数组。通过不断缩小查找范围，二分查找能够快速定位目标元素。
代码如下：
#include
//算法思路：先定义两个位置变量left和right，在循环里面，进行mid与左右的条件判断
//根据多个条件判断，修改左右变量，再去进行mid的重新赋值
int binarySearch(int arr[], int len, int num) {
int left = 0;
int right = len - 1;
while (left <= right) {
//需要每次定义mid的位置，因此放在循环内部
int mid = (left + right) / 2;
if (arr[mid] < num) {
//mid在num的左边
left = mid + 1;
}
else if (arr[mid] > num) {
//mid在num的右边
right = mid - 1;
}
else {
//找到了
return mid;
}
}
//退出循环为left>right，则为找不到
return -1;
}
int main() {
int arr[] = { 7, 23, 79, 81, 103, 127, 131, 147 };
int num = 81;
int len = sizeof(arr) / sizeof(arr[0]);
int search = 0;
search=binarySearch(arr, len, num);
printf("找到%d的索引为%d", num, search);
return 0;
}
2、排序算法
2.1 冒泡排序
冒泡排序是一种简单直观的排序算法，通过多次遍历数据，将较大（或较小）的元素逐步交换至正确的位置。
动画如下：
2.1.1 数组
代码如下：
#include
//算法思路：定义两个循环，在外循环执行进行几轮的交换，内循环执行每两个元素比较交换位置的次数
void bubbleSort(int arr[], int len) {
//外循环：表示我要执行多少轮。 如果有n个数据，那么执行n - 1 轮
for (int i = 0; i < len - 1; i++) {
//内循环：每一轮中我如何比较数据并找到当前的最大值
//-1：为了防止索引越界
//-i：提高效率，每一轮执行的次数应该比上一轮少一次。
for (int j = 0; j < len - 1 - i; j++) {
//排序后数组从小到大排序
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = { 2, 4, 5, 3, 1 };
int len = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, len);
for (int i = 0; i < len; i++) {
printf("%3d", arr[i]);
}
return 0;
}
2.1.2 链表
代码如下：
#include
#include
typedef int Elemtype;
typedef struct LNode {
Elemtype data;
struct LNode* next;
}LNode,*LinkList;
void listTailCreate(LinkList& L) {
L = (LinkList)malloc(sizeof(LNode));
LinkList s;
LinkList r = L;
Elemtype x;
printf("请输入链表的数值，以9999为终\n");
scanf("%d", &x);
while (x != 9999) {
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
}
void printList(LinkList L) {
L = L->next;
while (L) {
printf("%3d", L->data);
L = L->next;
}
printf("\n");
}
//算法思路：定义镶嵌循环，外循环表示进行了几轮，拿着链表的长度-1个结点元素进行比较
//无需知道链表的长度，由指向链表尾的指针p不为空可进行判断
//内循环表示与其他元素进行比较，条件判断符合进行位置的交换
void sortList(LinkList L) {
if (L == NULL || L->next == NULL) {
return; // 如果链表为空或只有一个元素，则无需排序
}
LinkList p, q;
for (p = L->next; p != NULL; p = p->next) {
//从p的下一个结点开始
for (q = p->next; q != NULL; q = q->next) {
if (p->data > q->data) {
// 交换 p 和 q 指向的元素
Elemtype temp = p->data;
p->data = q->data;
q->data = temp;
}
}
}
}
int main() {
LinkList L;
listTailCreate(L);
printf("创建的链表为：\n");
printList(L);
printf("排序后的链表为：\n");
sortList(L);
printList(L);
return 0;
}
2.2 选择排序
选择排序是另一种常见的排序算法，它通过多次选择最小（或最大）的元素，逐步构建有序序列。
动画如下：
代码如下：
#include
//算法思路：进行双循环，外循环表示进行了几轮比较
//内循环表示：拿着外循环指向的结点与其后面的所有元素进行比较，条件判断符合进行位置的交换
void selectSort(int arr[], int len) {
//外循环：进行了几轮比较，一共是len-1次
for (int i = 0; i < len - 1; i++) {
//内循环：拿着i和i后面的数据进行交换，所以得加1
for (int j = i + 1; j < len; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
int main() {
int arr[] = { 2, 4, 5, 3, 1 };
int len = sizeof(arr) / sizeof(arr[0]);
selectSort(arr, len);
for (int i = 0; i < len; i++) {
printf("%3d", arr[i]);
}
return 0;
}
2.3 插入排序
排序思路：将0索引的元素到N索引的元素看做是有序(依次从小到大)的，把N+1索引的元素到最后一个当成是无序(大小无顺序)的。
遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
动画如下：
代码如下：
#include
//算法思路：先用一个循环找出无序的首元素索引，然后用嵌套循环，
//外循环进行遍历，从startIndex开始到最后一个元素，得到无序数据的每一个元素
//内循环，拿着外循环得到的元素，与有序数据的每个元素进行大小判断交换位置
void insertSort(int arr[], int len) {
//1.找到无序的那一组数组是从哪个索引开始的。
int startIndex;
for (int i = 0; i < len; i++) {
//如果前一个元素大于后一个
if (arr[i] > arr[i + 1]) {
//找到并定义无序数据的首元素索引
startIndex = i + 1;
break;
}
}
//2.遍历从startIndex开始到最后一个元素，依次得到无序的那一组数据中的每一个元素
for (int i = startIndex; i < len; i++) {
//先记录当前要插入数据的索引，防止后面操作修改i
int j = i;
//将无序的第i个元素，在有序数据中从后往前，如果后一个元素小于前一个元素，需要交换
while (j > 0) {
//符合条件进行交换
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
j--;//继续跟前面的元素进行对比交换
}
}
}
int main() {
int arr[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
int len = sizeof(arr) / sizeof(arr[0]);
insertSort(arr, len);
for (int i = 0; i < len; i++) {
printf("%3d", arr[i]);
}
return 0;
}
2.4 快速排序
排序思路：
从数列中挑出一个元素，一般都是左边第一个数字，称为 “基准数”; (如果以0索引为基准数就要end先走，如果以最大索引为基准，就要start先走)！！！！！ 即3、4步步骤进行交换 创建两个指针，一个从前往后走，一个从后往前走。 先执行后面的指针，找出第一个比基准数小的数字 再执行前面的指针，找出第一个比基准数大的数字 交换两个指针指向的数字 继续偏转 直到两个指针相遇 将基准数跟指针指向位置的数字交换位置，称之为：基准数归位。 第一轮结束之后，基准数左边的数字都是比基准数小的，基准数右边的数字都是比基准数大的。 把基准数左边看做一个序列，把基准数右边看做一个序列，让这两个序列自己内部按照刚刚的规则递归排序 最后分成许多的序列递归完成最终的排序
代码如下：
#include
void quickSort(int arr[], int i, int j) {
//定义两个变量记录要查找的范围
int start = i;
int end = j;
//递归的出口，当到了出口，就不会执行下面的循环交换操作
if (start > end) {
return;
}
//记录基准数，下面的start会改变，这里是i
int baseNum = arr[i];
//利用循环找到要交换的数字
while (start != end) {
//利用end，从后往前开始找，找到比基准数小的数字
while (true) {
//异常情况或者找到了
if (end <= start || arr[end] < baseNum) {
break;
}
//不符合找到的条件，继续偏转
end--;
}
while (true) {
//异常情况或者找到了
if (end <= start || arr[start] > baseNum) {
break;
}
//不符合找到的条件，继续偏转
start++;
}
//找到之后，将end和start指向的元素进行交换
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//当start和end指向了同一个元素的时候，那么上面的循环就会结束
//表示已经找到了基准数在数组中应存入的位置
//下面进行基准数归位
//就是拿着这个范围中的第一个数字，跟start(或end)指向的元素进行交换
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
//确定基准数左边的范围，此时左边都会比基准数小，让他们内部重复刚刚所做的事情
//i依然是0
quickSort(arr, i, start - 1);
//确定基准数右边的范围，此时右边都会比基准数大，让他们内部重复刚刚所做的事情
//j依然是len-1
quickSort(arr, start + 1, j);
}
int main() {
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, len - 1);
for (int i = 0; i < len; i++) {
printf("%3d", arr[i]);
}
return 0;
}
总结
在这篇博客文章中，我详细介绍了查找算法和排序算法的各种技术和方法。希望这些内容能够帮助您更好地理解和运用算法，提升您在编程和数据处理方面的能力。如果您对这些内容有任何疑问或想要进一步探讨，欢迎在评论区留言，我会尽力解答您的问题。感谢您的阅读！
参考文章
发表评论