深圳龙华做网站公司,建筑焊工证查询网站官方网,wordpress wp_loginout,网站开发翻译一、冒泡排序
二、冒泡排序优化排各种类型数据 文章目录一、冒泡排序二、冒泡排序优化排各种类型数据冒泡排序
冒泡排序原理#xff1a;两两相邻元素进行比较
初级版
void bulle_sort(int* a, int sz)
{int i 0;for (int i 0; i sz-1; i){int j 0; for (j 0; j…一、冒泡排序
二、冒泡排序优化排各种类型数据 文章目录一、冒泡排序二、冒泡排序优化排各种类型数据冒泡排序
冒泡排序原理两两相邻元素进行比较
初级版
void bulle_sort(int* a, int sz)
{int i 0;for (int i 0; i sz-1; i){int j 0; for (j 0; j sz - 1 - i; j){if (a[j] a[j1]){int tmp a[j];a[j] a[j 1];a[j 1] tmp;}}}
} 这是冒泡排序初级版不管其原内容是否有序都会进行比较如果原内容原本就是有序的再每个都进行比较效率就会低下那么这时候可以改进一下想一个标记变量来记录是否有序如int falg 0; 如果无序的情况下falg会变为1有序的情况下falg保持0不变如果一趟下来falg 为0 不变那么就是有序的就不用再比较后面趟数了这样使其在有序的情况下时间复杂度为On),大大提高了效率 改进版
void bulle_sort(int* a, int sz)
{int i 0;int falg 0;for (int i 0; i sz-1; i){int j 0; for (j 0; j sz - 1 - i; j){if (a[j] a[j1]){int tmp a[j];a[j] a[j 1];a[j 1] tmp;falg 1;}}if (falg 0){break;}}
}冒泡排序优化排各种类型数据 上面冒泡排序可以发现只能够排序整形 那要是我们想利用冒泡来排其他不同类型应该如何实现呢这里就引入c语言里的一个库函数qsort(),在cplusplus上搜索qosrt 可以发现这是一个排序函数且qsort函数有四个参数void * base目标数组待排序的起始地址size_t num待排序数组大小size_t表示无符号类型由于数组大小不可能为负数因此设置为size_t更为合适,size_t size,数组中每个元素是多少字节其实就是每个元素是什么类型
int (*compar)(const void*,const void*)这是一个函数指针是比较函数的函数指针而comper实现的是比较功能 比较函数 由于比较类型不知道是什么类型的因此用void*这里这个设计十分合理void*,void*存的是要比较两个元素的地址是因为设计者在设计时不知道我们要比较什么类型的因为void*指针可以接收任意类型变量的地址。comper函数返回类型为in类型第一个比第二个于返回1相等返回0小于返回-1 qsort函数运用
int comper(const void* s1, const void* s2)
{return *((int*)s1) - *((int*)s2);//由于我们自己使用时知道了是什么类型因此强转为该类型就可//然后再对其解引用就可以相互进行比较了
}
int main()
{int arr[] { 9,8,7,6,5,4,3,2,1 };int sz sizeof(arr) / sizeof(arr[0]);//bulle_sort(arr, sz);qsort(arr, sz, sizeof(arr[0]), comper);for (int i 0; i sz; i){printf(%d , arr[i]);}printf(\n);return 0;
}可以发现出了警告是qsort未定义这是因为没有包含它所需的头文件 可以往下翻找到它该用什么头文件 以qsort排序结构体 #includestring.h
typedef struct Stu
{char name[20];int age;
}Stu;
int comper_stu_by_name(const void* s1, const void* s2)
{//按照名字比较两个字符串比较是不能直接相减用库函数strcmp进行比较//强制类型转换为结构体指针然后再-找到结构体成员变量namereturn strcmp(((Stu*)s1)-name , ((Stu*)s2)-name);//由于我们自己使用时知道了是什么类型因此强转为该类型就可//得到其地址再对其解引用就可以相互进行比较了
}int main()
{Stu s[3] { {zhangsan,20},{wangwu,30},{lisi,50} };qsort(s, sizeof(s)/sizeof(s[0]), sizeof(s[0]), comper_stu_by_name);for (int i 0; i sizeof(s)/sizeof(s[0]); i){printf(%s %d\n, s[i].name, s[i].age);}
}strcmp比较字符串函数 strcmp返回类型为int qsort可以实现任意类型的数据的排序 以冒泡模拟qsort
//比较时需要比较什么类型自己可以定义然后强转
//需要排不同类型只需要在这里更改就可以了
int comper(void* s1, void* s2)
{return *((int*)s1) - *((int*)s2);
}void swap(char* buf1, char* buf2, int width)
{int i 0;//width是数组中每个元素的字节大小其实以我们来看知道width就可以知道是什么类型for (i 0; i width; i){//将每个字节都交换char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}//与qsort函数内部一致
//比较类型不明确所有void*
void bulle_qsort( void* a, size_t sz, size_t width, int (*comper)(const void* s1, const void* s2))
{size_t i 0;int falg 0;for (int i 0; i sz-1; i){size_t j 0; for (j 0; j sz - 1 - i; j){if (comper((char*)aj*width,(char*)a(j1)*width)0)//实现比较交换,且由于不知道要比较什么类型那么我们只有使用偏移量比较{swap((char*)a j * width, (char*)a (j 1) * width, width);//由于不知道类型那么就交换每个字节把每个元素大小传过去falg 1;}}if (falg 0){break;}}
}int main()
{int a[] { 9,8,7,6,5,4,3,2,1 };int sz sizeof(a) / sizeof(a[0]);//这里可以排任意类型的数据我这里以整形数组模拟bulle_qsort(a, sizeof(a) / sizeof(a[0]), sizeof(a[0]), comper);for (int i 0; i sz; i){printf(%d , a[i]);}return 0;
}冒泡模拟实现qsort就到这里了有兴趣的小伙伴可以区试试其他类型的排序吧
