# 0. 经典快速排序算法-Quick_sort

#include<stdio.h>
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void Quick_sort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = begin;
int left = begin, right = end;
while (left < right)
{
while (left < right && arr[right] >= arr[keyi])
{
right--;
}
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
int meeti = left;
Swap(&arr[keyi], &arr[meeti]);
Quick_sort(arr, begin, meeti-1);
Quick_sort(arr, meeti+1, end);
}
void Print(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d\t", arr[i]);
}
}
int main()
{
int arr[5] = { 12,43,5,23,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
Quick_sort(arr, 0,sz-1);
Print(arr, sz);
return 0;
}

#include<stdio.h>
#include<string.h>
typedef struct stu
{
char name[20];
int age;
}stu;
void Swap(stu* a,stu* b)
{
stu temp = *a;
*a = *b;
*b = temp;
}
void Quick_sort(stu* ps, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = begin;
int left = begin, right = end;
while (left < right)
{
while (left < right && strcmp(ps[right].name, ps[keyi].name) >= 0)
{
right--;
}
while (left < right && strcmp(ps[left].name, ps[keyi].name) <= 0)
{
left++;
}
Swap(&ps[left], &ps[right]);
}
int meeti = left;
Swap(&ps[keyi], &ps[meeti]);
Quick_sort(ps, begin, meeti - 1);
Quick_sort(ps, meeti+1, end);
}
void Print(stu* ps, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%s\n", ps[i].name);
}
}
int main()
{
stu s[3] = { {"张三",18},{"李四",20},{"王五",19} };
int sz = sizeof(s) / sizeof(s[0]);
Quick_sort(s,0,sz-1);
Print(s, sz);
return 0;
}

# 1. qsort排序函数的基本介绍

qsort排序函数是C语言标准库里的函数,实现原理是快速排序算法,函数原型如下:

qsort函数的相关参数的介绍和意义:

void  base: 待排序数据元素的起始地址

size_t num:  待排序数据元素的个数

size_t width:待排序数据元素所占的大小,单位是字节

int( * cmp)(const void*,const void*): 函数指针-比较数据元素大小的函数,排序依据

#include<stdio.h>
#include<stdlib.h>
//以qsort库函数实现整型数组排序为例
int main()
{
int arr[5] = { 12,43,5,23,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp);
//arr:数组名,也是数组首元素的地址,数值上等于首元素中4个字节中地址最低的那个字节的地址
//sz:数组arr的元素个数
//sizeof(arr[0]):每一个数组元素所占的字节数
//cmp_int:回调函数-比较数组元素的函数,根据调用者的需要自行实现
Print(arr, sz);
return 0;
}

2. 比较函数

#include<stdio.h>
#include<stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
//比较两个整型元素
//void*是无具体类型的指针
//void*的指针可以接收任意类型的地址,类似垃圾桶
//void*的指针没有具体类型,不能+1-1(因为不知道加多少)
//升序:
return *(int*)e1 - *(int*)e2;
//降序:
//return *(int*)e2 - *(int*)e1;
}
void Print(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d\t", arr[i]);
}
}
void test1()
{
int arr[6] = { 14,35,4,42,6,12 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(&arr[0], sz, sizeof(arr[0]), cmp_int);
Print(arr, sz);
}
int main()
{
test1();
return 0;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct stu
{
char name[20];
int age;
}stu;
int cmp_struct_by_name(const void* e1, const void* e2)
{
return strcmp(((stu*)e1)->name, ((stu*)e2)->name);//妙哉之处
}
void Print(stu* ps, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%s\n", ps[i].name);
}
}
void test2()
{
stu s[3] = { {"zhangsan",18},{"lisi",20},{"wangwu",19} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s,sz,sizeof(s[0]),cmp_struct_by_name);
Print(s, sz);
}
int main()
{
test2();
return 0;
}

# 2. qsort函数的具体实现

void Swap(char* buff1,char* buff2,int width)
{
if (buff1 != buff2)
{
//way1
//while (width--)
//{
//  char temp = *buff1;
//  *buff1 = *buff2;
//  *buff2 = temp;
//  buff1++;
//  buff2++;
//way2
for (int i = 0; i < width; i++)
{
char temp = *(buff1+i);
*(buff1+i) = *(buff2+i);
*(buff2+i) = temp;
}
}
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void*, const void*))
{
int flag = 1;
//趟数
for (int i = 0; i < sz-1; i++)
{
for (int 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);
flag = 0;
}
}
if (flag == 1) break;
}
}

Print(arr,5),这里的arr其实就是首元素的地址，在数值上和首元素4个字节中最低字节的地址是相同的，所以cmp函数的参数即使是char* 一个字节的地址，在cmp函数内同样可以强转为所需要的类型，进行解引用，拿到相应的字节数进行比较，这样就能做到在bubble_sort函数内得到统一，所以无论我们要对任何类型的数据进行排序，都可以直接调用bubble_sort函数，只需要更改cmp函数即可，这就增加了bubble_sort函数代码的复用性。

|
1天前
|
C语言 C++
C语言----C语言内存函数
C语言----C语言内存函数
3 0
|
1天前
|
C语言
C语言----字符函数和字符串函数（4）
C语言----字符函数和字符串函数
5 0
|
1天前
|

C语言----字符函数和字符串函数（3）
C语言----字符函数和字符串函数
10 0
|
1天前
|
C语言
C语言----字符函数和字符串函数（2）
C语言----字符函数和字符串函数
6 0
|
1天前
|
C语言
C语言----字符函数和字符串函数（1）
C语言----字符函数和字符串函数
6 0
|
1天前
|
C语言
C语言----指针模拟二维数组
C语言----指针模拟二维数组
6 0
|
1天前
|
C语言
C语言---函数递归
C语言---函数递归
4 0
|
1天前
|
C语言
C语言---递归---输入一个整函数，按照顺序打印每一位
C语言---递归---输入一个整函数，按照顺序打印每一位
4 0
|
1天前
|
C语言
C语言---函数---请输入乘法口诀表的行，来打印几几乘法表
C语言---函数---请输入乘法口诀表的行，来打印几几乘法表
7 1
|
1天前
|
C语言
C语言--函数递归与迭代
C语言--函数递归与迭代
5 1