冒泡排序

冒泡排序的核心思想是:两两相邻的元素进行比较

代码如下:

//⽅法1 
void bubble_sort(int arr[], int sz)//参数接收数组元素个数 
{int i = 0;for(i=0; i<sz-1; i++){int j = 0;for(j=0; j<sz-i-1; j++){if(arr[j] > arr[j+1]){int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}
}
int main()
{int arr[] = {3,1,7,5,8,9,0,2,4,6};int sz = sizeof(arr)/sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for(i=0; i<sz; i++){printf("%d ", arr[i]);}return 0;
}//⽅法2 - 优化
void bubble_sort(int arr[], int sz)//参数接收数组元素个数
{int i = 0;for (i = 0; i < sz - 1; i++){int flag = 1;//假设这⼀趟已经有序了int j = 0;for (j = 0; j < sz - i - 1; j++){if (arr[j] > arr[j + 1]){flag = 0;//发⽣交换就说明，⽆序int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}if (flag == 1)//这⼀趟没交换就说明已经有序，后续⽆序排序了break;}
}
int main()
{int arr[] = { 3,1,7,5,8,9,0,2,4,6 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

qsort函数的使用

在cpp帮助文档中,qsort函数是这样定义的

作用是可以比较任意类型的数据,不限于整形,结构体类型等
其需要接受四个参数, 第一个参数可以理解为数组首元素地址, 第二参数为元素个数, 第三个为每个元素的大小, 第四个为一个函数指针,需要使用者自己定义, 函数指针有两个指针类型参数, 返回值为整形,当p1 > p2时返回1, 当p1 < p2 时返回-1, 当p1 = p2 时返回0.

1.使用qsort函数排序整型数据

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//使用qsort函数排序整形数据
int int_cmp(const void* p1, const void* p2) {return (*(int*)p1 - *(int*)p2);
}
int main() {int arr[] = { 1,3,5,7,9,2,4,6,8,0 };qsort(arr, 10, sizeof(arr[0]), int_cmp);for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

2.使用qsort函数排序结构数据

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[20];int age;
};
//假设按照年龄来比较
int cmp_stu_by_age(const void* p1, const void* p2) 
{return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
}
//假设按照名字来比较
int cmp_stu_by_name(const void*p1,const void *p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}
void test1() 
{struct Stu s[] = { {"zhangsan",20},{"lisi",30},{"wangwu",15} };int sz = sizeof(s) / sizeof(s[0]);//qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}int main() 
{test1();return 0;
}

冒泡排序模拟实现qsort函数

//两个整形比较函数
int int_cmp(const void*p1, const void*p2)
{return (*(int*)p1 - *(int*)p2);//强制类型转换成int*,解引用进行比较
}
//进行数据交换
void _swap(void* p1, void* p2,int size)
{for (int i = 0; i < size; i++) {//强制泪下转换成char*,解引用每次交换一个字节的内容,直到i==size为止char temp = *((char*)p1 + i);*((char*)p1 + i) = *((char*)p2 + i);*((char*)p2 + i) = temp;}
}
//模拟实现qsort
void bubble(void* base, int count, int size, int(*cmp)(const void*,const void*))
{for (int i = 0; i < count - 1; i++) {for (int j = 0; j < count - 1 - i; j++) {if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0) //如果比较结果>0则进行数据的交换,把base强制类型转换成字符型指针,并且加上
//j*size大小个字节			{_swap((char*)base + j * size, (char*)base + (j + 1) * size,size);}}}
}int main()
{int arr[] = { 1,3,5,7,9,2,4,6,8,0 };bubble(arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), int_cmp);//这里传递比较整形类型函数for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {printf("%d ",arr[i]);}printf("\n");return 0;
}

今日题目

1. 字符串旋转结果

写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

例如：给定s1 =AABCD和s2 = BCDAA，返回1

给定s1=abcd和s2=ACBD，返回0.

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

问题解析:

本题当然可以将所有旋转后的结果放到一个数组里，然后进行查找，但是这种做法既不好操作，也太费事，但是这题有一个很简单的做法：
其实ABCDE无论怎么旋，旋转后的所有结果，都包含在了ABCDEABCD这个字符串里了。
所以做法很简单，只需要将原字符串再来一遍接在后面，然后找一找待查找的字符串是不是两倍原字符串的子集即可。

代码如下:

int my_cmp(const char *src,const char *find) 
{char temp[256] = { 0 };strcpy(temp, src);strcat(temp, src);return strstr(temp, find) != NULL;
}int main() {char str1[100] = { 0 };char str2[100] = { 0 };scanf("%s %s", str1, str2);int ret = my_cmp(str1, str2);printf("%d\n", ret);return 0;
}

2.杨氏矩阵

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。

要求：时间复杂度小于O(N);

问题解析:

我们仔细分析，不难发现，对于杨氏矩阵老说，右上角和左下角的元素是有特点的。右上角的元素是一行中最大的，一列中最小的。左下角的元素是一行中最小的，是一列中最大的。所以我们可以从右上角或者左下角开始查找。比如：从右上角开始查找的时候，右上角的元素比我们要查找元素小，我们就可以去掉右上角元素所在的这一行；右上角的元素比我们要查找的元素大，我们就可以去掉右上角元素所在的这一列。然后依然找右上角的元素继续和要查找的元素与比较。这样每一次比较去掉一行或者去掉一列。这个查找效率是高于遍历数组元素的，所以时间复杂度是小于O(N)，也满足题目要求。

代码如下:

int find_num(int a[3][3], int x, int y, int f)
{int i = 0;int j = y - 1;while (i < x && j >= 0){if (a[i][j] > f){i++;}else if (a[i][j] < f){j--;}else {return 1;}}return 0;
}
int main() 
{int arr[3][3] = {{1,3,5},{3,5,7},{5,7,9}};int ret = find_num(arr, 3, 3, 6);if (ret == 1) {printf("It has been found!\n");}else {printf("It hasn't been found!\n");}return 0;
}

3.猜凶手

日本某地发生了一件谋杀案，警察通过排查确定杀人凶手必为4个嫌疑犯的一个。

以下为4个嫌疑犯的供词:

A说：不是我。
B说：是C。
C说：是D。
D说：C在胡说
已知3个人说了真话，1个人说的是假话。
现在请根据这些信息，写一个程序来确定到底谁是凶手。

问题解析:

这个题就是按照正常方式，假设凶手是a,b,c,d其中的一个，看是不是满足题目条件，如果满足就找出了凶手。

代码如下:

int main() {int killer = 0;for (killer = 'a'; killer <= 'd';killer++) {if (('a' != killer) + ('c' == killer) + ('d' == killer) + ('d' != killer) == 3) {printf("凶手是:%c", killer);}}return 0;
}

4.杨辉三角

在屏幕上打印杨辉三角。

1

1 1

1 2 1

1 3 3 1

……

问题解析:

能发现数字规律为：d[i][j] = d[i - 1][j] + d[i - 1][j - 1]。所以我们只要按照这个方法填表即可。

代码如下:

void YangHui(int arr[][4], int n)
{for (int i = 0; i < n; i++){for (int j = 0; j <= i; j++){if (i == j || j == 0){arr[i][j] = 1;}else{arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];}}}
}
void printArr(int arr[][4],int n)
{for (int i = 0; i < n; i++){for (int j = 0; j <= i; j++){printf("%d ", arr[i][j]);}printf("\n");}
}
int main() {int arr[4][4] = { 0 };YangHui(arr, 4);printArr(arr, 4);return 0;
}

总结

本文介绍了如何通过冒泡排序实现qsort函数的功能. 首先冒泡排序是一种简单直观的排序算法, 通过比较相邻元素的大小进行交换位置来实现排序, 而qsort是c语言标准库中提供的用于快速排序的函数, 示例中模拟实现了使用qsort对整形排序, 也可以实现对结构数据的排序, 让我们跟进一步理解qsort的底层原理. 如有错误 , 请评论留言 , 如果觉得文章有用的话 , 记得 点 赞 收 藏 !