一.qsort函数简介

  • 功能：执行快速排序

  • 头文件：#include <stdlib.h>或#include <search.h>

  • 时间复杂度：n*log（n）

🍑函数声明：

1
2
3
#include <stdlib.h>
 
extern void qsort(void *base, size_t num, size_t width, int(_cdecl *compare)(const void *elem1, cont void *elem2));

🍑参数解释：

base:待排序的目标数组的起始位置
num:数组的元素的个数
width:数组中每个元素的大小（字节）
compare:比较函数，这个需要我们自己去根据自己的场景进行设计

compare函数的声明：

1
extern int MyCompare(const void *e1, const void *e2);

Mycompare函数的返回值： 小于0:元素1小于元素2 等于0:元素1等于元素2 大于0:元素1大于元素2

qsort函数详细声明

二、qsort()函数应用

🍑对整型数据进行排序：

main()及头文件设计:

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
#include <stdio.h> //printf
#include <windows.h> //system("pause")
#include <stdlib.h> //qsort

int main()
{
int arr[] = {0, -1, 1, 9, 7, 3, 4, 6, 5, 8, 2, 10};
int sz = sizeof(arr) / sizeof(arr[0]); // 求出数组长度
int i = 0;

printf("排序前:>");
for (i=0; i<sz; i++)
{
 printf("%d ", arr[i]);
}

qsort(arr, sz, sizeof(int), CompareInt); // 开始排序

printf("\n排序后:>");
for (i=0; i<sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

system("pause");
return 0;
}

compare函数设计

1
2
3
4
int CompareInt(const void *e1, const void *e2)
{
return (*((int*)e1) - *((int*)e2)); // 相减的结果有>0,<0,==0三种情况
}

运行结果：

🍑对浮点型数据进行排序：

main()以及头文件设计：

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
#include <stdio.h> //printf
#include <windows.h> //system("pause")
#include <stdlib.h> //qsort
#include <math.h> //fabs

int main()
{
double arr[] = {0.0, -1.0, 1.2, 9.4, 7.5, 3.7, 4.4, 6.7, 5.2, 8.5,       2.2, 10.9};
int sz = sizeof(arr) / sizeof(arr[0]); // 求出数组长度
int i = 0;

printf("排序前:>");
for (i=0; i<sz; i++)
{
 printf("%.2lf ", arr[i]);
}

qsort(arr, sz, sizeof(double), CompareDouble); // 开始排序

printf("\n排序后:>");
for (i=0; i<sz; i++)
{
 printf("%.2lf ", arr[i]);
}
printf("\n");

system("pause");
return 0;
}

compare函数设计:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int CompareDouble(const void *e1, const void *e2) // 浮点数直接相减是会有精度损失的，所以采用分支语句
{
if (*((double*)e1) > *((double*)e2))
{
 return 1; //e1>e2
}
else if (*((double*)e1) < *((double*)e2))
{
 return -1; //e1<e2
}
else if (fabs(*((double*)e1) - *((double*)e2)) < __DBL_EPSILON__)
{
 return 0; // e1==e2
}
}

运行结果:

tip:因为浮点数的十进制转换为二进制会有进度损失，所以比较两个浮点数e1，e2是否相等不能直接用“==”来比较，需要使用fabs（e1-e2）< DBL__EPSILON(最小精度)的方式来进行比较

🍑对字符进行排序

main()函数及头文件设计

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
#include <stdio.h> //printf
#include <windows.h> //system("pause")
#include <stdlib.h> //qsort

int main()
{
char arr[] = {'b', 'a', 'c', 'e', 'd'};
int sz = sizeof(arr) / sizeof(arr[0]); // 求出数组长度
int i = 0;

printf("排序前:>");
for (i=0; i<sz; i++)
{
 printf("%c ", arr[i]);
}

qsort(arr, sz, sizeof(char), CompareChar); // 开始排序

printf("\n排序后:>");
for (i=0; i<sz; i++)
{
 printf("%c ", arr[i]);
}
printf("\n");

system("pause");
return 0;
}

compare函数设计

1
2
3
4
int CompareChar(const void *e1, const void *e2)
{
return ((*(char*)e1) - *((char*)e2)); // 相减的结果有>0,<0,==0三种情况
}

运行结果

🍑按字符串首字母进行排序

main()函数及头文件设计

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
#include <stdio.h> //printf
#include <windows.h> //system("pause")
#include <stdlib.h> //qsort

int main()
{
char arr[3][4] = {{"abc"}, {"cab"}, {"bac"}}; // 把arr看成一个有3个元素的一维数组，其中arr有3个元素，每个元素是一个4个元素的一维数组
int sz = sizeof(arr) / sizeof(arr[0]); // 求出数组长度
int i = 0;

printf("排序前:>");
for (i=0; i<sz; i++)
{
 printf("%s ", arr[i]);
}

qsort(arr, sz, sizeof(char[4]), CompareStr); // 开始排序,char arr[3][4]含义:arr数组有3个元素，每个元素大小以及类型是char[4]

printf("\n排序后:>");
for (i=0; i<sz; i++)
{
 printf("%s ", arr[i]);
}
printf("\n");

system("pause");
return 0;
}

compare函数设计

1
2
3
4
int CompareStr(const void *e1, const void *e2)
{
return ((*(char*)e1) - *((char*)e2)); // 相减的结果有>0,<0,==0三种情况
}

运行结果

🍑按字符串长度进行排序

main（）函数及头文件设计

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
#include <stdio.h> // printf
#include <windows.h> // system("pause")
#include <stdlib.h> // qsort
#include <string.h> // strlen

int main()
{
char arr[3][8] = {{"bacaaaa"}, {"cabaa"}, {"abca"}}; // 把arr看成一个有3个元素的一维数组
int sz = sizeof(arr) / sizeof(arr[0]); // 求出数组长度
int i = 0;

printf("排序前:>");
for (i=0; i<sz; i++)
{
 printf("%s ", arr[i]);
}

qsort(arr, sz, sizeof(char[8]), CompareStrlen); // 开始排序

printf("\n排序后:>");
for (i=0; i<sz; i++)
{
 printf("%s ", arr[i]);
}
printf("\n");

system("pause");
return 0;
}

compare函数设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int CompareStrlen(const void *e1, const void *e2) 

/* strlen的返回值是size_t 即unsigned int 无符号整形，所以最好不要对无符号整形直接相减*/

{
if (strlen(e1) > strlen(e2))
{
 return 1;
}
else if (strlen(e1) < strlen(e2))
{
 return -1;
}
else if (strlen(e1) == strlen(e2))
{
 return 0;
}
}

运行结果：

🍑结构体排序应用

stu.h

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
#ifndef __STU_H__
#define __STU_H__

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

#define MAX_ID 20
#define MAX_NAME 10


typedef struct student
{
char id[MAX_ID];
char name[MAX_NAME];
int ChineseScore;
int MathScore;
int EnglishScore;
int sum;
}student;

enum Option
{
EXIT,
ByName,
ById,
ByScore
};

extern void StuInit(student **stu, int n);
extern void StuDestory(student *stu);
extern void StuScanf(student **stu, int n);
extern void QsortByName(student **stu, int n);
extern void Print(student **stu, int n);
extern void QsortById(student **stu, int n);
extern void QsortByScore(student **stu, int n);

#endif

stu.c

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
101
102
103
104
#include "stu.h"

void StuInit(student **stu, int n)
{
if (NULL == stu)
{
 perror("StuInit()\n");
 exit(-1);
}

student *tmp = (student*)malloc(sizeof(student)*n);
if (NULL == tmp)
{
 perror("malloc()\n");
 exit(-1);
}
*stu = tmp;
tmp = NULL;
memset(*stu, 0, sizeof(student)*n);
}

void StuDestory(student *stu)
{
free(stu);
stu = NULL;
}

void StuScanf(student **stu, int n)
{
int i = 0;
for (i=0; i<n; i++)
{
int sum = 0;

printf("请输入姓名:>");
scanf("%s", (*stu)[i].name); // 二级指针变量先解引用为一级指针变量再进行操作!
printf("请输入学号:>");
scanf("%s", (*stu)[i].id);
printf("请输入语文成绩:>");
scanf("%d", &((*stu)[i].ChineseScore));
printf("请输入数学成绩:>");
scanf("%d", &((*stu)[i].MathScore));
printf("请输入英语成绩:>");
scanf("%d", &((*stu)[i].EnglishScore));

sum = ((*stu)[i].ChineseScore + (*stu)[i].MathScore + (*stu)[i].EnglishScore);
(*stu)[i].sum = sum;
printf("保存成功!\n");
}
}

static int SortByName(const void *e1, const void *e2)
{
return (*(((student*)e1)->name) - *(((student*)e2)->name));
}

void QsortByName(student **stu, int n)
{
if (NULL == stu)
{
perror("QsortByName()\n");
exit(-1);
}

qsort((*stu), n, sizeof(student), SortByName);
}

void Print(student **stu, int n)
{
int i = 0;

printf("排序完成!\n");
for (i=0; i<n; i++)
{
printf("姓名\t学号\t语文\t数学\t英语\t总分\t\n");
printf("%s\t%s\t%d\t%d\t%d\t%d\t\n", (*stu)[i].name,\
(*stu)[i].id,\
(*stu)[i].ChineseScore,\
(*stu)[i].MathScore,\
(*stu)[i].EnglishScore,\
(*stu)[i].sum);
}
}

static int SortById(const void *e1, const void *e2)
{
return (*(((student*)e1)->id) - *(((student*)e2)->id));
}

void QsortById(student **stu, int n)
{
qsort((*stu), n, sizeof(student), SortById);
}

static int SortByScore(const void *e1, const void *e2)
{
//return ((*((student*)e1)).sum - (*((student*)e2)).sum);
return ((((student*)e1)->sum) - (((student*)e2)->sum));
}

void QsortByScore(student **stu, int n)
{
qsort((*stu), n, sizeof(student), SortByScore);
}

test.c

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
// qsort((*stu))传入给compare的是*stu
// 运算符优先级第一梯队：() [] ->
// 运算符优先级第二梯队: *

#include "stu.h"

static void Menu(void)
{
printf("请选择要排序的方式:>\n");
printf("********1.按姓名排序********\n");
printf("********2.按学号排序********\n");
printf("******* 3.按总成绩排序 *****\n");
printf("********   0.退出   *******\n");
}

int main()
{
int input = 0;
int n = 0;

printf("请输入要输入的学生的个数:>");
scanf("%d", &n);
student *stu;
StuInit(&stu, n);
StuScanf(&stu, n);
do
{

Menu();
scanf("%d", &input);
switch(input)
{
 case EXIT:
   StuDestory(stu);
   printf("退出成功!\n");
   break;
 case ByName:
   QsortByName(&stu, n);
   Print(&stu, n);
   break;
 case ById:
   QsortById(&stu, n);
   Print(&stu, n);
   break;
 case ByScore:
   QsortByScore(&stu, n);
   Print(&stu, n);

   break;
 default:
   printf("输入有误,请重新输入!\n");
   break;
}

}while(input);

system("pause");
return 0;
}

三.qsort()函数模拟实现，但，是冒泡排序算法（BubbleSort算法实现通用排序函数）

函数设计

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

#define MAX_NAME 10

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

void Swap(void *buf1, void *buf2, int isize)
{
  int i = 0;
  for (i=0; i<isize; i++) // 逐字节交换
  {
    char tmp = 0;
    tmp = *(char*)buf1;
    *(char*)buf1 = *(char*)buf2;
    *(char*)buf2 = tmp;
    buf1++;
    buf2++;
  }
}

void BubbleSort(void *array, size_t len, size_t isize, int (*compar)(const void *e1, const void *e2))
{
  int i = 0;
  int j = 0;

  for (i=0; i<len-1; i++) // len个元素要比较len-1轮
  {
    for (j=0; j<len-1-i; j++) // 每轮比较完成后需要比较的元素个数-1
    {
      if ( compar( ((char*)array) + j*isize, ((char*)array) + (j+1)*isize ) > 0 ) 
      { // 如果首元素大于后一个元素就进入Swap函数进行交换
        Swap( ((char*)array) + j*isize, ((char*)array) + (j+1)*isize, isize );
      }
    }
  }
}

void TestInt(void)
{
  int i = 0;
  int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
  int sz = 0;
  sz = sizeof(arr) / sizeof(arr[0]);

  printf("排序前:>");
  for (i=0; i<sz; i++)
  {
    printf("%d ", arr[i]);
  }

  BubbleSort(arr, sz, sizeof(arr[0]), ComparInt);

  printf("\n排序后:>");
  for (i=0; i<sz; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}


typedef struct student
{
  char name[MAX_NAME];
  int id;
}student;

int ComparById(const void *e1, const void *e2)
{
  return ( ((student*)e1)->id, ((student*)e2)->id );
}

int ComparByName(const void *e1, const void *e2)
{
  return strcmp( ((student*)e1)->name, ((student*)e2)->name );
}

void TestStruct1(void)
{
  int i = 0;
  student stu[] = {{"bb", 01}, {"aa", 02}};
  int len = sizeof(stu) / sizeof(stu[0]);

  printf("按姓名排序前:>\n");
  printf("姓名\t学号\t\n");
  for (i=0; i<len; i++)
  {
    printf("%s\t%d\t\n", stu[i].name, stu[i].id);
  }
  
  BubbleSort(stu, len, sizeof(student), ComparByName);
  
  printf("按姓名排序后:>\n");
  printf("姓名\t学号\t\n");
  for (i=0; i<len; i++)
  {
    printf("%s\t%d\t\n", stu[i].name, stu[i].id);
  }
  printf("\n");
  
}

void TestStruct2(void)
{
  int i = 0;
  student stu[] = {{"bb", 01}, {"aa", 02}};
  int len = sizeof(stu) / sizeof(stu[0]);

  printf("按学号排序前:>\n");
  printf("姓名\t学号\t\n");
  for (i=0; i<len; i++)
  {
    printf("%s\t%d\t\n", stu[i].name, stu[i].id);
  }
  
  BubbleSort(stu, len, sizeof(student), ComparById);
  
  printf("按学号排序后:>\n");
  printf("姓名\t学号\t\n");
  for (i=0; i<len; i++)
  {
    printf("%s\t%d\t\n", stu[i].name, stu[i].id);
  }
  printf("\n");
}

int main()
{
  TestInt();
  TestStruct1();
  TestStruct2();
  system("pause");
  return 0;
}

四.参考来源 📕

C语言qsort（快速排序）（用冒泡排序的排序方式自主实现一个通用的快速排序的函数）_你需要实现 个类似 qsort() 函数的快速排序函数 qsort_with_skip() , 持对_KOBE 0824 BRYANT的博客-CSDN博客

C语言qsort()函数针对：整型、单个字符、字符串、结构体，超详细讲解（多维度分析举例，小白一看就懂！！！！！）_sunny-ll的博客-CSDN博客_qsort 字符串