Сортировка рекурсивных вставок

Question

У меня есть следующая проблема, с которой я сталкиваюсь, особенно в некоторых частях, где мне дается часть кода.

Описание проблемы: При наличии массива целых чисел вернуть массив, содержащий одинаковые целые числа, отсортированные от наибольшего к наименьшему, используя сортировку вставкой. Мы будем использовать соглашение о рассмотрении только той части массива, которая начинается с данного индекса и заканчивается в другом. Таким образом, рекурсивный вызов может работать через любую часть массива. Первоначальный вызов передается с индексом 0 и индексом до последнего элемента.

inserttionSort ([2, 1, 3, -2, 8], 0, 4) → [8, 3, 2, 1 , -2] inserttionSort ([2, 6, -4], 0, 2) → [6, 2, -4] inserttionSort ([2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22], 0, 10) → [22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2]

Код дан:

public int[] insertionSort(int[] nums, int begin, int end) {

}

void insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

У меня возникли проблемы с пониманием того, что означает переменная "element" в методе "insert".

Вот код, который я написал для него.

public int[] insertionSort(int[] nums, int begin, int end) {
 if(begin >= end) return nums;
 else if (begin < end){

   int element = nums.length;
   insert(nums, begin, end, element);
   insertionSort(nums, begin, end);

  }
  return nums;
}

void insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

Это ошибки, которые я получаю из своего кода:

Answer 1

Приведенное ниже решение проходит все ваши тесты. Ваш метод вставки должен выглядеть примерно так:

public static int[] insertionSort(int[] nums, int begin, int end) {
if (begin >= end) {
    return nums;
}

for (int i = 0; i < end; i++) {
    insert(nums, i, end - 1, nums[end]);
}
return nums;

}

Ниже приведено полное решение для вашей краткой справки.

public class Solution {

public static void main(String[] args) {
    int[] input1 = { 2, 1, 3, -2, 8 };
    int[] result1 = insertionSort(input1, 0, 4);
    printArray(result1);
    int[] input2 = { 2, 6, -4 };
    int[] result2 = insertionSort(input2, 0, 2);
    printArray(result2);
    int[] input3 = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 };
    int[] result3 = insertionSort(input3, 0, 10);
    printArray(result3);
    int[] input4 = { 6, 6, 6, };
    int[] result4 = insertionSort(input4, 0, 2);
    printArray(result4);
    int[] input5 = { 8 };
    int[] result5 = insertionSort(input5, 0, 0);
    printArray(result5);
}

public static void printArray(int[] input) {
    System.out.print("[ ");
    for (int i = 0; i < input.length; i++) {
        System.out.print(input[i] + " ");
    }
    System.out.println("]");
}

public static int[] insertionSort(int[] nums, int begin, int end) {
    if (begin >= end) {
        return nums;
    }

    for (int i = 0; i < end; i++) {
        insert(nums, i, end - 1, nums[end]);
    }
    return nums;
}

static void insert(int[] nums, int begin, int end, int element) {
    int index = end;
    while (index >= begin && nums[index] < element) {
        index--;
    }
    for (int i = end; i > index; i--) {
        nums[i + 1] = nums[i];
    }
    nums[index + 1] = element;
}

}

Answer 2

Я думаю, это более или менее то, что вы пытаетесь сделать.

class RecursiveInsertionSort {

    public static void main(String[ ] args) {
        int[] input1 = {2, 1, 3, -2, 8};
        int[] input2 = {2, 6, -4};
        int[] input3 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22};

        int[] res1 = insertionSort(input1, 0, 4);
        // res1 = [8, 3, 2, 1, -2]

        int[] res2 = insertionSort(input2, 0, 2);
        // res2 = [6, 2, -4]

        int[] res3 = insertionSort(input3, 0, 10);
        // res3 = [22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2]
    }

    public static int[] insertionSort(int[] nums, int begin, int end) {
        if(begin >= end) {
            return nums; // We are done
        }

        // Sort the first n-1 elements
        insertionSort(nums, begin, end - 1);

        // Insert the nth element in the first n-1 elements array
        insert(nums, begin, end - 1, nums[end]);

        return nums;
    }

    static void insert(int[] nums, int begin, int end, int element) {
        int index = end;
        while(index >= begin && nums[index] < element) {
            index--;
        }
        for(int i = end; i > index; i--) {
            nums[i + 1] = nums[i];
        }
        nums[index + 1] = element;
    }
}

Answer 3

Нерекурсивная версия:

    public static int[] insertionSort(int[] nums, int begin, int end) {

        for (int i = begin + 1; i <= end; i++) {
            insert(nums, begin, i - 1, nums[i]);
        }

        return nums;
    }

    public static void insert(int[] nums, int begin, int end, int element) {
        int index=end;
        while(index>=begin && nums[index]<element) {
            index--;
        }
        for(int i=end; i>index; i--) {
            nums[i+1] = nums[i];
        }
        nums[index+1] = element;
    }

    public static void main(String[] args) {
        int[] is = new int[]{5,6,7,2};
        insertionSort(is, 0, is.length - 1);
        System.out.println(Arrays.toString(is));
    }

Рекурсивная версия:

    public static int[] insertionSort(int[] nums, int begin, int end) {
        if (begin>=end) {
            return nums;
        }

        insertionSort(nums, begin, end-1);
        insert(nums, begin, end-1, nums[end]);

        return nums;
    }

    public static void insert(int[] nums, int begin, int end, int element) {
        int index=end;
        while(index>=begin && nums[index]<element) {
            index--;
        }
        for(int i=end; i>index; i--) {
            nums[i+1] = nums[i];
        }
        nums[index+1] = element;
    }

    public static void main(String[] args) {
        int[] is = new int[]{5,6,7,2};
        System.out.println();
        insertionSort(is, 0, is.length - 1);
        System.out.println(Arrays.toString(is));
    }

Answer 4

так что вы делаете неправильно, передавая элемент как nums.length, element это номер для вставки, то есть после каждого рекурсивного вызова это будет (begin + 1) th-й элемент, и вы продолжите увеличивать, начиная с 1, так как эта часть массива (от 0 до начала) будет уже отсортирована. В следующий раз сортировка вставок будет вызываться с начала + 1 до конца. Вот рабочий образец ниже.

public class Main
{

    public static int[] insertionSort(int[] nums, int begin, int end) {
 if(begin >= end) return nums;
 else if (begin < end){

   int element = nums[begin+1];
   insert(nums, 0, begin, element);
   insertionSort(nums, begin+1, end);

  }
  return nums;
}

static void  insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

    public static void main(String[] args) {
        int[] a = {3,41,0,10};
        int[] t = insertionSort(a, 0, 3);
        for (int i =0; i<4; i++){
            System.out.println(t[i]);
        }
    }
}