如何更改快速排序以降序输出元素?
我编写了一个快速排序算法,但是我想在某个地方进行更改,以便该快速排序能够按降序输出元素。
我搜索并发现我可以将partition()中的比较运算符(<)更改为其他方式(如下所示)。
//This is snippet from partition() function
while($array[$l] < $pivot) { $l++; }
while($array[$r] > $pivot) { $r--; }
但它不起作用..
如果我对下面的数组进行快速排序, $数组 = (3,9,5,7);
应该是:
$array = (9,7,5,3)
但实际输出是:
$array = (3,5,7,9)
下面是我的快速排序,它尝试按降序输出元素。 我应该如何更改以降序排序?如果您需要任何说明,请告诉我。谢谢!
$array = array(3,9,5,7);
$app = new QuicksortDescending();
$app->quicksortDesc($array, 0, count($array));
print_r($array);
class QuicksortDescending {
public function partitionDesc(&$array, $left, $right) {
$l = $left;
$r = $right;
$pivot = $array[($right+$left)/2];
while($l <= $r) {
while($array[$l] > $pivot) { $l++; }
while($array[$r] < $pivot) { $r--; }
if($l <= $r) {// if L and R haven't cross
$this->swap($array, $l, $r);
$l ++;
$j --;
}
}
return $l;
}
public function quicksortDesc(&$array, $left, $right) {
$index = $this->partitionDesc($array, $left, $right);
if($left < $index-1) { //if there is more than 1 element to sort on right subarray
$this->quicksortDesc($array, $left, $index-1);
}
if($index < $right) { //if there is more than 1 element to sort on right subarray
$this->quicksortDesc($array, $index, $right);
}
}
public function swap(&$array, $index1, $index2) {
$tmp = $array[$index1];
$array[$index1] = $array[$index2];
$array[$index2] = $tmp;
}
}
I wrote a quicksort algorithm however, I would like to make a change somewhere so that this quicksort would output elements in descending order.
I searched and found that I can change the comparison operator (<) in partition() to other way around (like below).
//This is snippet from partition() function
while($array[$l] < $pivot) { $l++; }
while($array[$r] > $pivot) { $r--; }
But it is not working..
If I quicksort the array below,
$array = (3,9,5,7);
should be:
$array = (9,7,5,3)
But actual output is:
$array = (3,5,7,9)
Below is my quicksort which trying to output elements in descending order.
How should I make change to sort in descending order? If you need any clarification please let me know. Thanks!
$array = array(3,9,5,7);
$app = new QuicksortDescending();
$app->quicksortDesc($array, 0, count($array));
print_r($array);
class QuicksortDescending {
public function partitionDesc(&$array, $left, $right) {
$l = $left;
$r = $right;
$pivot = $array[($right+$left)/2];
while($l <= $r) {
while($array[$l] > $pivot) { $l++; }
while($array[$r] < $pivot) { $r--; }
if($l <= $r) {// if L and R haven't cross
$this->swap($array, $l, $r);
$l ++;
$j --;
}
}
return $l;
}
public function quicksortDesc(&$array, $left, $right) {
$index = $this->partitionDesc($array, $left, $right);
if($left < $index-1) { //if there is more than 1 element to sort on right subarray
$this->quicksortDesc($array, $left, $index-1);
}
if($index < $right) { //if there is more than 1 element to sort on right subarray
$this->quicksortDesc($array, $index, $right);
}
}
public function swap(&$array, $index1, $index2) {
$tmp = $array[$index1];
$array[$index1] = $array[$index2];
$array[$index2] = $tmp;
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
比较两个元素时,只需将比较运算符
<
与>
交换,反之亦然:Just swap the comparison operators
<
with>
and vice versa when comparing two elements:不要更改快速排序的实现,而是从末尾迭代数组:
Instead of changing the quicksort implementation, iterate the array from the end: