C # Merge Sort создает ошибку переполнения стека - PullRequest
Новая
       17

C # Merge Sort создает ошибку переполнения стека

0 голосов
/ 10 марта 2019

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

if (array.Length > 1)

как-то создает ошибку, но я не уверен, как. Это код. 

public static string[] MergeSort(string[]array)
    {
        if (array.Length > 1)
        {
            int mid = array.Length / 2;
            string[] lefthalf = new string[mid];
            for (int l = 0; l < mid; l++)
            {
                lefthalf[l] = array[l];
            }
            string[] righthalf = new string[mid + 1];
            for (int r = mid; r < righthalf.Length ; r++)
            {
                righthalf[r] = array[r];
            }
            MergeSort(lefthalf);
            MergeSort(righthalf);
            int i = 0;
            int j = 0;
            int k = 0;
            while (i < lefthalf.Length && j < righthalf.Length)
            {
                if (String.Compare(lefthalf[i],righthalf[j]) == -1)
                {
                    array[k] = lefthalf[i];
                    i += 1;
                }
                else
                {
                    array[k] = righthalf[k];
                    j += 1;
                }
                k = k + 1;
            }

            while (i< lefthalf.Length)
            {
                array[k] = lefthalf[i];
                i += 1;
                k += 1;
            }
            while (j < righthalf.Length)
            {
                array[k] = righthalf[j];
                j += 1;
                k += 1;
            }
        }
        return array;
    }

массив начинается как массив из 100 строк. Когда я пытаюсь использовать эту процедуру, программа возвращает эту ошибку:

System.StackOverflowException: 'Исключение типа Вышло исключение System.StackOverflowException.

После того, как мне сообщили в комментариях, я попытался отладить, кажется, что он находится в бесконечном цикле создания массива длины 2 с нулем в качестве первого элемента, а второй элемент - второй строкой в ​​моем первом массив. Кажется, он никогда не вытаскивает его и не переносит на следующий этап сортировки слиянием.

Любая помощь будет оценена.

1 Ответ

0 голосов
/ 10 марта 2019

Для рекурсии вам нужно поставить return перед рекурсивными вызовами MergeSort, иначе рекурсивный цикл никогда не завершится, и вы просто продолжите укладывать вызовы функции MergeSort в стек вызовов. Кроме того, второй вызов MergeSort фактически никогда не будет вызван, первый рекурсивный вызов завершает функцию до того, как она сможет выполнить.

Вы в основном зацикливаетесь от начала функции до первого рекурсивного вызова этой функции.

...