黑马程序员技术交流社区

标题: 三大排序--堆排序 [打印本页]
作者: sunrise2    时间: 2014-7-23 23:23
标题: 三大排序--堆排序
本帖最后由 sunrise2 于 2014-7-23 23:33 编辑

   堆排序
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。
这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，
在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，
然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
  1. /// <summary>
  2.     /// 堆排序
  3.     /// </summary>
  4.     public class HeapSort : ISort
  5.     {
  6.         public int[] Sort(int[] array)
  7.         {
  8.             if (array != null)
  9.             {
  10.                 HeapHanle(array, array.Length);//整理了堆结构
  11.                 for (int i = array.Length - 1; i >= 0; i--)
  12.                 {
  13.                     Swap(ref array[0], ref array[i]);
  14.                     if (i > 1)
  15.                     {
  16.                         HeapToDown(array, 0, i);
  17.                     }
  18.                 }
  19.             }
  20.             return array;
  21.         }
  22.         /// <summary>
  23.         /// 整理堆结构
  24.         /// </summary>
  25.         /// <param name="array"></param>
  26.         /// <param name="length"></param>
  27.         private static void HeapHanle(int[] array, int length)
  28.         {
  29.             for (int i = length / 2 - 1; i >= 0; i--)
  30.             {
  31.                 HeapToDown(array, i, length);
  32.             }
  33.         }
  34.         /// <summary>
  35.         /// 从下往上处理
  36.         /// </summary>
  37.         /// <param name="array">数组</param>
  38.         /// <param name="i">给定的节点数组索引</param>
  39.         private static void HeapToUp(int[] array, int i)
  40.         {
  41.             int cur = array[i];
  42.             int preIndex = (i - 1) / 2;
  43.             while (i > 0 && preIndex >= 0 && cur < array[preIndex])
  44.             {
  45.                 array[preIndex] = cur;
  46.                 i = preIndex;
  47.                 preIndex = (i - 1) / 2;
  48.             }
  49.             array[i] = cur;
  50.         }
  51.         /// <summary>
  52.         /// 从上往下处理
  53.         /// </summary>
  54.         /// <param name="array">数组</param>
  55.         /// <param name="i">给定的节点数组索引</param>
  56.         private static void HeapToDown(int[] array, int i, int length)
  57.         {
  58.             int cur = array[i];
  59.             int nextIndex = 2 * i + 1;//左孩子对应的数组索引
  60.             while (nextIndex < length)
  61.             {
  62.                 if (nextIndex + 1 < length)
  63.                 {
  64.                     if (array[nextIndex] > array[nextIndex + 1])
  65.                     {
  66.                         nextIndex = nextIndex + 1;//右孩子
  67.                     }
  68.                 }

  70.                 if (cur <= array[nextIndex])
  71.                 {
  72.                     break;
  73.                 }
  74.                 else//处理
  75.                 {
  76.                     array[i] = array[nextIndex];
  77.                     i = nextIndex;
  78.                     nextIndex = 2 * i + 1;
  79.                 }
  80.             }
  81.             array[i] = cur;
  82.         }

  84.         public static void Swap(ref int int1, ref int int2)
  85.         {
  86.             int temp = int1;
  87.             int1 = int2;
  88.             int2 = temp;
  89.         }
  90.     }
复制代码
测试代码：
  1. class Program
  2.     {
  3.         public static Random re = new Random();
  4.         static void Main(string[] args)
  5.         {
  6.             Stopwatch stw4 = new Stopwatch();
  7.             Stopwatch stw5 = new Stopwatch();
  8.             Stopwatch stw6 = new Stopwatch();

  10.             int[] intArray4 = GetArray(int.MaxValue / 100000);
  11.             int[] intArray5 = GetArray(int.MaxValue / 100000);
  12.             int[] intArray6 = GetArray(int.MaxValue / 100000);

  14.             ISort sort4 = new HeapSort();//堆排序
  15.             stw4.Start();
  16.             int[] result4 = sort4.Sort(intArray4);
  17.             stw4.Stop();
  18.             Console.WriteLine("输出排序的结果(堆排序)");
  19.             Console.WriteLine("程序共运行时间:" + stw4.Elapsed.ToString());

  21.             ISort sort5 = new MergeSort();//归并排序
  22.             stw5.Start();
  23.             int[] result5 = sort5.Sort(intArray5);
  24.             stw5.Stop();
  25.             Console.WriteLine("输出排序的结果(归并排序)");
  26.             Console.WriteLine("程序共运行时间:" + stw5.Elapsed.ToString());

  28.             ISort sort6 = new QuickSort();//快速排序
  29.             stw6.Start();
  30.             int[] result6 = sort6.Sort(intArray6);
  31.             stw6.Stop();
  32.             Console.WriteLine("输出排序的结果(快速排序)");
  33.             Console.WriteLine("程序共运行时间:" + stw6.Elapsed.ToString());

  35.             Console.ReadKey();
  36.         }

  38.         private static int[] GetArray(long _arrayLength)
  39.         {
  40.             long arrayLength = _arrayLength;

  42.             //初始化数组
  43.             int[] intArray = new int[arrayLength];

  45.             for (int i = 0; i < arrayLength; i++)
  46.             {
  47.                 intArray[i] = re.Next();
  48.             }
  49.             return intArray;
  50.         }
  51.     }
复制代码





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2