就地交换逻辑不适用于快速排序,但是使用临时变量进行交换是可行的。为什么?

在下面实现的快速排序中,我将数组的第一个元素作为枢轴。当我使用temp变量交换元素时,sort算法工作得非常好,但是当我就地交换它们时,它不起作用(将0s作为元素添加到排序数组中)。 Kindy解释了这段代码中的问题。

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

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

    public static Integer partition(int[] arr,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;
    }
lnnyynv81 回答:就地交换逻辑不适用于快速排序,但是使用临时变量进行交换是可行的。为什么?

此“就地交换”算法与“非就地交换”算法之间的区别在于,当pivotj是相同的索引时,后者有效没有。

如果我们想象两个索引相同,这就是您的代码:

        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丢失的可能性而使其变慢。

本文链接:https://www.f2er.com/2944870.html

大家都在问