我需要用 C 编写一个快速排序算法作为家庭作业。这是我得到的原型:
static inline
int* choose_pivot(int *left, int *right) {
/* FIX ME */
}
/*
* partition(left, right, pivot): push value less than *pivot on the left
* return the new pivot.
*/
int* partition(int *left, int *right, int *pivot) {
/* FIX ME */
}
/*
* quick_sort(left, right)
*/
void quick_sort(int *left, int *right) {
/* FIX ME */
}
其中
left
是指向数组第一个元素的指针,right
是指向最后一个元素的指针(不包括)。我写了以下代码:
static inline
int* choose_pivot(int *left, int *right) {
return &left[(right - left)/2];
}
void swap(int *a, int *b) {
int c = *a;
*a = *b;
*b = c;
}
int* partition(int *left, int *right, int *pivot) {
int *i, *q;
q = right;
i = left ;
while ( q > pivot ) {
while ( pivot < i )
pivot++;
while ( q > i )
q--;
if ( *q > *pivot ) {
swap(pivot,q);
}
}
swap(left, q);
return q ;
}
void quick_sort(int *left, int *right) {
if(left >= right)
return;
int *pivot = partition(left, right, choose_pivot(left, right));
quick_sort(left, pivot-1);
quick_sort(pivot + 1, right);
}
我正在运行 3 种测试:一种在排序数组中,一种在反向排序中, 一个反向排序一个。第一个测试效果很好,但第二个和这个失败了。基本上意味着这些功能不起作用。我找不到任何关于我应该做什么的文档,因为所有快速排序算法都使用它的长度而不是最后一个元素上的指针,而且我无法将我发现的那些适应我的表示。这里出了什么问题?
编辑:
评论后我的新分区函数现在看起来像这样:
int* partition(int *left, int *right, int *pivot) {
int *i, *q;
q = right;
i = left ;
int p = *pivot;
while ( q > pivot ) {
while ( p < *i )
pivot++;
while ( *q > *i )
q--;
if ( q > pivot ) {
swap(pivot,q);
}
}
swap(left, q);
return q ;
}
这里是使用指针快速排序的简单函数..
quicksort( void *a, int low, int high )
{
int pivot;
/* Termination condition! */
if ( high > low )
{
pivot = partition( a, low, high );
quicksort( a, low, pivot-1 );
quicksort( a, pivot+1, high );
}
}
隔板的作用
int partition( void *a, int low, int high )
{
int left, right;
void *pivot_item;
pivot_item = a[low];
pivot = left = low;
right = high;
while ( left < right ) {
/* Move left while item < pivot */
while( a[left] <= pivot_item ) left++;
/* Move right while item > pivot */
while( a[right] > pivot_item ) right--;
if ( left < right ) SWAP(a,left,right);
}
/* right is final position for the pivot */
a[low] = a[right];
a[right] = pivot_item;
return right;
}
希望这有帮助!
void quick_sort (int *a, int n) {
if (n < 2)
return;
int p = a[n / 2];
int *l = a;
int *r = a + n - 1;
while (l <= r) {
if (*l < p) {
l++;
}
else if (*r > p) {
r--;
}
else {
int t = *l;
*l = *r;
*r = t;
l++;
r--;
}
}
quick_sort(a, r - a + 1);
quick_sort(l, a + n - l);
}
int main () {
int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
int n = sizeof a / sizeof a[0];
quick_sort(a, n);
printf("%d", a[]);
return 0;
}
// [1]: https://www.cse.ust.hk/~dekai/271/notes/L01a/quickSort.pdf
// [2]: http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html
// [3]: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
你的做法有问题:
pivot
指向数组中的一个元素,该元素可能会在 partition
函数的过程中发生变化。您应该将 pivot
指向的值与第一个元素的值交换并将 pivot = left
设置为以防止此问题。partition
......而不是while (pivot < i)
你应该写while (*pivot < *i)
等