qsort（冒泡排序）

一、void指针

void是非常宽容的，可以接受任意类型的地址； 想解引用void指针必须要强制转换；
void指针也是不能够进行p++移动，因为不知道移动多大的内存

int main()
{
	char ch = 'w';
	int i = 20;
	//void*的指针是非常宽容的，可以接收任意类型的地址
	void* p = &ch;
	void* p = &i;
	//*p=200;  err这个是不能修改的，
	*(int*)p = 200;
	p++;//err
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

二、qsort函数

void qsort(void* base, int num, int size, int(*cmp)(const void* e1, const void*e2))
1

void qsort (void* base, //待排序数据的起始地址
size_t num, //待排序数据的元素个数
size_t size, //待排序数据元素的大小（单位是字节）
int (cmp)(const void, const void*)，比较2个元素大小的函数指针 );

三、基础冒泡排序

//bubble_sort 函数只能排序整型数据
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 - 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[] = { 2, 1, 3, 7, 5, 9, 6, 8, 0, 4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	//打印
	print(arr, sz);
}
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

四、qsort原理

(*(int*)e1 - *(int*)e2)是升序；(*(int*)e2 - *(int*)e1)是降序。
1

/*
int cmp_int(const void* e1, const void* e2)
{
	if (*(int*)e1 > *(int*)e2)
	return 1;
	else if (*(int*)e1 < *(int*)e2)
		return -1;
	else
    	return 0;
}
*/
//对上述代码的简化
int cmp_int(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}

//测试qsort函数排序整型数据
int main()
{
	int arr[] = { 2, 1, 3, 7, 5, 9, 6, 8, 0, 4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	
	print(arr, sz);
}
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

如果是结构体呢？？同样强制类型转化

struct Stu
{
	char name[20];
	int age;
};

int cmp_stu_by_name(const void* e1, const void* e2)
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

int cmp_stu_by_age(const void* e1, const void* e2)
{
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

//测试qsort排序结构体数据
int main()
{
	struct Stu s[] = { { "zhangsan", 20 }, { "lisi", 55 }, { "wangwu", 40 } };
	//按照名字比较
	int sz = sizeof(s) / sizeof(s[0]);
	//qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}

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

五、qsort实现冒泡

char tmp为什么定义char类型？比较大小后换位置，因为不知道具体类型，我们把他们存在内存的数据进行交换，内存是以字节为单位的!
在这里的想&arr[j]与&arr[j+1]的比较这是不正确的，因为传地址所用的是void*类型

int cmp_int(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}

void Swap(char*buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort2(void* base, int sz, int width, int(*cmp)(const void* e1, const void*e2))
{
	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 main()
{
	int arr[] = { 2, 1, 3, 7, 5, 9, 6, 8, 0, 4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort2(arr, sz, sizeof(arr[0]), cmp_int);
	print(arr, sz);
}
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

图形分析上述的内在逻辑：

换成结构体？？ 也能够完全实现