Я пишу код, в котором член класса, если! = -1, устанавливает свою позицию в массиве. Если значение равно == -1, используется следующий свободный индекс (диапазон которого равен 0 и длине массива). В этом обзоре меня больше интересует алгоритм, делающий его более быстрым, точным и читаемым, чем что-либо еще. несмотря на то, что я использую C #, я хотел бы сохранить его простым, C-подобным и избегать таких вещей C #, как Linq и т. д. Если есть читаемый и более быстрый способ сделать это без valueSet
флаг, было бы неплохо. Я просто добавил его, потому что после swap()
При вызове замененные элементы будут посещены дважды со значением! = -1, что приведет к повторной установке ошибочного значения. Дайте мне знать, если что-то непонятно. Ниже приведен код с некоторыми функциями, который действует как unittests. Также приветствуются различные способы сделать это.
using System.Collections.Generic;
using System.Diagnostics;
namespace sort
{
class Program
{
static void Main(string[] args)
{
t1();
t2();
t3();
t4();
}
//test case 1
static void t1()
{
var arr = new List<A>();
arr.Add(new A(-1, "a"));
arr.Add(new A(-1, "b"));
arr.Add(new A(0, "c"));
arr.Add(new A(-1, "d"));
var sortedArr = doSort(arr.ToArray());
Debug.Assert(isSorted(sortedArr));
}
// test case 2
static void t2()
{
var arr = new List<A>();
arr.Add(new A(-1, "a"));
arr.Add(new A(-1, "b"));
arr.Add(new A(-1, "c"));
arr.Add(new A(-1, "d"));
var sortedArr = doSort(arr.ToArray());
Debug.Assert(isSorted(sortedArr));
}
// test case 3
static void t3()
{
var arr = new List<A>();
arr.Add(new A(0, "a"));
arr.Add(new A(1, "b"));
arr.Add(new A(2, "c"));
arr.Add(new A(3, "d"));
var sortedArr = doSort(arr.ToArray());
Debug.Assert(isSorted(arr.ToArray()));
}
static void t4()
{
var arr = new List<A>();
arr.Add(new A(-1, "a"));
arr.Add(new A(1, "b"));
arr.Add(new A(0, "c"));
arr.Add(new A(-1, "d"));
var sortedArr = doSort(arr.ToArray());
Debug.Assert(isSorted(sortedArr));
}
// not meant to be very fast just to be used in the "unittest"
static bool isSorted(A[] arr)
{
if(arr.Length == 0)
{
return false;
}
// this make sure the values is sequential, starting with 0
// and the last value must be same value as array's length
if(arr[0].index != 0 || arr[arr.Length - 1].index != arr.Length - 1)
{
return false;
}
// we have checked already if the first and last values
// are sequential, no need to recheck here so
// we loop from 1 to arr.length - 1
for (int i = 1; i < arr.Length - 1; i++)
{
if(i + 1 > arr.Length &&
arr[i].index + 1 != arr[i + 1].index)
{
return false;
}
}
return true;
}
static A[] doSort(A[] arr)
{
for(int i = 0; i < arr.Length; i++)
{
initValue(arr, i);
}
return arr;
}
static void initValue(A[] arr, int i)
{
var e = arr[i];
if(e.valueSet)
{
return; /* nothing to do, value initialized already */
}
// initialize to current index
if(e.index == -1)
{
e.index = i;
}
// an explicit index was set, the value at i index
// must be set to the value at e.index index
else if(e.index != i)
{
swap(arr, i, e.index);
// after the swap, that element may be left
// unitialized. Do initialize now.
initValue(arr, i);
}
e.valueSet = true;
}
static void swap(A[] arr, int i, int j)
{
// swap items
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
// update indexes
arr[i].index = i;
arr[j].index = j;
}
}
class A
{
public A(int i, string s)
{
index = i;
value = s;
}
public override string ToString()
{
return string.Format("index = %d, value = %s", index, value);
}
public int index { get; set; }
public string value { get; set; }
public bool valueSet { get; set; }
}
}
1 ответ
Обзор
В ваших тестовых случаях почему бы не использовать массив напрямую (
new A[] { new A(-1, "a"), new A(-1, "b"), new A(0, "c"),... };
) вместоList<A>.ToArray()
?В части
isSorted
, ожидаете ли вы, что возвращаемое значение будетfalse
если(arr.Length == 0)
? Или же Класс ArgumentException можно использовать здесь.В
class A
, может быть DictionaryКласс можно использовать здесь. Сделайте TKey индексным иTValue
это строка.
Ключи неизменны в
Dictionary
. Код изменяет индексы.— эспот