Рекурсивный выбор сортировки Java

Question

Я искал рекурсивную сортировку выбора, используя только 2 параметра:

• Массив, который должен быть отсортирован
• значение k, которое указывает, до какого элементаон должен быть отсортирован.

Пример: SelectionSort (array [] a, int k) с существом {6,3,5,7,2} и k, равным 2, отсортирует первые 3элементы, и оставит последние элементы нетронутыми.

Я думал о том, чтобы начать с оператора if, если k равно 0, и если бы это было так, он просто вернул бы массив как есть, так как выЯ не могу отсортировать массив размером 1. Что-то вроде:

public int[] sort(int[] a){
    a = selectionSort(a, n-1);
    return a;
}

public int[] selectionSort(int[] a, int k){
    if (k = 0){
        return a;
    }
    else{
        selectionSort(a, k-1 );
               ... (part i really don't know)
}

Я понятия не имею, как выполнить часть 'else', так как знаю только, что он должен вызывать метод снова.Мне не разрешено создавать другие методы.Мне также нужно убедиться, что я использую ровно 2 параметра, ни больше, ни меньше.

Мне нужно разобраться с этим в псевдокоде, но я понимаю кое-что на Java, так что если кто-то может помочь мне, используя любой псевдоили Java, это было бы так полезно

Answer 1

Сначала несколько замечаний к вашему коду:

• Ваши методы sort и selectionSort не должны возвращать массив int[], поскольку объект массива a остается прежнимвсе время.Изменяется только содержимое этого массива.Следовательно, вы можете использовать void в качестве возвращаемого типа.
• В вашем if используйте (k == 0) вместо (k = 0)

Вы уже разобрались с первой частью.Вот как вы можете выполнить вторую часть в псевдокоде:

public void selectionSort(int[] a, int k) {
    if (k == 0) {
        return;
    }
    else {
        selectionSort(a, k-1 );
        find x such that a[x] is the smallest of a[k] ... a[a.length - 1]
        if (a[k-1] > a[x]) {
            swap a[k-1] and a[x]
        }
    }
}

Я уверен, что вы можете улучшить псевдокод до реального кода Java.

Answer 2

РЕДАКТИРОВАТЬ: ОП уточнил вопрос, это может не относиться к ОП, но это может быть для будущих посетителей.

Пожалуйста, имейте в виду комментарий на ваш вопрос в следующий раз.Только один раз, я помогу тебе, потому что ты новичок.Сделав простой поиск в Google, я нашел большую часть кода ниже на этом сайте .Я сам добавил метод selectionSort в соответствии с вашими параметрами.Обратите внимание, что переполнение стека не является службой написания кода (хотя люди и дают код довольно часто, это не является обязательным требованием при ответе).

    public void selectionSort(int a[], int n) 
    {
      recurSelectionSort(a, n, 0);
    }

    // Recursive selection sort. n is size of a[] and index
    // is index of starting element.
    static void recurSelectionSort(int a[], int n, int index)
    {

        // Return when starting and size are same
        if (index == n)
           return;

        // calling minimum index function for minimum index
        int k = minIndex(a, index, n-1);

        // Swapping when index nd minimum index are not same
        if (k != index){
           // swap
           int temp = a[k];
           a[k] = a[index];
           a[index] = temp;
        }
        // Recursively calling selection sort function
        recurSelectionSort(a, n, index + 1);
    }

    // Return minimum index
    static int minIndex(int a[], int i, int j)
    {
        if (i == j)
            return i;

        // Find minimum of remaining elements
        int k = minIndex(a, i + 1, j);

        // Return minimum of current and remaining.
        return (a[i] < a[k])? i : k;
    }