У меня есть список входных слов, разделенных запятой. Я хочу сортировать эти слова по алфавиту и по длине. Как я могу это сделать без использования встроенных функций сортировки?Как я могу отсортировать массив строк?
Хороший вопрос !! Сортировка - это, пожалуй, самая важная концепция, которую мы изучаем как перспективный ученый-компьютер.
Существует множество разных алгоритмов для сортировки списка.
Когда вы нарушаете все эти алгоритмы, самая фундаментальная операция - это сравнение двух элементов в списке, определяющих их «естественный порядок».
Например, для того, чтобы отсортировать список целых чисел, я бы нужна функция, которая говорит мне, учитывая любые два целых числа X и Y, является ли X меньше, равна или больше, чем Y.
Для ваших строк вам понадобится одно и то же: функция, которая сообщает вам, какая из строк имеет «меньшее» или «большее» значение, или же они равны.
Традиционно эта «компаратор» функция выглядит примерно так:
int CompareStrings(String a, String b) {
if (a < b)
return -1;
else if (a > b)
return 1;
else
return 0;
}
Я оставил некоторые детали (как, как вы вычисляете ли меньше или больше, чем б ключ? : итерация по символам), но это основной скелет любой функции сравнения. Он возвращает значение меньше нуля, если первый элемент меньше, а значение больше нуля, если первый элемент больше, возвращая ноль, если элементы имеют равное значение.
Но что это касается сортировки?
Маршрутизация сортировки вызовет эту функцию для пар элементов в вашем списке, используя результат функции, чтобы выяснить, как переупорядочить элементы в отсортированный список. Функция сравнения определяет «естественный порядок», а «алгоритм сортировки» определяет логику вызова и ответа на результаты функции сравнения.
Каждый алгоритм похож на стратегию большого изображения, гарантирующую правильность сортировки ЛЮБОГО ввода. Вот некоторые из алгоритмов, которые вы, вероятно, хотите знать о:
Bubble Сортировка:
перебирать список, вызывающему функцию сравнения для всех соседних пар элементов. Всякий раз, когда вы получаете результат больше нуля (это означает, что первый элемент больше второго), замените два значения. Затем переходите к следующей паре. Когда вы дойдете до конца списка, если вам не нужно было заменять ЛЮБЫЕ пары, то поздравления, список отсортирован! Если вам необходимо выполнить любые свопы, вернитесь к началу и начните. Повторите этот процесс, пока не будет больше свопов.
ПРИМЕЧАНИЕ. Обычно это не очень эффективный способ сортировки списка, поскольку в худших случаях может потребоваться отсканировать весь список целых N раз, для списка с N элементами.
Merge Сортировка:
Это один из самых популярных алгоритмов разделяй и властвуй для сортировки списка. Основная идея состоит в том, что если у вас есть два уже отсортированных списка, их легко слить. Просто начните с начала каждого списка и удалите первый элемент, в котором список имеет наименьшее начальное значение. Повторяйте этот процесс до тех пор, пока вы не будете использовать все элементы из обоих списков, а затем все готово!
1 4 8 10
2 5 7 9
------------ becomes ------------>
1 2 4 5 7 8 9 10
Но что, если у вас нет двух отсортированных списков? Что делать, если у вас есть только один список, а его элементы в случайном порядке?
Это умная вещь о сортировке слияния. Вы можете разбить любой отдельный список на более мелкие фрагменты, каждый из которых является либо несортированным списком, либо отсортированным списком, либо одним элементом (который, если вы это знаете, на самом деле является отсортированным списком с длиной = 1).
Итак, первый шаг в алгоритме сортировки слияния состоит в том, чтобы разделить общий список на более мелкие и мелкие списки, на самых маленьких уровнях (где каждый список содержит только один или два элемента), их очень легко сортировать. И после сортировки легко объединить любые два смежных отсортированных списка в более крупный отсортированный список, содержащий все элементы двух подписок.
ПРИМЕЧАНИЕ: Этот алгоритм много лучше, чем метод пузырьковой сортировки, описанной выше, с точки зрения его эффективности в худшем случае-сценария. Я не буду вдаваться в подробное объяснение (которое включает в себя довольно довольно тривиальную математику, но потребуется некоторое время для объяснения), но быстрым основанием для повышения эффективности является то, что этот алгоритм разбивает свою проблему на куски идеального размера, а затем объединяет результаты этих кусков. Алгоритм сортировки пузыря решает все сразу, поэтому он не получает выгоду от «деления и покорения».
Это лишь два алгоритма для сортировки списка, но есть много других интересных методов, каждый из которых обладает своими преимуществами и недостатками: Quick Sort, Radix Сортировка, выбор сортировки, Heap Сортировка, Сортировка Шелла, и сортировка ковша.
Интернет переполнен интересной информацией о сортировке. Вот хорошее место, чтобы начать:
Существует целая область исследований, построенная вокруг sorting algorithms. Вы можете выбрать простой и реализовать его.
Несмотря на то, что это не будет самым результативным, вам не нужно слишком долго выполнять bubble sort.
Создайте консольное приложение и вставьте его в Program.cs как тело класса.
public static void Main(string[] args)
{
string [] strList = "a,b,c,d,e,f,a,a,b".Split(new [] { ',' }, StringSplitOptions.RemoveEmptyEntries);
foreach(string s in strList.Sort())
Console.WriteLine(s);
}
public static string [] Sort(this string [] strList)
{
return strList.OrderBy(i => i).ToArray();
}
Обратите внимание, что я использую встроенный метод, OrderBy. Как указывают другие ответы, существует много разных алгоритмов сортировки, которые вы могли бы реализовать там, и я думаю, что мой фрагмент кода делает все для вас, кроме фактического алгоритма сортировки.
Если вы не хотите использовать встроенный-функции, вы должны создать по вашей собственной личности. Я бы порекомендовал Bubble sort или какой-то подобный алгоритм. Сорт Bubble не является эффективным алгоритмом, но он выполняет выполненные работы и его легко понять.
Вы найдете много хорошего чтения на wikipedia.
Я бы порекомендовал сделать wiki для быстрой сортировки.
Не знаете, почему вы не хотите использовать встроенную сортировку?
пузырь сортировка повреждает мозг.
Вставка сортировки по крайней мере так же проста для понимания и кодирования, и фактически практична (для очень маленьких наборов данных и почти сортированных данных). Он работает следующим образом:
Предположим, что первые n элементов уже в порядке (вы можете начать с n = 1, так как, очевидно, одна вещь сама по себе «находится в правильном порядке»).
Возьмите (n + 1)-й элемент в своем массиве. Назовите это «pivot». Начиная с n-го элемента и спускающегося вниз:
- если он больше шарнира, переместите его на одно место справа (чтобы создать «пробел» слева от него).
- в противном случае оставьте его на месте, поставьте «поворот» на одно место справа от него (то есть, в «пробеле», если вы что-то перемещаете, или где оно началось, если вы ничего не двигаете), и остановите ,
Теперь первые n + 1 элементов в массиве в порядке, потому что стержень справа от всего меньшего, чем он, и слева от всего большего, чем он. Поскольку вы начали с n пунктов в порядке, это прогресс.
Повторите, с шагом n на 1 на каждом шаге, пока вы не обработаете весь список.
Это соответствует одному из способов, по которому вы можете физически помещать ряд папок в шкаф для хранения в порядке: вставьте его; затем поставьте другой в правильное положение, нажав все, что принадлежит ему, одним пространством, чтобы освободить место; повторить до конца. Никто никогда не сортирует физические объекты по форме пузыря, поэтому для меня это загадка, почему это считается «простым».
Все, что осталось сейчас, это то, что вам нужно иметь возможность работать, учитывая две строки, будь то первая больше второй. Я не совсем уверен, что вы подразумеваете под «алфавитом и длиной»: алфавитный порядок выполняется путем сравнения одного символа за раз от каждой строки. Если это не так, это ваш заказ. Если они одинаковы, посмотрите на следующий, если только вы не попали в символы в одной из строк, и в этом случае это «меньше».
Использование NSort
Я перебежал NSort библиотеке пару лет назад в книге Windows Developer Power Tools. Библиотека NSort реализует ряд алгоритмов сортировки. Главное преимущество использования чего-то вроде NSort над написанием собственной сортировки - это то, что уже проверено и оптимизировано.
Проводка ссылку на быстро строки кода сортировки в C#:
http://www.codeproject.com/KB/cs/fast_string_sort.aspx
Еще один момент: Предложенное компаратор выше не рекомендуется для неанглийских языков:
Int CompareStrings (String а, Строка b) {
if (a < b) return -1;
else if (a> b)
возвращение 1; else
return 0; }
Checkout ссылку для языка рода неанглийской:
http://msdn.microsoft.com/en-us/goglobal/bb688122
И как уже упоминалось, использование nsort для действительно гигантских массивов, которые не помещаются в памяти.
Как бы вы хотели, чтобы их отсортировали? В алфавитном порядке? По длине строки? Или что еще? – victoriah 2008-11-29 19:15:18
в алфавитном порядке и по длине – 2008-11-29 19:22:52
Почему (кроме домашней работы) вы хотели бы сделать это без использования каких-либо встроенных функций? – 2008-11-29 19:25:24