Понимание Radix Сортировка в C
Я использую это программа здесь для справки, чтобы увидеть, как реализован алгоритм. Я понимаю большую часть этого, кроме этой части:
/*
* update all the buckets. If bucket[8] has 2,
* then there are 2 elements present till bucket 8
*/
for (i = 1; i < 10; i++)
bucket[i] = bucket[i] + bucket[i-1];
Я не понимаю, что автор делает в этом цикле. Может кто-нибудь объяснить, пожалуйста, что происходит?
И да, я использую ручку и бумагу, чтобы увидеть, что происходит. Просто подумал, что могу уточнить, что
Решение
Если вас смущает эта строка, вы можете прочитать о подсчете сортировки. Одна из важных вещей, которые нужно понять, — это не сортировка сама по себе. Существует подалгоритм, который нужно использовать, и он часто рассчитывает сортировку.
Ссылка, которую вы предоставили, не говорит об этом, и, по моему мнению, это является большой путаницей. Когда ты читаешь
«Во время первого прохода, Сортировать все данные основаны на младшем значащем бите
Это не говорит как ты сортируешь Вы можете сортировать с любой другой стабильной сортировкой, и код будет резко меняться.
Все это говорит о том, что, если это единственная линия, которую вы не понимаете, то вы получили правильную сортировку. Прочтите о подсчете сортировки, чтобы понять, как это работает, и убедитесь, что вы понимаете, почему это хороший выбор в качестве подпрограммы сортировки по основанию.
Другие решения
Эта функция принимает накопленную сумму, теперь bucket [i] содержит накопленную сумму себя и всех сегментов перед ней. Что означает комментарий, так это то, что bucket [8] == 2 будет означать, что сумма от buckets 0 до 8 = 2
Редактировать: лично я думаю http://www.youtube.com/watch?v=Nz1KZXbghj8&noredirect = 1 имеет отличное объяснение.