Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »
реклама
Качественная накрутка лайков вконтакте на сайте http://bosslike.ru/.

Почтовая рассылка

Подписчиков: 11829
Последний выпуск: 19.06.2015

Быстрая сортировка на C#

Автор: Трубецкой Алексей

Пошаговое описание алгоритма

  1. Из массива выбирается элемент a[i]. Как правило, в качестве этого элемента берется центральный элемент массива.
  2. Остальные элементы распределяются таким образом, чтобы слева от a[i] оказались все элементы, меньшие или равные a[i]. Элементы, большие или равные a[i], помещаются справа. В результате массив будет выглядеть так:
  3. Производится проверка количества элементов в левой и правой частях массива. Если какая-либо часть (или обе части) содержит более двух элементов, то для этой части (или частей) запускается та же процедура сортировки с помощью рекурсивного вызова.

Реализация на C#

Класс QuickSorting, содержащий функцию быстрой сортировки, и класс Test для тестирования этой функции:

class QuickSorting {
   public static void sorting(double[] arr, long first, long last) {
      double p = arr[(last - first)/2 + first];
      double temp;
      long i = first, j = last;
      while(i  p && j >= first) --j;
            if(i  first) sorting(arr, first, j);
      if(i  key");
      System.Console.ReadLine();
   }
}

Смотрие также

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
31K
06 сентября 2007 года
homa.andy
6 / / 06.09.2007
Мне нравитсяМне не нравится
7 апреля 2011, 15:43:03
Я уже молчу про строчку 4 (как пронумеровано выше). Ну зачем же делать перестановку, если i == j?
2.
31K
06 сентября 2007 года
homa.andy
6 / / 06.09.2007
Мне нравитсяМне не нравится
7 апреля 2011, 15:29:43
А теперь попробуйте заполнить массив одинаковыми числами и посмотрите, что делает ваш цикл:

Код:
while(i <= j) {

  while(arr[ i ] < p && i <= last)  ++i;

  while(arr[ j ] > p && j >= first) --j;

    if(i <= j) {

         temp = arr[ i ];

         arr[ i ] = arr[ j ];

         arr[ j ] = temp;

         ++i; --j;

       }

  }

Строки 2 и 3 не выполняются (там строгое неравенство), поэтому всегда срабатывает перестановка. ВСЕГДА!!!

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

В общем, КГ/АМ, уж извините.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог