从冒泡到模拟q sort函数——初见排序算法的探索和思考

小此方

发布于 2025-12-24 17:35:20

文章被收录于专栏：数据结构博客专栏数据结构博客专栏

国庆中秋喜相连，万家团圆乐同庆。

各位小伙伴们大家好，我是此方，在此，先祝大家双节快乐！

我们都知道排序有很多种：例如冒泡排序，插入排序，快速排序，等等很多种。

而冒泡排序，是各种计算机语言中最经典的一种排序算法。

今天我将从冒泡排序开始，到实现qsort函数的模拟。逐层深入，探索排序问题。

并给出鄙人的一些拙见。

上正文：

一，冒泡排序：最经典的排序算法

假如有一个十元素整型数组，他是完全倒着排序的：就像这样

now，我们要按照从小到大的顺序将这十个数字重新排列。

如果我们想要用冒泡排序：那么他的逻辑应该是这样的：

首先让最左边的数字和他右边的数字比较：9>8，将9和8互换位置：

让9继续和他右边的数字比较，再互换位

以此类推：9不断的比较——>移动——>再比较：最后；会到达最右边，这样，我们就让最大的数字9放在了最低位置

然后是8，接下来是7，6，5......................直到最后，数列变成0，1，2，3，4，5，6，7，8，9

结束；

我们将一个数字通过不断和他右边的数字”比较，移动。直到这个数字到达他基于升序排序应该到达的位置“这一整个过程称为”一趟“。

将每一个数字的一趟中的每一次移动称为”一次“

那么，冒泡排序函数应该是这样的：

int*arr表示接收arr（数组首元素的地址），sz是数组元素个数，（width（串了，应该删除））

变量 i 表示趟数：一共有sz-1趟：因为有sz个数字，而将前9个数字全部排好后，最后一个数字默认到达了他应该在的位置。

变量 j 表示次数：每一趟有j-1-i次：因为某一个数字（首先假设他是最左边的那个），在考虑最坏的情况下，他可能要移动到数列的最后一个，即他后面有几个数字就移动几次。紧接着第二趟（此时i+1），同样在考虑最坏的情况下，他后面有几个数字就要移动几次但是要去掉目前最后一个数字。以此类推；第一趟额外-0，第二趟额外-1：这与i的变化完全一致：所以使用j-i-1来说明每趟需要的次数。

呈现一下源代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void bouble_qsort( int* arr,size_t sz,int width)//默认升序
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int change = 0;
				change = *(arr + j);
				*(arr + j) = *(arr + 1 + j);
				*(arr + 1 + j) = change;
			}
		}
	}
}
void print(int* arr, size_t sz)
{
	int i;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", *(arr + i));
	}

}
int main()
{
	int arr[10] = { 2,5,8,7,4,1,3,6,9,0};
	int sz = sizeof(arr) / sizeof(arr[0]);
	bouble_qsort(arr,sz,arr[0]);
	print(arr,sz);
	return 0;
}

二，qsort函数

qsort函数的功能是为一切类型进行排序；他的使用需要头文件<string.h>，

他有四个参数：

base：待排序数组的首元素地址。

num：待排序元素个数。

size：待排序元素的大小单位字节。

cmp：比较函数指针。

同时对比较函数的返回值做了规定：

前一个数（p1）大于后一个数（p2）返回小于0的数

反之返回大于0的数，等于则返回0；

学会了这些之后，我们不妨写下如下代码测试一下qsort的强大功能：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int cmp_int(const void* p1,const void* p2)
{
	return  *((int*)p1) - *((int*)p2);
}
test1()
{
	int arr[] = { 1,4,7,2,5,8,6,3,9,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr,sz,sizeof(arr[0]),cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", *(arr + i));
	}
}
int main()
{
	test1();//排序整型
//	test2();//排序结构体————以整数成员
//	test3();//排序结构体————以字符成员
	return 0;
}

实际上，为了测试qsort可以排序任意类型数据的万能性：我们还有以下代码:

struct stu
{
	char name;
	int age;
};
int cmp_stu_by_name(const void*p1,const void*p2)
{
	return strcmp(((struct stu*)p1)->name, ((struct stu*)p2)->name);
}
void test2()
{
	struct stu s1[3] = { {"zhangsan",18},{"lisi",19} ,{"wangwu",22}};
	int sz = sizeof(s1) / sizeof(s1[0]);
	qsort(s1, sz, sizeof(s1[0]), cmp_stu_by_name);
}
int main()
{
	//test1();//排序整型
	test2();//排序结构体————以整数成员
    //test3();//排序结构体————以字符成员
	return 0;
}

好了，既然qsort的功能如此强大。那么我们可不可以模拟一个qsort函数呢？

事实上是可以的：

三，冒泡排序模拟qsort函数

qsort函数，其本质上是使用了快速排序算法；

这里我们可以用冒泡排序算法来完成他：

不难发现：qsort的前三个参数用来用指针的方式排序每个元素。

最后一个函数指针参数，传入比较函数的指针，在qsort函数内用来调用比较函数。（回调函数）

此外，对比冒泡排序的局限性（只能排序整数。）模拟qsort函数必须具备可以排序任意类型给能力：所以交换函数也得改成泛式编程。

直接上源码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void swap(void* buf1, void* buf2, size_t width)
{
	int i = 0;
	
	for (i = 0; i < width; i++)
	{
		char tmp  = *((char* )buf1+i);
		*((char*)buf1 + i) = *((char*)buf2 + i);
		*((char*)buf2 + i) = tmp;
	}
}
void bouble_qsort( void* base,size_t sz,size_t width,int (*cmp)(const void*,const void*))//默认升序
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)base+j*width,(char*)base+(j+1)*width)>0)
			{
				swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}

int cmp_int(const void*p1, const void*p2)
{
	return (*(int*)p1 - *(int*)p2);
}

void print(int* arr, size_t sz)
{
	int i;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", *(arr + i));
	}

}
int main()
{
	int arr[10] = { 2,5,8,7,4,1,3,6,9,0};
	int sz = sizeof(arr) / sizeof(arr[0]);
	bouble_qsort(arr,sz,sizeof(arr[0]),cmp_int);
	print(arr,sz);
	return 0;
}

好的，本期到此结束，感谢你的观看。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-14，如有侵权请联系 cloudcommunity@tencent.com 删除

sort