目录

• 📝 什么是快速排序？
• • 🌟 回顾冒泡排序
• 📝解析C语言qsort快速排序函数

📝 什么是快速排序？

快速排序（Quick Sort）是一个十分经典的排序算法，但不同于希尔排序、选择排序的思想，快速排

序的思想其实来源于冒泡排序，他们都属于交换类的排序思想，不断通过比较和移动来实现排序。

🌟 回顾冒泡排序

那么，作为引入，我们先回顾一下冒泡排序的思想：基本思想就是交换，两两比较相邻的元素，如果反序则进行交换，知道整个数组 / 序列没有反序为止。

假设我们有一个数组，现在要进行升序排序：
（下面是冒泡排序的初级版本）

#include <stdio.h>
void BubbleSort0(int arr[], int sz) {for (int i = 0; i < sz; i++) {for (int j = 0; j < sz - i - 1; j++) {if (arr[j] > arr[j + 1]) {int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}
}
int main() {int arr[10] = { 5,3,6,9,1,7,2,10,8,4 };//我们相对arr数组的元素进行排序(升序)int sz = sizeof(arr) / sizeof(arr[0]);BubbleSort0(arr, sz);for (int i = 0; i < sz; i++) {printf("%d ", arr[i]);}return 0;
}

我们可以分析，双重for循环结束条件如何控制，在这儿有排序趟数，和每一趟的比较次数，考虑 3 2 1，这是一个数组，那我们想排为1 2 3，显然先交换3和2变为2 3 1，再3和1交换，变为2 1 3，一次（一趟）排序我们找到一个最大的元素放在数组末尾，到第二次的话第一次最大的元素就不需要进行比较，则第二趟比较2和1，并交换即可。那么显然排序三个数字需要两趟可以排好，且考虑N个数字是要进行进行N – 1次比较，而N个数字共需要N – 1趟来进行排序。

但是不难发现，当数组完全逆序时，是最贴合上述次次比较且交换的情况的，这也是冒泡排序时间复

杂度最坏的情况，但是把那个不是所有的序列是完全逆序的，考虑这样一种情况：

当序列已经是完全有序的情况呢？如：1 2 3 4 5；或者在第一趟排完后序列就有完全序了，如：5 1 2 3 4，一趟后变为：1 2 3 4 5，这意味着后续的训话在做无用功，我们必然要考虑改进：

//改进后的冒泡排序
void BubbleSort1(int arr[], int sz) {int flag = 1;for (int i = 0; i < sz && flag; i++) {for (int j = 0; j < sz - i - 1; j++) {flag = 0;if (arr[j] > arr[j + 1]) {int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 1;  //有数据交换，则代表不有序}}}
}

通过flag标记就可以控制当这一趟比较未发生交换时，那么整个数组就是有序的，&& flag 就不满足，跳出循环，排序完成。

考虑冒泡排序的时间复杂度，关于最差性能，即所有趟分别比较（n-1）、（n – 2）、········3、2、1次，等差数列求和为 n（n-1）/ 2 次，那么时间复杂度显然是O(n^2)。当然，最好情况就是完全有序，只进行比较n – 1次，那时间复杂度为O(n)。

📝解析C语言qsort快速排序函数

qsort函数是C语言标准库提供的排序函数，对数据进行排序，且qsort可以实现排序任意类型的数据。

在官方的函数细节文档qsort我们可以看到qsort函数的描述。

void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*));

• 【base】指向待排序数据的起始位置

• 【num】base数据里的元素个数

• 【size】数据里每一个元素的大小（字节）

• 【compar】 int (*compar)(const void*,const void*)这很显然是一个函数指针，这是一个比较函数。compar指针指向比较两个元素的函数。

    当p1指向的元素大于p2，那么返回大于0的数字；当p1指向的元素小于p2，那么返回小于0的数字；如果相等，返回0；
  

base设计为void* 类型代表我并不想知道待排序数据的类型，void* 指针很宽容，可以接收不同类型的

指针，其实给了我们很多自由度，也便于实现排序任意类型的数据。

那么我们还是使用上面的例子：{ 5,3,6,9,1,7,2,10,8,4 }，来使用qsort函数排序整形数组。

void print(int arr[], int sz) {for (int i = 0; i < sz; i++) {printf("%d ", arr[i]);}
}
int Cmpint(const void* e1,const void* e2) {return *(int*)e1 - *(int*)e2;
}
void Test_qsort() {int arr[10] = { 5,3,6,9,1,7,2,10,8,4 };//我们相对arr数组的元素进行排序(升序)int sz = sizeof(arr) / sizeof(arr[0]);// 在本例中我们实现比较两个整形qsort(arr, sz, sizeof(arr[0]), Cmpint);print(arr, sz);
}
int main() {Test_qsort();return 0;
}

上面实现了升序，那么根据compar的特点，我们交换e1和e2，就可以实现降序排序：

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

那么其实如果要排序结构体类型，原理也是相同的，只不过多了一些结构体的使用方法：

struct Stu {char name[10];int age;
};
CmpStruct(const void* e1, const void* e2) {//假设按姓名排序//return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);//假设按年龄排序return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
void test_qsort2() {struct Stu s[] = { {"wang",20},{"liu",18} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), CmpStruct);printf("%s %d\n", s[0].name, s[0].age);printf("%s %d\n", s[1].name, s[1].age);}
int main() {//Test_qsort();test_qsort2();return 0;
}

这样也可以使用qsort函数实现结构体排序。

考虑将qsort函数特点，我们自己来实现一个可以排序任意类型的BubbleSort冒泡排序算法。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void print(int arr[], int sz) {for (int i = 0; i < sz; i++) {printf("%d ", arr[i]);}
}
int Cmpint(const void* e1,const void* e2) {return *(int*)e1 - *(int*)e2;  //升序//return *(int*)e2 - *(int*)e1;  //降序
}
struct Stu {char name[10];int age;
};
CmpStruct(const void* e1, const void* e2) {//假设按姓名排序//return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);//假设按年龄排序return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
void Swap(char* buf1, char* buf2,int size) {for (int i = 0; i < size; i++) {char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void Bubble_sort(void* base,size_t sz,size_t size,int (*cmp)(const void* e1,const void* e2)) {for (int i = 0; i < sz; i++) {for (int j = 0; j < sz - i - 1; j++) {if (cmp((char*)base + j*size, (char*)base + (j + 1)*size) > 0){//返回大于零,那就要交换Swap((char*)base + j * size, (char*)base + (j + 1) * size,size); }}}
}
void test3() {int arr[10] = { 5,3,6,9,1,7,2,10,8,4 };//我们相对arr数组的元素进行排序(升序)int sz = sizeof(arr) / sizeof(arr[0]);Bubble_sort(arr, sz, 4, Cmpint);print(arr, sz);printf("\n");//测试排序结构体struct Stu s[] = { {"wang",20},{"liu",18} };sz = sizeof(s) / sizeof(s[0]);Bubble_sort(s, sz, sizeof(s[0]), CmpStruct);printf("%s %d\n", s[0].name, s[0].age);printf("%s %d\n", s[1].name, s[1].age);
}
int main() {//Test_qsort();//test_qsort2();test3();return 0;
}