Ответ 1
OK. Вот что я хотел бы попробовать на основе того, что вы сказали в ответ на мой комментарий.
Я хочу сказать "4-6" и получить что-то вроде: 3, 2, 1 (несортированный, но все меньше, чем правильный 4-й элемент); 4, 5, 6 (отсортировано и в том же месте они будут для отсортированного списка); 8, 7, 9 (несортированный, но все больше, чем правильный 6-й элемент).
Давайте добавим 10 к нашему списку, чтобы упростить его: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
Итак, что вы можете сделать, это использовать алгоритм быстрого выбора, чтобы найти я th и k th. В вашем случае выше я равно 4, а k равно 6. Это, конечно, вернет значения 4 и 6. Это займет два прохода через ваш список. Итак, до сих пор среда исполнения O (2n) = O (n). Разумеется, следующая часть проста. У нас есть нижняя и верхняя границы данных, о которых мы заботимся. Все, что нам нужно сделать, это сделать еще один проход через наш список, ища любой элемент, который находится между нашими верхними и нижними границами. Если мы найдем такой элемент, мы переместим его в новый список. Наконец, мы сортируем наш List, который содержит только я th через k th элементы, которые нас волнуют.
Итак, я считаю, что общая продолжительность выполнения заканчивается O (N) + O ((k-i) lg (k-i))
static void Main(string[] args) {
//create an array of 10 million items that are randomly ordered
var list = Enumerable.Range(1, 10000000).OrderBy(x => Guid.NewGuid()).ToList();
var sw = Stopwatch.StartNew();
var slowOrder = list.OrderBy(x => x).Skip(10).Take(10).ToList();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
//Took ~8 seconds on my machine
sw.Restart();
var smallVal = Quickselect(list, 11);
var largeVal = Quickselect(list, 20);
var elements = list.Where(el => el >= smallVal && el <= largeVal).OrderBy(el => el);
Console.WriteLine(sw.ElapsedMilliseconds);
//Took ~1 second on my machine
}
public static T Quickselect<T>(IList<T> list , int k) where T : IComparable {
Random rand = new Random();
int r = rand.Next(0, list.Count);
T pivot = list[r];
List<T> smaller = new List<T>();
List<T> larger = new List<T>();
foreach (T element in list) {
var comparison = element.CompareTo(pivot);
if (comparison == -1) {
smaller.Add(element);
}
else if (comparison == 1) {
larger.Add(element);
}
}
if (k <= smaller.Count) {
return Quickselect(smaller, k);
}
else if (k > list.Count - larger.Count) {
return Quickselect(larger, k - (list.Count - larger.Count));
}
else {
return pivot;
}
}