二进制快速排序 [英] binary quicksort

问题描述

我想实现[Robert Sedgewick的书] [1]中的Binary Quicksort算法。看起来像这样：

I want to implement the Binary Quicksort algorithm from [Robert Sedgewick's book][1]. It looks like this:

    public class quickb{
public static final int bitsword=32;

public static void quicksortB(int a[],int l,int r,int d){
 int i=l;
int j=r;
if (r<=l || d>bitsword) return ;

 while (j!=i)
{

  while (digit(a[i],d)==0 && (i<j)) i++;
while (digit(a[j],d)==1 && (j>i)) j--;
   int t=a[i];
a[i]=a[j];
a[j]=t;
}
      if (digit(a[r],d)== 0) j--;

  quicksortB(a,l,j-1,d+1);
 quicksortB(a,j,r,d+1);




}

public static void main(String[]args){
   int a[]=new int[]{4,7,3,9,8,2};


 quicksortB(a,0,a.length-1,0);

 for (int i=0;i<a.length;i++){
  System.out.println(a[i]);
}



}

 public static int digit(int m,int d){


    return (m>>d)&1;



}
}

我更改了它可以编译，但是结果是
4
8
9
3
7
2
也许代码在书中是正确的有人可以帮我解决这个问题吗？

i have changed it compiles but result is 4 8 9 3 7 2 maybe code is in correct in book can anybody help me to solve this problem?

推荐答案

使用TJMonk15校正（-有时）。

我试图执行，这就是发生的情况

With TJMonk15 correction (-- in the while).
I've tried to execute and that's what happens

最终数组是489372，带有 log：

The final array is 489372, with this "log":

交换（从左到右）：7和8

交换（从左到右）：3和3

交换（从左到右）：3和9

交换（从左到右）：3和3

交换（从左到右）：7和7

Swapping (from left to right): 7 with 8
Swapping (from left to right): 3 with 3
Swapping (from left to right): 3 with 9
Swapping (from left to right): 3 with 3
Swapping (from left to right): 7 with 7

根据我的说法，没有交换是正确的。

No swapping is correct according to me..

我不明白为什么 int j = r-1 ，并且您将 length-1 用作r，则j开头等于 length-2 。

I don't understand why int j=r-1 and you use length-1 as r, then j is equal to length-2 at the beginning.

这篇关于二进制快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！