java - 快速排序分区功能

Question

想请教一个关于quick sort partition function()的问题。如果我替换语句

int pivot = arr[(left + right) / 2];

与

int pivot = arr[left+(right-left)>>1];

当数组中有重复元素时，该算法不起作用。为什么？谢谢。

int partition(int arr[], int left, int right) 

{ 

      int i = left, j = right; 

      int tmp; 

      int pivot = arr[(left + right) / 2]; **********        

      while (i <= j) { 

            while (arr[i] < pivot)  i++; 
            while (arr[j] > pivot)  j--; 

            if (i <= j) { 
                  tmp = arr[i]; 
                  arr[i] = arr[j];
                  arr[j] = tmp; 
                  i++; 
                  j--; 
            } 
      }     

      return i; 
} 

Answer 1

问题是运算符的优先级。

您使用的 3 的顺序如下:

1. 乘法
2. 添加剂
3. 转变

发生的事情是，left+(right-left)>>1 被当作 (left+(right-left))>>1，这不相等，而只是 right >> 1 或 right/2。

您可以在此处查看优先级:http://docs.oracle.com/javase/tutorial/java/nutsandbolts/operators.html