2012-06-26 16:22 yuejianjun 阅读(201) 评论() 收藏 举报
ObjectScore[] obj = ObjectScoreArray.GetObjectScoreArray();
ScoreSort.TopSort(obj, 5, new ObjectScoreComparer());
obj 前5个最小
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Test
{
class ScoreSort
{
public static void TopSort(ObjectScore[] array, int top, ObjectScoreComparer comparer)
{
//Judge input
if (array.Length <= 2 || top >= array.Length / 2)
{
Array.Sort(array);
return;
}
//One time partition
int pivot = PartitionInt(array, 0, array.Length - 1, array.Length / 2);
int lastPivot = pivot;
//Run until pivot near the top
while ((!(lastPivot >= top && pivot <= top)))
{
lastPivot = pivot;
if (pivot > top)
{
pivot = PartitionInt(array, 0, pivot, pivot / 2);
if (pivot == lastPivot)
{
pivot--;
}
}
else
{
if (pivot >= array.Length - 1)
{
lastPivot = array.Length - 1;
break;
}
pivot = PartitionInt(array, pivot + 1, array.Length - 1, (array.Length - pivot) / 2);
}
}
//Finally sort
if (lastPivot < array.Length)
{
Array.Sort(array, 0, lastPivot + 1, comparer);//前lastPivot + 1行是最小的，但他们顺序没排好，最后对前lastPivot + 1个进行排序
}
else
{
Array.Sort(array, 0, lastPivot, comparer);
}
}
private static int PartitionInt(ObjectScore[] array, int low, int high, int pivotIndex )
{
ObjectScore pivotValue = array[pivotIndex];
array[pivotIndex] = array[low];
array[low] = pivotValue;
while (low < high)
{
while (array[high].Score >= pivotValue.Score && high > low)
{
--high;
}
if (high > low)
{
array[low] = array[high];
}
while (array[low].Score <= pivotValue.Score && high > low)
{
++low;
}
if (high > low)
{
array[high] = array[low];
}
}
array[low] = pivotValue;
return low;
}
}
public class ObjectScore
{
public int ID { get; set; }
public float Score { get; set; }
}
public class ObjectScoreComparer : IComparer<ObjectScore>
{
public int Compare(ObjectScore x, ObjectScore y)
{
return x.Score.CompareTo(y.Score);
}
}
public class ObjectScoreArray
{
/// <summary>
/// 初始化数据集
/// </summary>
/// <returns></returns>
public static ObjectScore[] GetObjectScoreArray()
{
List<ObjectScore> testValues = new List<ObjectScore>();
Random rand = new Random();
int count = 500000;
for (int i = 0; i < count; i++)
{
ObjectScore obj = new ObjectScore();
obj.ID = i;
obj.Score =float .Parse ( (rand.Next(3,1000) /4).ToString ());
testValues.Add(obj);
}
ObjectScore[] testArr = new ObjectScore[testValues.Count];
testValues.CopyTo(testArr);
return testArr;
}
}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。