// 快速排序
// O(n^2), 但是如果middle取得比较好的话,时间复杂度为O(nlogn)
// 所以普遍认为是nlogn
// 不需要额外的存储空间,是一般情况下最好的排序方法。
#include "sort.h"
int partition(void *data, int size, int esize, int i, int k,
int (*compare)(const void *key1, const void *key2))
{
int *a = (int *)data;
int *temp;
int r[3], middle;
r[0] = rand() % (k - i + 1) + i; // 利用快排找到三个随机数的中位数
r[1] = rand() % (k - i + 1) + i;
r[3] = rand() % (k - i + 1) + i;
issort(r, 3, esize, compare);
middle = a[r[1]];
if ((temp = (int *)malloc(sizeof(int))) == NULL)
{
return -1;
}
while(i <= k)
{
while (compare(&middle, &a[i]) > 0) // 定位左边的位置
{
i++;
}
while(compare(&middle, &a[k]) < 0) // 定位右边的位置
{
k--;
}
if (i <= k) // 交换位置
{
memcpy(temp, &a[k], sizeof(int));
memcpy(&a[k], &a[i], sizeof(int));
memcpy(&a[i], temp, sizeof(int));
i++;
k--;
}
else
{
break;
}
}
free(temp);
return k;
}
int qksort(void *data, int size, int esize, int i, int k,
int (*compare)(const void *key1, const void *key2))
{
int j = (k + i - 1) / 2; // 中间值
while (i <= k)
{
if (j = partition(data, k - i + 1, esize, i, k, compare) < 0) // 取中间值
{
return -1;
}
if (qksort(data, k - j + 1, esize, i, j, compare) < 0) // 对左边递归
{
return -1;
}
i = j + 1; // 对右边递归
}
}
分享到:
相关推荐
OpenCV算法精解-代码
算法精解 C语言描述 算法精解 C语言描述 算法精解 C语言描述
全书共分为三部分:部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础;...
OpenCV算法精解代码 OpenCV算法精解代码 OpenCV算法精解代码
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术...
OpenCV是一个基于BSD许可(开源)发行的跨平台计算机视觉库...它轻量级而且高效——由一系列 C 函数和少量 C++ 类构成,同时提供了Python、Ruby、MATLAB等语言的接口,实现了图像处理和计算机视觉方面的很多通用算法。
计算机视觉,OpenCV算法精讲
C语言描述》共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:...
算法精解 c语言 中文版,适合学习算法和程序员 算法精解:C语言描述 中文版 pdf
算法精解:C语言(中文版)_带书签,讲述C语言常用算法,学习用
C语言描述》共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习《算法精解:...
算法精解中文版,这是c语言版,希望能帮助各位
全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还介绍了算法的分析方法,旨在为读者学习这本书打下坚实的基础...
《OpenCV算法精解:基于Python与C++》是以OpenCV 为工具学习数字图像处理的入门书。内容由浅入深,每一章都采用阐述基本概念、数学原理、C++ 实现、Python 实现相结合的方法,使初学者循序渐进地掌握数字图像处理...
算法精解:C语言描述中译本的源码,可作为准备学习数据结构与算法作参考
算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针...
《OpenCV算法精解:基于Python与C++》是以OpenCV 为工具学习数字图像处理的入门书。内容由浅入深,每一章都采用阐述基本概念、数学原理、C++ 实现、Python 实现相结合的方法,使初学者循序渐进地掌握数字图像处理...
《OpenCV算法精解:基于Python与C++》是以OpenCV 为工具学习数字图像处理的入门书。内容由浅入深,每一章都采用阐述基本概念、数学原理、C++ 实现、Python 实现相结合的方法,使初学者循序渐进地掌握数字图像处理...
算法精解:C语言描述一书中的源代码,学习C语言各种数据结构很有帮助。
OpenCV算法精解:基于Python与C(优秀教材,值得一看),需要请自行下载