C语言实现冒泡排序_冒泡排序c语言

1.冒泡排序

冒泡排序（升序）：遍历数组，从第一个元素开始，相邻两两元素进行比较，如果第一个位置的元素的数值大于第二个位置的元素的数值，则进行交换位置；接着，第二个位置的元素与第三个位置的元素，依次循环往复。

• 第一次遍历：需要进行n-1(数组元素个数为n)次比较，遍历完成之后，最大的数就被挪到最后一个位置
• 第二次遍历：需要进行n-1-1(数组元素个数为n)次比较，这是因为第一次遍历已经确定一位数。遍历完成之后，最大的数就被挪到倒数第二个位置
• …
• n个元素，需要进行n-1次遍历数组，第一次遍历数组需要比较n-1次，之后每次遍历数组，比较次数依次递减

遍历n-1次数组：每遍历数组一次，便会固定一个元素，当遍历n-1次后，便固定n-1个元素，剩余一个元素就在本身该有的位置
比较次数依次递减：n个元素两两进行比较，只需要进行n-1次比较；而每遍历数组一次，便会固定一个元素，因此比较次数依次递减

2.自定义函数实现冒泡排序

#include <stdio.h>

/*
功能：冒泡排序 (升序) 
时间：2024.1.29
参数：arr:整型数组首地址
	  length:整型数组元素个数 
作者：Excellent.bai 
*/

void bubble_sort(int arr[],int length)
{
	int i = 0,j = 0，flag = 1;
	for(i = 0;i < length - 1;i++)
	{
		for(j = 0;j <(length - 1 -i);j++)
		{
			if(arr[j] > arr[j+1])
			{
				//交换 
				int temp = 0;
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				flag = 0;
			}
		}
		if(flag) //如果本身就是升序序列，则直接退出循环 
		{
			break;
		}
	}
}

int main()
{
	int arr[] = {9,8,7,6,5,4,3,2,1};
	int i = 0;
	
	//计算元素个数
	int length = sizeof(arr) / sizeof(arr[0]);
	 
	bubble_sort(arr,length);
	
	//输出数据 
	for(i = 0;i < length;i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

3.利用qsort()实现冒泡排序

qsort( )快速排序函数，可实现不同类型数据的排序
数组按照比较函数定义的递增顺序排序。要按降序对数组进行排序，请颠倒比较函数中“大于”和“小于”的含义。

• void* base：进行排序数据的起始位置
• size_t num：需要排序的数据个数
• size_t width:每个待排序数据所占的字节数
• int (__cdecl *compare )(const void *elem1, const void *elem2 )：函数指针，是一个比较函数，不同类型数据的比较方法
  elem1：第一个比较元素的地址
  elem2：第一个比较元素的地址
  这两个指针类型为void*，void*是无具体类型的指针，可接收任意数据类型的地址，但不能解引用和+、-整数操作，若需要解引用时，需要强制类型转换

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 

struct stu
{
 	char name[10];
 	int age;
};
 
 //整型数据的比较函数 ，qsort()默认升序排序 
 int cmp_int(const void*e1,const void*e2)
 {
 	return (*(int*) e1 - *(int*) e2);
 }
 
//字符型数据的比较函数 ，qsort()默认升序排序 
 int cmp_name(const void*e1,const void*e2)
 {
 	//e1和e2里面传入的都是结构体指针 ，所以要强制转换结构体类型，之后进行引用 
 	return  strcmp((*(struct stu*) e1).name,(*(struct stu*) e2).name);
 	
 	//strcmp()函数与qsort()第四个参数函数指针所指向函数的的返回值一模一样 
 }
 
 
int main()
{
	int arr[] = {9,8,7,6,5,4,3,2,1};
	struct stu s[3] = {{"libai",18},{"hanxin",19},{"luna",20}};
	int i = 0;
	
	//计算整型数组的元素个数
	int length = sizeof(arr) / sizeof(arr[0]);
	
	//计算整结构体组的元素个数
	int sz = sizeof(s) / sizeof(s[0]);	
	
	//qsort()各参数的含义 
	//void* base：进行排序数据的起始位置
	//size_t num：需要排序的数据个数
	//size_t width:每个待排序数据所占的字节数
	//int (__cdecl *compare )(const void *elem1, const void *elem2 )：函数指针，不同类型数据的比较方法,需要自定义 
	//整型数组升序排序 
	//qsort(arr,length,sizeof(arr[0]),cmp_int); 
	
	//结构体数组比较字符串排序 
	qsort(s,sz,sizeof(s[0]),cmp_name); 
	
	//输出数据 
	for(i = 0;i < sz;i++)
	{
		printf("%s %d\n",s[i].name,s[i].age);
	}
	return 0;
 }  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

说明：

1. 在自定义函数中，由于传入的是结构体指针，所以要将void*类型强制转换结构体指针类型
2. strcmp()函数与qsort()第四个参数函数指针所指向函数的的返回值一模一样

4.模仿qsort()函数的实现

#include <stdio.h>

/*
功能：模拟实现库函数qsort() (升序) 
时间：2024.1.29
参数：
	  //base：进行排序数据的起始位置
      //sz：需要排序的数据个数
	  //length:每个待排序数据所占的字节数
	  //int (*cmp)(const void *e1, const void *e2 )：函数指针，不同类型数据的比较方法,需要自定义  
作者：Excellent.bai 
*/

void bubble_sort(void* base,int sz,int length,int (*cmp)(const void*e1,const void*e2))
{
	int i = 0,j = 0,flag = 1;
	for(i = 0;i < sz - 1;i++)
	{
		for(j = 0;j <(sz - 1 -i);j++)
		{
			//这里运用了函数指针，进行比较 
			
			//可以采用起始地址+偏移地址（相差元素个数*每个元素所占的字节空间），表示两位比较元素的地址 
			//前提，把首元素地址强制转换成（char*） 
			
			//>0: 第一个数据 >  第二个数据
			if(cmp((char*)base + j*length,(char*)base + (j+1)*length) > 0)
			{
				swap((char*)base + j*length,(char*)base + (j+1)*length,length); 
				flag = 0;
			}
			
			
			/*
			if(arr[j] > arr[j+1])  ==  if(*(arr+j) > *(arr+j+1))   //这里的arr+j,表示在arr的起始地址+j*(一个元素所占的字节个数) 
			{
				//交换 
				int temp = 0;
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				flag = 0;
			}
			*/
		}
		if(flag) //如果本身就是升序序列，则直接退出循环 
		{
			break;
		}
	}
}

/*
功能：交换数据（以字节为单位交换） 
时间：2024.1.29
参数：buf1:数据1的首地址 
	  buf2:数据2的首地址
	  length:每个交换数据所占的字节数 	  
作者：Excellent.bai 
*/
void swap(char* buf1,char* buf2,int length)
{
	//可以交换不同数据
	//由于事先不知道数据类型，故进行字节交换 
	//只要知道两数据的起始地址，以及一个数据所占字节数 
	int i = 0;
	for(i = 0;i < length;i++)
	{
		char buf;
		buf = *buf1;
		*buf1 = *buf2;
		*buf2 = buf;
		buf1++;
		buf2++;		
	}
	
}

 //整型数据的比较函数 ，qsort()默认升序排序 
 int cmp_int(const void*e1,const void*e2)
 {
 	return (*(int*) e1 - *(int*) e2);
 }

int main()
{
	
	int arr[] = {9,8,7,6,5,4,3,2,1};
	int i = 0;
	
	//计算整型数组元素个数
	int sz = sizeof(arr) / sizeof(arr[0]);
	
	bubble_sort(arr,sz,sizeof(arr[0]),cmp_int); 
	for(i = 0;i < sz;i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

说明：

1. 实现任意类型相邻数据间两两比较：由于形参void* base为void*类型，首先要强制类型。转换成short*、int*都不合适，所以先转化为char*,base作为起始地址
   那如何表示第二个元素的地址呢？
   采用：起始地址+偏移地址（j X 一个元素所占的字节个数）
2. 实现任意类型相邻数据的交换：
   由于事先不知道数据类型，故进行字节交换
   只要知道一个数据所占字节个数和两元素的地址，就可以实现字节交换
   实现方法：利用循环，循环次数为一个数据所占字节个数，利用中间变量进行交换，即可实现