java - 具有重复值的QuickSort

我已经实现了以下代码，但是对于我的数组具有重复值的情况，它似乎不起作用。

 private int partition(Integer[] arr,int left, int right)
 {
    int i = left;
    int j = right;
    int pivot = arr[left];

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

        if(i < j)
        {
            print(arr);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        else return j;
    }
}


public void quickSort(Integer[] arr, int left,int right)
{
    print(arr);
    if(left >= right) return;

    int index = partition(arr,left,right);

    quickSort(arr,left,index-1);
    quickSort(arr,index+1,right);
}

我发现有一个稍微不同的实现，在这种情况下效果很好，但是我不明白为什么。任何帮助，将不胜感激。

    private int partition(Integer[] arr, int left, int right)
    {
    int i = left-1;
    int j = right+1;
    int pivot = arr[left];


    while(true)
    {

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

        if(i < j)
        {
            print(arr);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        else return j;
     }
     }

    public void quickSort(Integer[] arr, int left,int right)
    {
    print(arr);
    if(left >= right) return;

    int index = partition(arr,left,right);

    quickSort(arr,left,index);
    quickSort(arr,index+1,right);
    }

最佳答案

1，选择一个元素作为枢轴

2，将所有小于枢轴的元素移至左侧，将所有大于枢轴的元素移至右侧

3.将以上步骤同时应用于两个部分

以下方法实现了快速排序。它定义了一种对子数组进行排序的递归方法，还定义了将数组划分为两部分的方法。

public static void quickSort(int[] data, int first, int last)
      {
        if (first >= last)return;
        int pivot = partition(data, first, last);
        quickSort(data, first, pivot - 1); // sort the left part
        quickSort(data, pivot + 1, last); // sort the right part
      }

分区过程包括拾取枢轴并围绕枢轴移动元素。一个简单的过程如下：

1，分配一个新的保存分区结果的临时数组

2.拾取第一个元素作为枢轴

3.从第二个元素扫描数组，将每个元素与支点进行比较，如果其小于或等于支点，则将其放到临时数组的左端，否则将其放到右端。

4，最后将结果从临时数组复制回原始数组

public static int partition(int[] data, int first, int last)
 {
int[] temp = new int[last - first + 1];
int pivot = data[first];
int i = 0, j = last - first, k;

for (k = first + 1; k <= last; k++)
{
    if (data[k] <= pivot)
        temp[i++] = data[k];
    else
        temp[j--] = data[k];
}
temp[i] = data[first];

// Copy data back into original array
for (k = first; k <= last; k++)
    data[k] = temp[k - first];
return first + i;
  }

上面的方法需要额外的存储（线性空间）来保存中间结果。以下是该分区的就地版本，不需要附加存储：

1.拾取数组中的第一个元素作为枢轴

2.从两端向中间扫描阵列

3，只要发现错误的两个元素，就将它们交换

4，当两端的扫描在中间相遇时，将轴与该中间元素交换

public static int partition(int[] data, int first, int last)
 {
int pivot = data[first];
int left = first, right = last;

while (left < right)
{
    // Find an element bigger than the pivot from the left
    while (data[left] <= pivot && left < right)
        left++;
    // Find an element smaller than the pivot from the right
    while (data[right] > pivot)
        right--;
    // Swap the two elements found
    if (left < right)
        swap(data, left, right);
}

// move the pivot element to the middle
swap (data, first, right);
return right; }

1，如果每次选择的枢轴是中位数元素，则划分为偶数，划分级别为O（log n）

2.如果每次选择的枢轴都是最小或最大元素（每次运气不好），则一个部分没有元素，而另一部分则包含除枢轴本身以外的所有元素。这将生成n个分区级别，这基本上类似于选择排序。

3.如果每次随机选择枢轴，则平均而言，分区将是均匀的，并且分区级别接近O（log n）。

希望这可以为您带来有关“快速排序”的正确想法，也需要一些时间来阅读我在摘要中提供的所有注释。