三大高级排序

三大高级排序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);            }        }    }

测试代码：