【C语言】冒泡排序的快排模拟

这篇具有很好参考价值的文章主要介绍了【C语言】冒泡排序的快排模拟。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

说到排序,必然绕不开两个排序,冒泡排序快速排序
冒泡排序是大多数人的启蒙排序,因为他的算法简单。但效率不高,便于新手理解;
而快速排序是集大成之作,效率最高,使用最为广泛。

今天这篇文章带来如何使用qsort(quick sort,快速排序),和如何使用冒泡排序的快速排序的模拟。
也会在不久后讲解几大排序的算法。

冒泡排序:

开始之前先来回顾一下冒泡排序的实现

冒泡排序的思想是让数组的元素从头开始两两比较,大的放在后边(根据情况定),解决完一个元素在进行下一个,如下图。

【C语言】冒泡排序的快排模拟,c语言,算法,数据结构,c++,开发语言
从上图中我们发现排序第一趟要进行5次(len-1次)
而一趟可以解决1个元素的位置(当剩最后一个元素时不用排序)
所以可以得到一共需要进行5趟(len-1趟)
故可以写一个外层for循环模拟趟数,循环变量为i,从0开始
【C语言】冒泡排序的快排模拟,c语言,算法,数据结构,c++,开发语言
第二次时就进行4
每趟都会减少一个需要排序的元素,与外层循环变量i有关
故我们控制一趟次数的内循环可以根据i来写出适当的表达式

代码实现:

void bubble_sort(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 tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int len = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

这样一个朴实无华的冒泡排序就完成了。
接下来研究qsort

一一一一一一一一一分割线一一一一一一一一

qsort的参数设计:

登录网站cpulsplus.com,可以查询qsort函数信息

cpp网站链接
【C语言】冒泡排序的快排模拟,c语言,算法,数据结构,c++,开发语言
觉得难以理解不要紧,下边有详细的解释。

我们发现qsort有4个参数

void qsort (void* base, 
            size_t num, 
            size_t size,
            int (*compar)(const void*,const void*));
参数:

1.void*base
大家看到这个肯定就懵了,啥是void*
void*也是一种指针类型,不过他可以接收任意类型的数据;
什么?任意类型,这也就说明qsort不只可以排序整形,字符,甚至结构体都可以排序
base就是数组的数组名,因为知道数组在哪里才可以进行排序。

2.size_t num
size_tsizeof这个操作符的返回值类型,本质是unsigned类型。
num是指数组中元素个数的多少

3.size_t size
排序有了数组名,有了个数就可以排序了吗?
想到冒泡排序好像就是这样,但是,别忘记qsort可以排序任意类型,这也就意味着我们不仅需要知道数组名与元素个数,还需要知道排序的是什么类型,也就是多少字节,size就是数组中每个元素的字节大小。

4.int (*compar)(const void*,const void*))
仔细看,发现他像什么?
没错是个函数指针,他的类型是int (*)(const void*,const void*)),为什么qsort需要传参一个函数指针,因为qsort需要知道两个数据间是如何比较,这取决于使用者的想法,比如结构体你想按照其中的字符串比较还是整形比较

这是比较函数的返回值:
【C语言】冒泡排序的快排模拟,c语言,算法,数据结构,c++,开发语言
当返回值小于0 ,p1指向元素被排在p2指向元素左边。即[*p1, *p2];

当返回值大于0 ,p1指向元素被排在p2指向元素右边。即[*p2, *p1];

当返回值等于0 ,p1指向元素和p2指向元素顺序不确定。

即e1指向的值大于e2指向的值,返回正数,否则返回负数,相等时返回0(默认升序)
知道了参数是什么,那我们应该怎样使用呢?
不要看着感觉复杂,其实很简单

#include <stdio.h>
//qosrt函数的使用者得实现一个比较函数
int int_cmp(const void * p1, const void * p2)
{
    return (*( int *)p1 - *(int *) p2);
    //因为我们比较的是int类型,所以需要将e1,e2强转后再解引用
    //void*类型是不可以解引用的
}
//注意比较函数的返回值
e1>e2返回一个正数
int main()
{
    int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    int i = 0;
    qsort(arr, 
          //数组名
          sizeof(arr) / sizeof(arr[0]), 
          //数组的元素个数
          sizeof (int),
          //每个元素类型
          int_cmp);
          //比较函数
    for (i = 0; i< sizeof(arr) / sizeof(arr[0]); i++)
    {
        printf( "%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

这就实现了如何使用qsort。

一一一一一一一一一分割线一一一一一一一一

冒泡排序的快排模拟:

那么如果我们将qsort中的参数放到冒泡排序中,该如何以qsort的方式实现冒泡排序呢?
我们发现,整体的逻辑不需要改动,需要改动的是两个元素的比较需要使用我们自己定义的cmp函数
那么请看代码,会在代码中解释大家的各种疑问
代码实现:

先来看函数的主体部分:,只是改写了参数

int main()
{
	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 ,0};
	int len = sizeof(arr) / sizeof(arr[0]);
	//参数改成qsort形式的参数
	bubble_sort(arr, len, sizeof(arr[0]), cmp);
	for (int i = 0; i < len; i++) 
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

然后看冒泡排序的实现:

//比较函数
int cmp(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}

void bubble_sort(void*base,int len,int width,int(*cmp)())
{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++)
		{
		if (cmp((char*)base+width*j, (char*)base + width * (j+1))> 0)
//因为base是void*类型,需要强转成(char*),因为char*是最小的单位,
//容易操作,同时利用width和j得出当前元素与下一个元素的地址,
//在cmp中强转为int*进行比较
//当返回值为正数1说明e1指向的数大于e2指向的,需要交换
			{
				swap((char*)base + width * j, width);
				//交换函数
			}
		}
	}
}

交换函数:
共循环width次,因为width为字节大小,而我们是char*类型,只有1字节,我们通过for循环来交换

void swap(char* p,int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *(p+i);
		*(p+i) = *(p + i + width);
		*(p + i + width) = tmp;
	}
}

【C语言】冒泡排序的快排模拟,c语言,算法,数据结构,c++,开发语言
一一一一一一一一一分割线一一一一一一一一
整体代码:

int cmp(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}
void swap(char* p,int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *(p+i);
		*(p+i) = *(p + i + width);
		*(p + i + width) = tmp;
	}
}
void bubble_sort(void*base,int len,int width,int(*cmp)())
{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++)
		{
			if (cmp((char*)base+width*j, (char*)base + width * (j+1)) > 0)
			{
				swap((char*)base + width * j, width);
			}
		}
	}
}

int main()
{
	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 ,0};
	int len = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, len, sizeof(arr[0]), cmp);
	for (int i = 0; i < len; i++) 
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

欢迎纠错与交流!文章来源地址https://www.toymoban.com/news/detail-696856.html

到了这里,关于【C语言】冒泡排序的快排模拟的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法-选择&冒泡&快排&计数

        一:选择排序     场景:找出一个班上身高最高的人你会怎么找?A B C D A B 选择排序的思路和插入排序非常相似,也分已排序和未排序区间。但选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。但是不像插入排序会移动数组 选择排序会每次

    2024年02月09日
    浏览(41)
  • 【基础算法】八大排序算法:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序(快排),归并排序,计数排序

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年02月01日
    浏览(45)
  • 十大排序算法(冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序)

    目录 一、冒泡排序: 二、插入排序: 三、选择排序: 四、希尔排序: 五、堆排序: 六、快速排序: 6.1挖坑法: 6.2左右指针法 6.3前后指针法: 七、归并排序: 八、桶排序: 九、计数排序: 9.1绝对映射: 9.2现对映射: 十、基数排序:  1、思路: 通过对待排序序列从前

    2024年03月11日
    浏览(54)
  • c语言经典算法—二分查找,冒泡,选择,插入,归并,快排,堆排

             1、前提条件:数据有序,随机访问;          2、实现:递归实现,非递归实现          3、注意事项:                 循环退出条件:low =high,low = high.说明还有一个元素,该元素还要与key进行比较                 mid的取值:mid=(low + high)/2;mid = l

    2024年02月05日
    浏览(44)
  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(48)
  • 冒泡排序 && 快排(hoare递归)

    今天要讲一个是冒泡排序,进一个是快排,首先是冒泡排序,我相信大家接触的第一个排序并且比较有用的算法就是冒泡排序了,冒泡排序是算法里面比较简单的一种,所以我们先看看一下冒泡排序 还是个前面一样,我们先看一下单趟排序 假设我们又以下数组 我们想要对他

    2023年04月08日
    浏览(33)
  • c语言用冒泡排序模拟实现qsort排序

    1、简单介绍冒泡排序 冒泡排序就是两两相邻元素进行比较,如果不满足顺序就进行交换。现有一组整数,将其用冒泡排序实现排序为升序。 假设有这样一组整数:9 8 7 6 5    由此可知,如果一个整型数组有num个元素,则需走num-1趟,若走在第i趟,则在第i趟内需要比较num-1

    2024年02月15日
    浏览(45)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(69)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(81)
  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包