Подсчет сортировки в односвязном списке C#

Question

Есть ли способ сделать счетную сортировку в односвязном списке? Я не видел ни одного примера, и довольно сложно сделать это без них. У меня есть пример этого в массиве, и я хотел бы сделать это в односвязном списке. Кто-нибудь делал это в односвязном списке?

    public static int[] CountingSortArray(int[] array)
    {
        int[] aux = new int[array.Length];

        // find the smallest and the largest value
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i] < min) min = array[i];
            else if (array[i] > max) max = array[i];
        }

        int[] counts = new int[max - min + 1];

        for (int i = 0; i < array.Length; i++)
        {
            counts[array[i] - min]++;
        }

        counts[0]--;
        for (int i = 1; i < counts.Length; i++)
        {
            counts[i] = counts[i] + counts[i - 1];
        }

        for (int i = array.Length - 1; i >= 0; i--)
        {
            aux[counts[array[i] - min]--] = array[i];
        }

        return aux;
    }

Answer 1

Пример кода больше похож на основную сортировку с основанием (max-min+1). Обычно сортировка выглядит как код ниже. Сделайте проход по списку, чтобы получить мин и макс. Сделайте второй проход, чтобы сгенерировать счет. Сделайте проход по количеству, чтобы сгенерировать новый массив на основе количества (вместо копирования данных). Пример фрагмента кода:

    for (size_t i = 0; i < array.Length; i++)
        counts[array[i]-min]++;
    size_t i = 0;
    for(size_t j = 0; j < counts.Length); j++){
        for(size_t n = counts[j]; n; n--){
            aux[i++] = j+min;
        }
    }

Answer 2

Я нашел один, который работает с массивом по адресу: http://www.geeksforgeeks.org/counting-sort/

Я думаю, что с минимальными усилиями он может быть изменен на связанный список, единственная проблема заключается в том, что вам придется в конечном итоге обходить связанный список много раз, поскольку у вас нет произвольного доступа, например.[] что делает его довольно неэффективным. Поскольку вы, кажется, нашли то же самое, что и я, прежде чем я успел закончить печатать, я думаю, что мой ответ бессмысленно. Тем не менее, мне все еще немного любопытно, где у вас проблемы.

Вот подсказка, если выяснить, с чего начать, это проблема: каждый раз, когда вы видите array[i] используется, вам сначала нужно будет пройти по связанному списку, чтобы сначала получить i-й элемент.

Редактировать: Единственная причина, по которой вам нужно было бы создать второй связанный список частот, - это если вы действительно должны работать с результирующим связанным списком. Если вам просто нужен отсортированный список значений внутри связанного списка для целей отображения, будет работать массив, содержащий частоты (я полагаю, что в то же время вы можете просто создать массив всех значений, а затем выполнить сортировку подсчета, которая у вас уже есть). Это). Я извиняюсь, если перепутал мои c, C++, C++/cx, где-то по пути (сейчас у меня нет под рукой компилятора), но это должно дать вам хорошее представление о том, как это сделать.

public static node* FindMin(node* root){  //FindMax would be nearly identical
  node* minValue = root;
  while(node->Next){
    if(node->Value < minValue->Value)
      minValue = node;
  }
  return minValue;
}
public static node* CountingSortArray(node* linklist){
  node* root = linkedlist

  node* min = FindMin(linklist);
  node* max = FindMax(linklist);

  int[] counts = new int[max->Value - min->Value + 1];

  while(root != NULL){
    counts[root->Value] += 1;
    root = root->Next;
  }

   int i = 0;
   root = linkedlist;

   while(ptr != NULL){
     if(counts[i] == 0)
       ++i;
     else{
       root->Value = i;
       --count[i];
       root = root->Next;
     }
   }
}

void push(node** head, int new_data){
  node* newNode = new node();

  newNode->Value = new_data;
  newNode->Next = (*head);
  (*head) = newNode;
}

void printList(node* root){
  while(root != NULL){
    printf(%d ", root->Value);
    root = root->Next;
  }
  printf("\n");
}

int main(void){
  node* myLinkedList = NULL;
  push(&head, 0);
  push(&head, 1);
  push(&head, 0);
  push(&head, 2);
  push(&head, 0);
  push(&head, 2);

  printList(myLinkedList);
  CountingSortArray(myLinkedList);
  printList(myLinkedList);
}