我已经实现了以下快速选择算法来实现O(n)
中位数选择的复杂性(更一般地说是第 k 个最小的数字):
static size_t partition(struct point **points_ptr, size_t points_size, size_t pivot_idx)
{
const double pivot_value = points_ptr[pivot_idx]->distance;
/* Move pivot to the end. */
SWAP(points_ptr[pivot_idx], points_ptr[points_size - 1], struct point *);
/* Perform the element moving. */
size_t border_idx = 0;
for (size_t i = 0; i < points_size - 1; ++i) {
if (points_ptr[i]->distance < pivot_value) {
SWAP(points_ptr[border_idx], points_ptr[i], struct point *);
border_idx++;
}
}
/* Move pivot to act as a border element. */
SWAP(points_ptr[border_idx], points_ptr[points_size - 1], struct point *);
return border_idx;
}
static struct point * qselect(struct point **points_ptr, size_t points_size, size_t k)
{
const size_t pivot_idx = partition(points_ptr, points_size, rand() % points_size);
if (k == pivot_idx) { //k lies on the same place as a pivot
return points_ptr[pivot_idx];
} else if (k < pivot_idx) { //k lies on the left of the pivot
//points_ptr remains the same
points_size = pivot_idx;
//k remains the same
} else { //k lies on the right of the pivot
points_ptr += pivot_idx + 1;
points_size -= pivot_idx + 1;
k -= pivot_idx + 1;
}
return qselect(points_ptr, points_size, k);
}
然后我尝试将它与 glibc 进行比较,qsort()
并O(nlog(n))
对其卓越的性能感到惊讶。这是测量代码:
double wtime;
wtime = 0.0;
for (size_t i = 0; i < 1000; ++i) {
qsort(points_ptr, points_size, sizeof (*points_ptr), compar_rand);
wtime -= omp_get_wtime();
qsort(points_ptr, points_size, sizeof (*points_ptr), compar_distance);
wtime += omp_get_wtime();
}
printf("qsort took %f\n", wtime);
wtime = 0.0;
for (size_t i = 0; i < 1000; ++i) {
qsort(points_ptr, points_size, sizeof (*points_ptr), compar_rand);
wtime -= omp_get_wtime();
qselect(points_ptr, points_size, points_size / 2);
wtime += omp_get_wtime();
}
printf("qselect took %f\n", wtime);
对于 10000 个元素的数组,qsort took 0.280432
结果类似于。qselect took 8.516676
为什么快速排序比快速选择快?