Я читаю MSD по следующей ссылке.как msd уменьшает количество проверяемых ключей
http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf
Здесь упоминается, что в МСД не должны изучить все ключи на странице 20. Как это связано с программирования на странице 18. Когда я пытаюсь поставить пример в код блуждания через I я не могу понять, как мы сократили, чтобы изучить все ключи.
Спасибо!
Допустим, у вас есть: (действительно может быть что угодно 0 в)
600000
100000
300000
500000
400000
200000
Если вы только сортировку по наиболее значащей цифры, вы получите:
100000
200000
300000
400000
500000
600000
После этого массив уже отсортирован и мы можем остановиться - нет необходимости проверять другие цифры.
Хотя это может быть не так идеально на практике, есть, конечно, случаи, когда мы не должны оценивать все цифр всех элементов.
Оператор if (hi <= lo + 1) return; должен возвращать его, если в подмассиве есть только один элемент, предотвращающий проверку ненужных данных.