本帖最后由 sunrise2 于 2014-7-23 23:33 编辑
堆排序
堆排序适合于数据量非常大的场合(百万数据)。
堆排序不需要大量的递归或者多维的暂存数组。
这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,
在数据量非常大的时候,可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆,最大的数据在堆顶,
然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。
- /// <summary>
- /// 堆排序
- /// </summary>
- public class HeapSort : ISort
- {
- public int[] Sort(int[] array)
- {
- if (array != null)
- {
- HeapHanle(array, array.Length);//整理了堆结构
- for (int i = array.Length - 1; i >= 0; i--)
- {
- Swap(ref array[0], ref array[i]);
- if (i > 1)
- {
- HeapToDown(array, 0, i);
- }
- }
- }
- return array;
- }
- /// <summary>
- /// 整理堆结构
- /// </summary>
- /// <param name="array"></param>
- /// <param name="length"></param>
- private static void HeapHanle(int[] array, int length)
- {
- for (int i = length / 2 - 1; i >= 0; i--)
- {
- HeapToDown(array, i, length);
- }
- }
- /// <summary>
- /// 从下往上处理
- /// </summary>
- /// <param name="array">数组</param>
- /// <param name="i">给定的节点数组索引</param>
- private static void HeapToUp(int[] array, int i)
- {
- int cur = array[i];
- int preIndex = (i - 1) / 2;
- while (i > 0 && preIndex >= 0 && cur < array[preIndex])
- {
- array[preIndex] = cur;
- i = preIndex;
- preIndex = (i - 1) / 2;
- }
- array[i] = cur;
- }
- /// <summary>
- /// 从上往下处理
- /// </summary>
- /// <param name="array">数组</param>
- /// <param name="i">给定的节点数组索引</param>
- private static void HeapToDown(int[] array, int i, int length)
- {
- int cur = array[i];
- int nextIndex = 2 * i + 1;//左孩子对应的数组索引
- while (nextIndex < length)
- {
- if (nextIndex + 1 < length)
- {
- if (array[nextIndex] > array[nextIndex + 1])
- {
- nextIndex = nextIndex + 1;//右孩子
- }
- }
- if (cur <= array[nextIndex])
- {
- break;
- }
- else//处理
- {
- array[i] = array[nextIndex];
- i = nextIndex;
- nextIndex = 2 * i + 1;
- }
- }
- array[i] = cur;
- }
- public static void Swap(ref int int1, ref int int2)
- {
- int temp = int1;
- int1 = int2;
- int2 = temp;
- }
- }
复制代码 测试代码:- class Program
- {
- public static Random re = new Random();
- static void Main(string[] args)
- {
- Stopwatch stw4 = new Stopwatch();
- Stopwatch stw5 = new Stopwatch();
- Stopwatch stw6 = new Stopwatch();
- int[] intArray4 = GetArray(int.MaxValue / 100000);
- int[] intArray5 = GetArray(int.MaxValue / 100000);
- int[] intArray6 = GetArray(int.MaxValue / 100000);
- ISort sort4 = new HeapSort();//堆排序
- stw4.Start();
- int[] result4 = sort4.Sort(intArray4);
- stw4.Stop();
- Console.WriteLine("输出排序的结果(堆排序)");
- Console.WriteLine("程序共运行时间:" + stw4.Elapsed.ToString());
- ISort sort5 = new MergeSort();//归并排序
- stw5.Start();
- int[] result5 = sort5.Sort(intArray5);
- stw5.Stop();
- Console.WriteLine("输出排序的结果(归并排序)");
- Console.WriteLine("程序共运行时间:" + stw5.Elapsed.ToString());
- ISort sort6 = new QuickSort();//快速排序
- stw6.Start();
- int[] result6 = sort6.Sort(intArray6);
- stw6.Stop();
- Console.WriteLine("输出排序的结果(快速排序)");
- Console.WriteLine("程序共运行时间:" + stw6.Elapsed.ToString());
- Console.ReadKey();
- }
- private static int[] GetArray(long _arrayLength)
- {
- long arrayLength = _arrayLength;
- //初始化数组
- int[] intArray = new int[arrayLength];
- for (int i = 0; i < arrayLength; i++)
- {
- intArray[i] = re.Next();
- }
- return intArray;
- }
- }
复制代码
|
|