Проблема с сортировкой
Пишу программу на C# и у меня возникла проблема с сортировкой списка. Как проиндексировать список для сортировки методом вставки.
Исходный код программы:
Сортировать данным алгоритмом:
Исходный код программы:
Код:
public class ElList
{
public int K;
public ElList L;
public ElList() : base() { }
public ElList(int K, ElList L = null)
{
this.K = K;
this.L = L;
}
public override string ToString()
{
return K + "\r\n";
}
}
public class MyList
{
public ElList El;
public MyList ()
{
El = new ElList();
El = null;
}
public void Add(int d)
{
ElList P;
if(El==null)
P = new ElList(d);
else
P = new ElList(d,El);
El = P;
}
public void ShowList(ref TextBox txtBox)
{
txtBox.Clear();
ElList P = El;
do{
txtBox.AppendText(P.ToString());
P = P.L;
} while(P!=null);
}
}
{
public int K;
public ElList L;
public ElList() : base() { }
public ElList(int K, ElList L = null)
{
this.K = K;
this.L = L;
}
public override string ToString()
{
return K + "\r\n";
}
}
public class MyList
{
public ElList El;
public MyList ()
{
El = new ElList();
El = null;
}
public void Add(int d)
{
ElList P;
if(El==null)
P = new ElList(d);
else
P = new ElList(d,El);
El = P;
}
public void ShowList(ref TextBox txtBox)
{
txtBox.Clear();
ElList P = El;
do{
txtBox.AppendText(P.ToString());
P = P.L;
} while(P!=null);
}
}
Вставки в список (Алгоритм L с.120 Кнут)
Предполагается, что записи R1, R2, ..., RN содержат ключи K1, K2, ..., KN и поля "связи" L1, L2, ..., LN, в которых могут храниться числа от 0 до N; имеется также еще одно поле связи L0 в некоторой искусственной записи R0 в начале файла. Алгоритм устанавливает поля связи так, что записи оказываются связанными в возрастающем порядке. Так, если p(1)...p(N)-"устойчивая" переустановка, такая, что Kp(1) ≤ ... ≤ Kp(N) ,то в результате применения алгоритма получим L0=p(1); Lp(i)=p(i+1) 1 ≤ i < N; Lp(N)=0.
L1: [Цикл по j]
Установить L0=N, LN=0.( L0 служит "головой" списка, а 0-пустой связью; следовательно, список, по существу, циклический.) Выполнить шаги от L2 до L5 при J=N-1,N-2,...,1 и завершить работу алгоритма.
L2: [Установить p, q, K]
Установить p= L0, q=0, K=Kj (в последующих шагах мы вставим запись Rj в нужное место в связанном списке путем сравнения ключа K с предыдущими ключами в возрастающем порядке. Переменные p и q служат указателями на текущее место в списке, причем p=Lq, так что q всегда на один шаг отстает от p.
L3: [Сравнить K и Kp]
Если K ≤ Kp, то перейти к шагу L5. (Мы нашли искомое положение записи R в списке между Rq и Rp.)
L4: [Продвинуть p, q]
Установить q=p, p=Lq. Если p>0, то возвратиться к шагу L3. (Если p=0, то K - наибольший ключ, обнаруженный до сих пор; следовательно запись R должна попасть в конец списка, между Rq и R0.)
L5: [Вставить в список]
Установить Lq=j, Lj=p
Предполагается, что записи R1, R2, ..., RN содержат ключи K1, K2, ..., KN и поля "связи" L1, L2, ..., LN, в которых могут храниться числа от 0 до N; имеется также еще одно поле связи L0 в некоторой искусственной записи R0 в начале файла. Алгоритм устанавливает поля связи так, что записи оказываются связанными в возрастающем порядке. Так, если p(1)...p(N)-"устойчивая" переустановка, такая, что Kp(1) ≤ ... ≤ Kp(N) ,то в результате применения алгоритма получим L0=p(1); Lp(i)=p(i+1) 1 ≤ i < N; Lp(N)=0.
L1: [Цикл по j]
Установить L0=N, LN=0.( L0 служит "головой" списка, а 0-пустой связью; следовательно, список, по существу, циклический.) Выполнить шаги от L2 до L5 при J=N-1,N-2,...,1 и завершить работу алгоритма.
L2: [Установить p, q, K]
Установить p= L0, q=0, K=Kj (в последующих шагах мы вставим запись Rj в нужное место в связанном списке путем сравнения ключа K с предыдущими ключами в возрастающем порядке. Переменные p и q служат указателями на текущее место в списке, причем p=Lq, так что q всегда на один шаг отстает от p.
L3: [Сравнить K и Kp]
Если K ≤ Kp, то перейти к шагу L5. (Мы нашли искомое положение записи R в списке между Rq и Rp.)
L4: [Продвинуть p, q]
Установить q=p, p=Lq. Если p>0, то возвратиться к шагу L3. (Если p=0, то K - наибольший ключ, обнаруженный до сих пор; следовательно запись R должна попасть в конец списка, между Rq и R0.)
L5: [Вставить в список]
Установить Lq=j, Lj=p
П.С. Сильно не ругать т.к. возможно я думаю не в том направлении...
Никак. Индексированный список — это уже ассоциативный массив. Список может хранить только какой-то объект, вернее, ненумерованное множество объектов. Но никто не мешает помещать в него объекты вида {индекс:данные}.
Вообще, тебе не нужны индексы для сортировки вставками, которые принадлежали бы классу списка. Индекса for будет достаточно.
Топорная реализация сортировка вставками сишарп C# скачать без смс бесплатно .cs Insertion sort студентам.
Код:
static List<int> Sort(List<int> lst)
{
int len = lst.Count - 1;
int j = 0;
if (len < 1)
return lst;
for (int i = 1; i <= len; ++i)
{
int key = lst[i];
j = i - 1;
while (j >= 0 && lst[j] > key)
{
lst[j + 1] = lst[j];
j--;
}
lst[j + 1] = key;
}
return lst;
}
static void Main(string[] args)
{
int[] x = { 5, 7, 9, 1, 3, 4, 8 };
foreach (int num in Sort(x.ToList<int>()))
Console.Write(num + " ");
Console.ReadKey();
}
{
int len = lst.Count - 1;
int j = 0;
if (len < 1)
return lst;
for (int i = 1; i <= len; ++i)
{
int key = lst[i];
j = i - 1;
while (j >= 0 && lst[j] > key)
{
lst[j + 1] = lst[j];
j--;
}
lst[j + 1] = key;
}
return lst;
}
static void Main(string[] args)
{
int[] x = { 5, 7, 9, 1, 3, 4, 8 };
foreach (int num in Sort(x.ToList<int>()))
Console.Write(num + " ");
Console.ReadKey();
}