停留在一个简单的快速排序实现随机支点

问题描述

我检讨算法的东西，停留在简单的快速排序算法的实现在Java

I'm reviewing algorithm stuff and stuck in a simple quick sort algorithm implementation in java

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    int arr[];
    boolean randomPick;
    Random rand = null;

    public QuickSort(int[] inputArray) {
        arr = inputArray;
        randomPick = false;
    }

    public QuickSort(int[] inputArray, boolean random) {
        arr = inputArray;
        if (random) {
            randomPick = true;
            rand = new Random(System.currentTimeMillis());
        }
        else {
            randomPick = false;
        }
    }

    public int[] sort() {
        int start = 0;
        int end = arr.length - 1;
        try {
            _sort(start, end);
        }
        catch (StackOverflowError e) {
            System.out.println("StackOverflow: " + Arrays.toString(arr));
        }
        return arr;
    }

    private void _sort(int start, int end) {
        int i = start;
        int j = end;
        int pivotLoc;
        if (!randomPick) {
            pivotLoc = (j + i) / 2;
        }
        else {
            pivotLoc = rand.nextInt(j - i) + i;
        }
        int pivot = arr[pivotLoc];
        while (i < j) {   // swapping numbers around the pivot
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i++;
                j--;
            }
        }
        if (i - start > 1) {
            _sort(start, i);
        }
        if (end - i > 1) {
            _sort(i, end);
        }
    }
}

在code可以挑中间的数字为支点或随机选择一个数字作为支点，并通过调用 _sort 反复地排序数组。它工作在第一种情况下，但无法在第二

The code can either pick the middle number as the pivot or randomly pick a number as the pivot and it sorts the array by calling _sort recurrently. It works in the first case but fails in the second.

的情况是：当它到达一个子，因为这{3,5,5}，我==启动== 0和j == ==结束2。最后5和5被交换，I成为2和j变为1（ⅰ++和j--）。然后，因为我 - 开始＆gt; 1 ，它会调用 _sort 一遍又一遍，最终唤起计算器错误。但是应该错误发生在第一种情况下（固定支点），这并没有发生至今...

The situation is: when it reaches a subarray as this {3,5,5}, i==start==0 and j==end==2. Finally 5 and 5 are swapped, i becomes 2 and j becomes 1 (i++ and j--). Then since i - start>1 it will call _sort over and over and eventually evoke the stackoverflow error. However the error is supposed to happen in the first case (fixed pivot), which hasn't happened so far...

我不知道这有什么错我的code。我知道这是不是一个阅读快感code其他人写的，但任何帮助吗？

I don't know what's wrong with my code. I know it's not a pleasure to read code written by others but any help?

推荐答案

您已经在递归情况做了一个小错误，无论是启动和结束比较反对我的启动应该是对Ĵ

You've made a small mistake in your recursion condition, both the start and end compares are against i, the start should be against j

您有：

    if (i - start > 1) {
        _sort(start, i);
    }
    if (end - i > 1) {
        _sort(i, end);
    }

必须是：

    if (j > start) {
        _sort(start, j);
    }
    if (end > i) {
        _sort(i, end);
    }

和您的我和Ĵ比较需要允许等于：

And your i and j comparison needs to allow equals:

   // here ----v
        if (i <= j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            i++;
            j--;
        }

这篇关于停留在一个简单的快速排序实现随机支点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！