Поиск по этому блогу

пятница, 18 мая 2012 г.

Быстрая сортировка

Решил уделить больше внимание различным сортировкам на C#. Первая, которую решил осуществить  -  Quick Sort (Быстрая сортировка). Один из быстрых известных универсальных алгоритмов сортировки массивов. Суть алгоритма:
  • из массива выбирается элемент. Как правило, в качестве этого элемента берется центральный элемент массива. 
  • остальные элементы распределяются таким образом, чтобы слева  оказались все элементы, меньшие или равные опорному элементу. Элементы, большие или равные опорному элементу, помещаются справа. 
//метод сортировки
        static void Sort(int[] arr, int l, int r) 
        {
            //i и j нужны для цикла
            int i = l;
            int j = r;
            int x = arr[(l + r) / 2]; //Опорная
            //Цикл сортировка
            while(i<=j)
            {
                //Деление на меньше и больше опорного
                while (arr[i] < x) i++;
                while (arr[j] > x) j--;
                //Если i<=j:
                if (i <= j) 
                {
                    //меняем значение элемонтов
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i++;
                    j--;
                }
            }
            //Рекурсия
            if (l < j) Sort(arr, l, j);
            if (i < r) Sort(arr, i, r);
        }
        static void Main(string[] args)
        {
            int[] arr = { 255, 457, 34564, 1442, 4795, 4422, 10, 0, 1124, 3424 };
            //вывод элемонтов массива
            foreach (int ar in arr)
                Console.WriteLine(ar + " ");
            Console.WriteLine("Сортировка");
            Sort(arr, 0, arr.Length - 1);
            foreach (int ar in arr)
                Console.WriteLine(ar + " ");
            Console.ReadLine();
        }

Комментариев нет:

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