C随机枢轴快速排序（改进分区function）
我是一名计算机科学专业的学生（刚刚开始），我正在从伪代码编写Quicksort的随机枢轴版本。 我已经编写并测试了它，但这一切都完美无缺……
分区部分看起来有点过于复杂，因为它感觉我已经错过了某些东西或者过分了。 我无法理解它是否正常或者我是否犯了一些可以避免的错误。
长话短说：它有效，但如何做得更好？
在此先感谢您的帮助
void partition(int a[],int start,int end) { srand (time(NULL)); int pivotpos = 3; //start + rand() % (end-start); int i = start; // index 1 int j = end; // index 2 int flag = 1; int pivot = a[pivotpos]; // sets the pivot's value while(i<j && flag) // main loop { flag = 0; while (a[i]pivot) { j--; } if(a[i]>a[j]) // swap && sets new pivot, and restores the flag { swap(&a[i],&a[j]); if(pivotpos == i) pivotpos = j; else if(pivotpos == j) pivotpos = i; flag++; } else if(a[i] == a[j]) // avoids getting suck on a mirror of values (fx pivot on pos 3 of : 1-0-0-1-1) { if(pivotpos == i) j--; else if(pivotpos == j) i++; else { i++; j--; } flag++; } } } 这是来自Introduction to Algorithms的partition()的伪代码，它被称为Lomuto的分区算法，本书下面有一个很好的解释。
PARTITION(A, p, r) 1 x ← A[r] 2 i ← p - 1 3 for j ← p to r - 1 4 do if A[j] ≤ x 5 then i ←i + 1 6 exchange A[i] ↔ A[j] 7 exchange A[i + 1] ↔ A[r] 8 return i +1
您可以基于上面的伪代码轻松实现随机分区实现。 正如评论所指出的那样，将srand()移出partition 。
// srand(time(NULL)); int partition(int* arr, int start, int end) { int pivot_index = start + rand() % (end - start + 1); int pivot = arr[pivot_index ]; swap(&arr[pivot_index ], &arr[end]); // swap random pivot to end. pivot_index = end; int i = start -1; for(int j = start; j <= end - 1; j++) { if(arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[pivot_index]); // place the pivot to right place return i + 1; }
本书中提到了另一种分区方法，称为Hoare的分区算法，伪代码如下：
Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true repeat j = j - 1 until A[j] <= x repeat i = i + 1 until A[i] >= x if i < j swap( A[i], A[j] ) else return j
在分区之后，A [p ... j]中的每个元素都是A [j + 1 ... r]中的每个元素。 快速排序将是：
QUICKSORT (A, p, r) if p < r then q = Hoare-Partition(A, p, r) QUICKSORT(A, p, q) QUICKSORT(A, q+1, r)
有多种方法可以对快速排序进行分区，以下可能是最简单的方法。 通常使用两个分区学校：
- Squeeze – 折叠序列的两端，直到找到合适的交换对 ，然后将两个元素交换到分区的正确边。 实现起来并不容易，但可以比替代方案更有效（减少交换计数）…
- 扫描 – 使用单个从左到右（或从右到左）扫描值，将值交换为递增的枢轴索引，该索引在算法运行时移动。 实现起来非常简单，如下所示。
我更喜欢Sweep算法，因为人们学习快速排序和分区只是因为它实现起来非常简单。 两者都可以实现为执行就地分区，如下面的实现中的情况。 除了在swap()您将看到存储在临时存储中的值。
使用随机数据透视表选择只是其中的一小部分。 下面显示了如何初始化随机数生成器，并演示了您将要找到的最简单的分区算法和快速排序用法。
除其他事项外，它演示了在C / C ++中，您不需要分区的两端，因为可以使用简单的指针算法来调整分区的“顶部”一半。 有关如何完成此操作，请参阅quicksort()函数。
#include #include #include void swap(int *lhs, int *rhs) { if (lhs == rhs) return; int tmp = *lhs; *lhs = *rhs; *rhs = tmp; } int partition(int ar[], int len) { int i, pvt=0; // swap random slot selection to end. // ar[len-1] will hold the pivot value. swap(ar + (rand() % len), ar+(len-1)); for (i=0; i
输出 （明显不同）
32 49 42 49 5 18 41 48 22 33 40 27 12 47 41 6 50 27 8 7 5 6 7 8 12 18 22 27 27 32 33 40 41 41 42 47 48 49 49 50
注意：这并不考虑使用rand() % len模偏差，坦率地说，对于这个例子来说这样做太过分了。 如果它很关键，我会完全使用另一台发电机。 有关为快速分区选择随机枢轴位置的方法的杰出讨论可以在本网站的这篇文章中找到 ，包括许多指向不同方法的链接。 我建议复习一下。