java - 对数组进行快速排序并在 Java 中进行二进制搜索

Question

所以我必须制作一种方法，该方法使用快速排序作为排序算法而不使用 Java API。然后我必须编写另一个方法，返回排序后的数组，如果在其中找到搜索到的元素，则使用二进制搜索返回 true。我不知道我在哪里犯了愚蠢的错误。

public class Aufgabe1 {
    public static void sort(int[] array) {
        /* TODO: add code here */
        sort(array, 0, array.length - 1);

    }

    public static void sort(int[] array, int start, int end) {
        int i = start;
        int j = end;
        int pivot = array[(start+end)/2];
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (pivot < array[j]) {
                j--;
            }

            if (i <=j) {
                int h = array[i];
                array[i] = array[j];
                array[j] = h;
                i++;
                j--;
            }
        }
        if (start < i-1) {
            sort(array, start, i - 1);
        }
        if (i < end) {
            sort(array, i, end);
        }

    }

    public static boolean binSearch(int[] array, int elem) {
        /* TODO: add code here */

        int i = 0; //the first element
        int j = array.length -1; // the last element

        while (i<=j) {
            int k = i + ((i+j)/2); //try the middle word
            if (elem == array[k]){
                return true;
            }
            if (elem < array[k]) {
                j = k-1;
                return false;
            }else {
                i = k+1;
                return false;
            }
        }
        return false;
    }

    //just for testing
    public static void main(String[] args) {

        int[] arr = new int[] {5, 3, 7, 2, 1, 6};

        sort(arr);

        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");

        }
        binSearch(arr,5);

    }

Answer 1

试试这个，修正了一些小错误，你在错误的地方有几个 i 和 j。虽然，我建议您将代码模块化一些，因为这将使事情更容易阅读，并让您更好地了解正在发生的事情。请注意，您实际上并没有返回正确的位置，因此它将始终返回 false，除非该元素位于中间。附带说明一下，也不鼓励使用 static。

编辑:此外，我刚刚注意到您在结束类(class)时缺少一个“}”。

public class Main
{
    public static void sort(int[] array) 
    {
        /* TODO: add code here */
        sort(array, 0, array.length - 1);
    }

    public static void sort(int[] array, int start, int end) 
    {
        int i = start;
        int j = end;
        int pivot = array[(start+end)/2];

        while (i <= j)
        {
            while (array[i] < pivot) 
            {
                i++;
            }

            while (pivot < array[j]) 
            {
                j--;
            }

            if (i <=j)
            {
                int h = array[i];
                array[i] = array[j];
                array[j] = h;
                i++;
                j--;
            }
        }

        if (start < i-1)
        {
            sort(array, start, i - 1);
        }

        if (i < end) 
        {
            sort(array, i, end);
        }
    }

    public static boolean binSearch(int[] array, int elem) 
    {
        /* TODO: add code here */

        int i = 0; //the first element
        int j = array.length -1; // the last element
        int k = i + ((i+j)/2); //try the middle word

        while (k >= 0 && k < array.length) 
        {
            if (elem == array[k])
            {
                return true;
            }

            if (elem < array[k]) 
            {
                k--;
            }

            else
            {
                k++;
            }
        }

        return false;
    }

    //just for testing
    public static void main(String[] args)
    {
        int[] arr = new int[] {5, 3, 7, 2, 1, 6};

        sort(arr);

        for(int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");
        }

        if (binSearch(arr,5))
        {
            System.out.println("TRUE");
        }
    }
}