三大高級排序

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

測試代碼：