快速排序数组并在Java中执行二进制搜索 [英] quicksort an array and do binary search in java

问题描述

因此，我必须设计一种无需使用Java API即可将quicksort用作排序算法的方法.然后，我必须编写另一种方法来返回排序后的数组，并且如果在其中找到了被搜索的元素，则使用二进制搜索返回true.我不知道我在哪里犯了这个愚蠢的错误.

So I have to make a method which is using the quicksort as a sort algorithm without using the Java API. Then I have to write another method that gives the sorted array back and using the binary search return true if the searched element is found in it. I have no idea where am I making the stupid mistake.

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);

    }

推荐答案

尝试一下，修复了一些小错误，您在错误的位置放了几个i和j.虽然，我建议您对代码进行一些模块化，因为这将使事情更易于阅读，并使您对正在发生的事情有更好的了解.请注意，您实际上并未返回正确的位置，因此除非元素位于中间，否则它将始终返回false.顺便提一句，不建议使用static.

Try this, fixed a few small errors, you had a couple of i and j in the wrong places. Although, I suggest you modularise your code a bit as this will make things easier to read and give you a better idea of what is happening. Note that you are not actually returning in the correct places, so it will always return false unless the element is in the middle. On a side note, the use of static is also discouraged.

而且，我刚刚注意到您在结束课程的末尾缺少一个'}'.

Also, I have just noticed you have a '}' missing at the end where you should close the 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");
        }
    }
}

这篇关于快速排序数组并在Java中执行二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！