详解基于快速排序算法的qsort的模拟实现

目录

1. 快速排序

1.1 快速排序理论分析 

1.2 快速排序的模拟实现 

2. qsort的模拟实现 

2.1 qsort的理论分析

2.2 qsort的模拟实现

---

qsort函数是基于快速排序思想设计的可以针对任意数据类型的c语言函数。要对qsort进行模拟实现，首先就要理解快速排序。

1. 快速排序

1.1 快速排序理论分析 

上一期博客选择排序，冒泡排序，插入排序，快速排序及其优化-CSDN博客我们大概讲解了快速排序的思路，现在我们来详细讲解以下快速排序。

 让我们来逐帧分析快速排序的思想。

1. 第一步便是找到基准数，开始分区：基准数可以选择第一个，最后一个，也可以是随机的（为了便于理解，以下的图都默认选的是第一个，当然代码是随机的，重要的是先把交换三个数的本质理解到）

2.  分而治之，调整后基准数的左右两边，再进行相同的操作，直到不能再排序（数组长度为1时，就不能再排序了）

 

1.2 快速排序的模拟实现 

以上便是对快速排序底层逻辑的分析， 接下来以c语言为例，讲解模拟实现快速排序。

1. 选一个基准数，这里选的是首元素

2. 开始分区，遍历整个数组，开始交换位置（三个数），小的在前，大的在后

3. 开始递归，左右两边都要开始递归，由于需要知道边界，所以分区时，应该再返回基准数的地址。同时为了避免递归递而不归，应设置最小的长度

/*返回值：基准数最后的下标参数：需要分区的部分（从头到尾开始排）
*/
int partition(int arr[], int start, int end)
{int len = end - start;int* ppivot = arr + start;int* s = ppivot + 1;while (len--){if (*ppivot >= *s){int temp = *s;*s = *(ppivot + 1);*(ppivot + 1) = *ppivot;*ppivot = temp;ppivot++;}s++;}return ppivot - arr;
}/*返回值：arr首元素的地址参数：需要排序的部分（从头到尾）
*/int* quick_sort(int arr[], int start, int end)
{assert(arr);int* p = arr;if (end > start){int pivot = partition(arr, start, end);quick_sort(arr, start, pivot - 1);quick_sort(arr, pivot + 1, end);}return p;
}

 当然，对于分区的排序可以进行优化，使用双指针也可以。双指针就是首尾往中间交换的模式，效率自然更高。这里不过多展开去讲。

2. qsort的模拟实现 

2.1 qsort的理论分析

C 库函数 void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) 对数组进行排序。它可以接收任意类型进行排序，其实跟快速排序接收int类型差不多，只是这里多了一个强制类型转换。

2.2 qsort的模拟实现

qsort的模拟实现，基本就是在quick_sort上做改造，将原来只可以进行int数据类型的改成任意数据类型。

1. 原来是数值之间的比较，现在要改成有专门的比较数据大小的函数（字符：strcmp）

2. 交换位置，原来int直接就可以交换数据，现在强制类型转换成char*后，单位转换的变少了，则需要循环4次，才够int 四个字节

3. 指针加1， 原来有确定类型，现在是void* 原来加1，现在就应该加size

int cmp_int(const void* a, const void* b)
{return *(int*)a - *(int*)b;
}/*返回值：基准数最后的下标参数：需要分区的部分（从头到尾开始排）
*/
int partition(void* arr, int start, int end, size_t size)
{int len = end - start;char* ppivot = ((char*)arr + start * size);char* s = ppivot + size;while (len--){if ((*cmp_int)(ppivot, s) > 0){for (int i = 0; i < size; i++){int temp = *(s+i);*(s+i) = *(ppivot + size + i);*(ppivot + size + i) = *(ppivot+i);*(ppivot+i) = temp;}ppivot += size;}s += size;}return (int)((ppivot - (char*)arr) / size);
}/*返回值：arr首元素的地址参数：需要排序的部分（从头到尾）
*/void* quick_sort(void* arr, int start, int end,size_t size)
{assert(arr);if (end > start){int pivot = partition(arr, start, end,size);quick_sort(arr, start, pivot - 1,size);quick_sort(arr, pivot + 1, end,size);}return arr;
}void* my_qsort(void* arr, size_t len, size_t size, int (*cmp_int)(const void* a, const void* b))
{assert(arr);int start = 0;int end = (int)len - 1;quick_sort(arr, start, end, size);return arr;
}

感谢各位大佬的支持与指正！！！