VPF::Как обойтись без указателей - Форум программистов

6atoh

Дата 18.9.2006, 02:01 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 160
Регистрация: 15.9.2006
Где: Minsk

Репутация: 2
Всего: 4

Взял алгоритм быстрой сортировки с http://algolist.manual.ru/sort/quick_sort.php
Вот он собственно:

Код


template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.

  long i = 0, j = N; // поставить указатели на исходные места
  T temp, p;

  p = a[ N>>1 ];// центральный элемент

  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;

    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );


  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}

Как организовать такой алгоритм на С#? Я имею ввиду 24-ю строку...выражение a+i. В моем случае a это массив byte[]

Exception

Дата 18.9.2006, 15:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 4525
Регистрация: 26.12.2004

Репутация: 29
Всего: 186

Реализация алгоритма Quick Sort на C#.

Код


using System;
using System.Text;

public class QuickSort
{

    public delegate bool Compare<T>(T rhs, T lhs);

    public static void QuickSort<T>(ref T[] values, Compare<T> comp)
    {
        QuickSortRecurse(ref values, 0, values.Length, comp);
    }

    public static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    public static string PrintArray<T>(T[] values, int start, int end)
    {
        StringBuilder builder = new StringBuilder();
        for (int i = start; i < end; i++)
        {
            builder.Append(values[i].ToString());
            builder.Append(" ");
        }
        return builder.ToString();
    }

    public static void QuickSortRecurse<T>(ref T[] values, 
           int start, int end, Compare<T> comp)
    {
        if ((end - start) < 2) return;
        if (((end - start) == 2)) 
        {
            if (!comp(values[start], values[end - 1]))
            {
                Swap(ref values[start], ref values[end-1]);
            }
            return;
        }
        int stop = end - 1;
        int i = start + 1;
        while (i < stop)
        {
            while (!comp(values[start], values[i]) && i < stop) i++;
            while (comp(values[start], values[stop]) && stop >= i) stop--;
            if (i < stop)
            {
                Swap(ref values[i], ref values[stop]);
            }
        }
        if (start < stop)
        {
            Swap(ref values[start], ref values[stop]);
        }
        if (start < stop-1)
            QuickSortRecurse(ref values, start, stop, comp);
        if (stop+1 < end)
            QuickSortRecurse(ref values, stop + 1, end, comp);
    }
}

Использование:

Код


public class Test
{

    public static void Main()
    {
        Random r = new Random();
        int[] stuff = new int[10];
        // Заполняем масссив случайными числами
        for (int i = 0; i < stuff.Length; i++)
            stuff[i] = r.Next(10);
        // Сортируем по возрастанию
        QuickSort(ref stuff, delegate (int rhs, int lhs) {return rhs <= lhs; });
        // Выводим на консоль
        foreach(int element in stuff) Console.WriteLine(element);
    }

}

6atoh

Дата 18.9.2006, 21:02 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 160
Регистрация: 15.9.2006
Где: Minsk

Репутация: 2
Всего: 4

Огромное спасибо Exception

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »