三大高级排序

三大高级排序
1、堆排序
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。
这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，
在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，
然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

/// <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;
        }
    }

2、归并排序
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，
当分解到只有1个一组的时候，就可以排序这些分组，
然后依次合并回原来的序列中，这样就可以排序所有数据。
合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，
因为它需要一个额外的数组。

/// <summary>
    /// 归并排序
    /// </summary>
    public class MergeSort : ISort
    {
        public int[] Sort(int[] array)
        {
            if (array != null)
            {
                int[] temp = new int[array.Length];
                SortLeftAndRight(array, 0, array.Length - 1, temp);
            }
            return array;
        }
        /// <summary>
        /// 对array[first]-array[middle]和array[middle+1]-array[last]进行并归
        /// </summary>
        /// <param name="array"></param>
        /// <param name="first"></param>
        /// <param name="middle"></param>
        /// <param name="last"></param>
        /// <param name="temp"></param>
        private void Merge(int[] array, int first, int middle, int last, int[] temp)
        {
            int i = first;
            int n = middle;
            int j = middle + 1;
            int m = last;
            int k = 0;
            while (i <= n && j <= m)
            {
                if (array[i] <= array[j])
                {
                    temp[k++] = array[i++];
                }
                else
                {
                    temp[k++] = array[j++];
                }
            }
            while (i <= n)
            {
                temp[k++] = array[i++];
            }
            while (j <= m)
            {
                temp[k++] = array[j++];
            }
            for (i = 0; i < k; i++)
            {
                array[first + i] = temp[i];
            }
        }

        /// <summary>
        /// 递归分治
        /// </summary>
        /// <param name="array"></param>
        /// <param name="first"></param>
        /// <param name="last"></param>
        /// <param name="temp"></param>
        private void SortLeftAndRight(int[] array, int first, int last, int[] temp)
        {
            if (first < last)
            {
                int middle = (first + last) / 2;
                SortLeftAndRight(array, first, middle, temp);
                SortLeftAndRight(array, middle + 1, last, temp);
                Merge(array, first, middle, last, temp);
            }
        }

    }

3、快速排序
快速排序是一个就地排序，分而治之，大规模递归的算法。
从本质上来说，它是归并排序的就地版本。
快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，
但是就通常情况而言，没有比它更快的了。
快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。

/// <summary>
    /// 快速排序
    /// </summary>
    public class QuickSort : ISort
    {
        public int[] Sort(int[] array)
        {
            if (array != null)
            {
                int[] temp = new int[array.Length];
                QuickSorting(array, 0, array.Length - 1);
            }
            return array;
        }
        private static void QuickSorting(int[] array, int l, int r)
        {
            if (l < r)
            {
                int i = l;
                int j = r;
                int temp = array[i];
                while (i < j)
                {
                    while (i < j && array[j] >= temp)
                    {
                        j--;
                    }
                    if (i < j)
                    {
                        array[i++] = array[j];
                    }

                    while (i < j && array[i] < temp)
                    {
                        i++;
                    }
                    if (i < j)
                    {
                        array[j--] = array[i];
                    }
                }
                array[i] = temp;

                QuickSorting(array, l, i - 1);
                QuickSorting(array, i + 1, r);
            }
        }
    }

测试代码：

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;
        }
    }

测试结果截图：