java - 就地交换逻辑在快速排序中不起作用，但使用临时变量进行交换可以工作。为什么？

Question

在下面实现的快速排序中，我将数组的第一个元素作为基准。当我使用临时变量交换元素时，排序算法工作得很好，但当我交换它们就位时，它不起作用(在排序数组中添加 0 作为元素)。请解释一下这段代码有什么问题。

    public static void quickSort(int[] arr, int start, int end)
    {
        if(start < end)
        {
            int partition = partition(arr, start, end);

            quickSort(arr, start, partition-1);
            quickSort(arr, partition+1, end);
        }
    }

    public static Integer partition(int[] arr, int start, int end)
    {

        int pivot = start, i = start, j = end;

        while(i<j)
        {
            while(i<end && arr[i]<=arr[pivot])
            {
                i++;
            }

            while(arr[j]>arr[pivot])
            {
                j--;
            }

            if(i<j)
            {
                arr[i] = arr[i] + arr[j];
                arr[j] = arr[i] - arr[j];
                arr[i] = arr[i] - arr[j];   //It doesn't work

               /*int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;     
                */                          //It works


            }
        }
        arr[pivot] = arr[pivot] + arr[j];
        arr[j] = arr[pivot] - arr[j];
        arr[pivot] = arr[pivot] - arr[j];   //It doesn't work

        /*int temp = arr[pivot];
        arr[pivot] = arr[j];
        arr[j] = temp;     
        */                          //It works
        return j;
    }

Answer 1

这种“就地交换”算法和“异地交换”算法的区别在于，后者在 pivot 时起作用。和j是相同的索引，但前者不是。

如果我们假设两个索引相同，那么您的代码如下所示:

        arr[j] = arr[j] + arr[j];
        arr[j] = arr[j] - arr[j];
        arr[j] = arr[j] - arr[j];

第二行始终设置 arr[j]为 0，无论其原始值如何，第三行将其保留为 0。如果您绝对必须不使用额外的局部变量，那么您将需要使用 if(j != pivot) { ... } 来保护交换。 。但这可能会因为额外的比较、条件跳转以及 branch prediction 的潜力而使其变慢。未命中。