深入理解指针04

1、qsort使⽤举例

今天我们来学习qsort函数，它的主要功能就是能给任意数据排序，类似冒泡排序，

那我们再来复习一下什么是冒泡排序：

#include<stdio.h>

void bubble(int arr[], int sz)//以升序为例
{
	for (int i = 0; i < sz - 1; i++)//需要排序的趟数
	{
		for (int j = 0; j < sz - 1 - i; j++)//每趟需要比较的次数
		{
			if (arr[j] > arr[j + 1])//判断是否为升序，不是则交换
			{
				int tem = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tem;
			}
		}
	}
}

//打印数组
void print(int arr[], int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}

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

现在我们来彻底地了解qsort函数

接下来我们来使用qsort函数排序

1.1使⽤qsort函数排序整型数据 

#include <stdio.h>
//qosrt函数的使⽤者得实现⼀个⽐较函数

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

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

1.2 使⽤qsort排序结构数据 

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

struct stu
{
	char name[20];
	int num;
};

int cmp_name(const void* p1,const void* p2)
{
	return strcmp(((struct stu*)p1)->name,((struct stu*)p2)->name);
}

int cmp_num(const void* p1, const void* p2)
{
	return ((struct stu*)p1)->num - ((struct stu*)p2)->num;
}

void test1()
{
	struct stu arr[2] = { {"zhangsan",18},{"lisi",23} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(struct stu), cmp_name);

}

void test2()
{
	struct stu arr[2] = { {"zhangsan",37},{"lisi",23} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(struct stu), cmp_num);
}

int main()
{
	//test1();按name排列
	test2();//按num排列
	return 0;
}

2、qsort函数的模拟实现

2.1分析

qsort函数类似冒泡排列，冒泡排列只能排整型，qsort能排各种类型。那我们就把模拟的my_qsort函数主体结构设计成冒泡排列的形式，它的参数全部模仿qsort函数，为了能实现各种类型都能排序，我们将各元素看成n个char类型合在一起，所以在元素比较时将其强制类型转化成char*,然后加上j*width(width可看成宽度，j是个数)。同理在交换时也将其拆分成n个char类型的合在一起，一个char一个char的传，故需要同时传width(宽度--一个元素占多少字节（char类型)。

2.2代码实现

#include<stdio.h>

void swap(char* s1, char* s2, size_t width)
{
	for (int i = 0; i < width; i++)
	{
		char* tem = *s1;
		*s1 = *s2;
		*s2 = tem;
		s1++;
		s2++;
	}
}

int cmp(const void* p1, const void* p2)
{
	return *(int*)p1-*(int*)p2;
}
//                         元素个数         元素大小
void my_qsort(void* str,size_t num,size_t width,int (*cmp)(void*p1,void*p2))
{
	int i = 0;
	//趟数
	for (i = 0; i < num - 1; i++)
	{
		//每行需要比较的次数
		for (int j = 0; j < num - 1 - i; j++)
		{
			if (cmp((char*)str + width * j , (char*)str + width * (j + 1))>0)      
			{
				//交换
				swap((char*)str + width * j, (char*)str + width * (j + 1),width);
			}
		}
	}

}

//输出
void print(int arr[], int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[] = { 9,8,4,5,67,21,54,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_qsort(arr, sz, sizeof(int), cmp);//升序
	print(arr, sz);
	return 0;
}