1．堆排序思想
堆排序是一種樹形選擇排序，在排序過程中，將A[1..n]看成是完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。
2．堆的定義：n個元素的序列K1，K2，K3，…Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：Ki≤K2i ， Ki ≤K2i+1（1≤i≤n/2）
堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。例如序列{1,35,14,60,61,45,15,81}就是一個堆，它對應(yīng)的完全二叉樹如下圖1所示。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。
下面的例子用大根堆來實現(xiàn)訂單排序
思路是保持前K大有序，然后插入時候判斷，非大不插，并且插入的時候是二分查找位置，彈出最后一個
訂單結(jié)構(gòu)
public struct Order:IComparable<Order>
{
public DateTime CreateTime;
public string Name;
public decimal Total;
public int OrderDetailCount;
private static IComparer<Order> _compare;
public Order(string name,DateTime createTime,decimal total,int orderdetailCocunt)
{
Name = name;
CreateTime = createTime;
Total = total;
OrderDetailCount = orderdetailCocunt;
}
public int CompareTo(Order other)
{
return string.Compare(Name, other.Name);
}
public static IComparer<Order> SortByTime()
{
return new TimeCompare();
}
public static IComparer<Order> SortByTotal()
{
return new TotalComare();
}
public static IComparer<Order> SortByOrderDetail()
{
return new OrderDetailCompare();
}
public static bool operator >=(Order left,Order right)
{
return left.CompareTo(right)>=0;
}
public static bool operator <=(Order left, Order right)
{
return left.CompareTo(right) <= 0;
}
public static bool operator >(Order left, Order right)
{
return left.CompareTo(right) > 0;
}
public static bool operator<(Order left, Order right)
{
return left.CompareTo(right) <0;
}
}
public class TimeCompare : IComparer<Order>
{
public int Compare(Order x, Order y)
{
return x.CreateTime.CompareTo(x.CreateTime);
}
}
public class TotalComare : IComparer<Order>
{
public int Compare(Order x, Order y)
{
return x.Total.CompareTo(y.Total);
}
}
public class OrderDetailCompare : IComparer<Order>
{
public int Compare(Order x, Order y)
{
return x.OrderDetailCount.CompareTo(y.OrderDetailCount);
}
}
堆排類
public class HeapSort
{
private int heapSize = 0;
public Order[] Heap;
public int Count = 0;
IComparer<Order> SelfCompare;
public HeapSort(int size,IComparer<Order> compare)
{ heapSize = size;
Heap = new Order[size];
SelfCompare = compare;
}
public void Insert(Order iterm)
{
if (SelfCompare.Compare(iterm, Heap[heapSize - 1]) > 0)
{
Insert(iterm, 0, (Heap.Length - 1) / 2, Heap.Length - 1);
}
Count++;
}
private void Insert(Order iterm, int min, int pos, int max)
{
if ((SelfCompare.Compare(iterm, Heap[pos]) <= 0 && SelfCompare.Compare(iterm,Heap[pos + 1]) >= 0) || pos == 0)
{
for (int i = heapSize - 1; i > pos; i--)
{
Heap[i] = Heap[i - 1];
}
if (pos == 0)
{
Heap[pos] = iterm;
}
else
{
Heap[pos + 1] = iterm;
}
}
else
{
if (iterm.CompareTo(Heap[pos]) > 0)
{
max = pos;
}
else
{
min = pos;
}
pos = Convert.ToInt32((max + min) / 2);
Insert(iterm, min, pos, max);
}
}
}
測試代碼
static void Main(string[] args)
{
HeapSort mySort = new HeapSort(1000,new TimeCompare());
Random Rand = new Random();
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
for (int i = 0; i < 1000 * 1000; i++)
{
Order temporder = new Order("Product"+i, DateTime.Now.AddMinutes(Rand.Next()),i,Rand.Next());
mySort.Insert(temporder);
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
for (int i = 0; i < mySort.Heap.Length; i++)
{
Order iterm = mySort.Heap[i];
Console.WriteLine(iterm.Name);
}
Console.WriteLine("長度：" + mySort.Count + "-------------------------------");
Console.Read();
}
百萬訂單實際需要30毫秒，時間復(fù)雜度 大致可看做o(n).
