重养网站建设,包头网站建设平台广和,社交类网站开发需求,wordpress 分类导航目录
1. 快速排序
1.1 快速排序理论分析
1.2 快速排序的模拟实现
2. qsort的模拟实现
2.1 qsort的理论分析
2.2 qsort的模拟实现 qsort函数是基于快速排序思想设计的可以针对任意数据类型的c语言函数。要对qsort进行模拟实现#xff0c;首先就要理解快速排序。
1. 快…目录
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 *(si);*(si) *(ppivot size i);*(ppivot size i) *(ppivoti);*(ppivoti) 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;
} 感谢各位大佬的支持与指正
