排序综合讲解–第一弹(bubble_sort & q_sort)

完整函数的实现:组合同级标题完成代码的综合.

1. 冒泡排序 bubble_sort

1.1 思路解析

1.2 整型比较

只能排序整型的数据

冒泡排序:两两相邻元素的比较

对整型数据进行排序 – 升序 – 并进行交换

1.2.1 函数的遍历与交换

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;
			}
		}
	}
}

1.2.2 打印函数的实现

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

1.2.3 主函数

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);
	return 0;
}

2. 快速排序 q_sort

底层是快速排序的方法

2.1 q_sort函数的介绍

void qsort(void* base,//指向起始地址（pointer to the first object of the array to be sorted）
          size_t num;//元素个数
          size_t size;//每个元素大小（单位：字节）
          int(*compar)(const void*,const void*)//比较两个元素的函数指针
          );

2.1.1 void* 介绍

void*的指针是非常宽容的，可以接收任意类型的地址

char ch='w';
int i=20;

void* p=&ch;
void* p=&i;

*p=200;//写法错误：无具体类型的指针，解引用后值类型未知
*(int*)p=200;//正确写法，先用指定类型解引用，再进行修改

p++;//写法错误

2.1.2 不同类型如何比较大小?

2.2 整型比较

2.2.1 主函数

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);
	return 0;
}

2.2.2 头文件引用

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

2.2.3 整型比较的实现

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;
}

2.2.4 整型比较实现的改进

对cmp_int(…)函数的改进,比较函数里面内容

int cmp_int(const void* e1, const void* e2)
{
    //升序:
    return (*(int*)e1-*(int*)e2);

    //降序:
    return (*(int*)e2-*(int*)e1);
}

2.2.5 打印函数的实现

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

2.4 结构体类型

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

2.4.1 头文件的引用

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

2.4.2 主函数

int main()
{
	struct Stu s[] = { {"zhangqiran",23},{"lijun",20},{"xiugou",25} };
	//按照名字比较
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	return 0;
}

A. 按姓名排序

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

A.1 调试

关注首字母升序

B. 按照年龄排序

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

B.1 调试

关注年龄升序

3. 用bubble_sort函数实现q_sort

借鉴bubble_sort,来实现对任意类型数据的排序

3.1 思路解析

3.2 逐一交换

void Swap(char* buf1,char* buf2,int width)
    //width:整型4字节;结构体类型:32字节
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

3.3 关键实现代码

照猫画虎:依照q_sort写bubble_sort

void bubble_sort(void* base, int sz, int width, int (*cmp)(const void* e1, const void* e2))
{
	//base:起始位置，width：字节
	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)
				//if(arr[j]>arr[j+1]
			{
				//交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}	
		}
	}
}

3.4 可替换的比较项

可替换成上述:结构体(AB)\整型(2.2.4)

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

3.5 打印函数

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

3.6 主函数

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