算法笔记(排序算法)

比较常见的比较排序有插入排序，选择排序，冒泡排序，合并排序，快速排序，堆排序等方法，这些排序的期望时间T(n)>O(nlgn).线性排序的方法有计数排序，基数排序，桶排序。排序方法的选择应该考虑几个比较重要的特性：时间复杂度，空间复杂度，稳定性，常数因子，算法实现难度，输入依赖性等。综合这些因素来讲，在实际应用中，线性排序未必就比比较排序要好。
下面是常见的排序实现（计数排序和快速排序可参见前面的博文）:

  public class MySort
    {
        #region 插入排序
        /// <summary>
        /// 插入排序算法
        /// 原地置换：是
        /// 平均性能：O(n^2)
        /// 最好性能O(n)：已符合目标排序；
        /// 最坏情况O(n^2)：目标排序的倒排；
        /// </summary>
        /// <param name="Source">待排数组</param>
        public static void InsertionSort(int[] Source)
        {
            int theLength = Source.Length;
            //从第2个开始，将当前数插入到0..i-1数组中去.
            for (int i = 1; i < theLength; i++)
            {
                int theCurrVal = Source[i];
                int j = i - 1;
                //找到插入位置，并后移元素.
                while (j>=0 && theCurrVal < Source[j])
                {
                    Source[j + 1] = Source[j];
                    j--;
                }
                Source[j + 1] = theCurrVal;
            }
        }
        #endregion
        #region  合并排序.
        /// <summary>
        /// 归并排序
        /// 性能：O(nlog(n))，很稳定，不依赖于输入
        /// 原地置换：非原地置换排序，需要O(n)辅助空间.
        /// 稳定性：稳定的.
        /// </summary>
        /// <param name="Source">待排序数组</param>
        /// <param name="Start">开始位置</param>
        /// <param name="End">结束位置</param>
        public static void MergeSort(int[] Source, int Start, int End)
        {
            if (Start + 1 == End)
            {
                if (Source[Start] > Source[End])
                {
                    int theTmp = Source[End];
                    Source[End] = Source[Start];
                    Source[Start] = theTmp;
                }
                return;
            }
            if (Start == End)
            {
                return;
            }
            int theCenter = (Start + End) / 2;
            MergeSort(Source, Start, theCenter);
            MergeSort(Source, theCenter + 1, End);
            MergeArray(Source, Start, theCenter, theCenter + 1, End);
        }
        /// <summary>
        /// 归并两组.
        /// </summary>
        /// <param name="Source">源数组</param>
        /// <param name="S1">数组1开始索引</param>
        /// <param name="E1">数组1结束索引</param>
        /// <param name="S2">数组2开始索引</param>
        /// <param name="E2">数组2结束索引</param>
        private static void MergeArray(int[] Source, int S1, int E1, int S2, int E2)
        {
            int theLen = E2 - S1 + 1;
            int[] theTemp = new int[theLen];
            int i = S1;
            int j = S2;
            int k=0;
            while (i <= E1 && j <= E2)
            {
                if (Source[i] < Source[j])
                {
                    theTemp[k] = Source[i];
                    i++;
                }
                else
                {
                    theTemp[k] = Source[j];
                    j++;
                }
                k++;
            }
            while (i <= E1)
            {
                theTemp[k] = Source[i];
                i++;
                k++;
            }
            while (j <= E2)
            {
                theTemp[k] = Source[j];
                j++;
                k++;
            }
            for (i = 0; i < theLen; i++)
            {
                Source[S1 + i] = theTemp[i];
            }
        }
        #endregion
        #region 堆排序
        /// <summary>
        /// 堆排序：
        /// 平均性能：O(n*lgn)，性能依赖于输入，性能最好是输入倒序排列（最大堆，目标为升序)
        /// 稳定性：不稳定；
        /// 原地置换：原地置换排序；
        /// </summary>
        /// <param name="A"></param>
        public static void HeapSort(int[] A)
        {
            //建堆O(n)
            HeapBuilder(A);
            int theHeapSize = A.Length;
            //循环取当前堆的最大值,并整理剩余堆
            //O(n*lgn)
            for (int i = A.Length-1; i > 0; i--)
            {
                int theTmp = A[0];
                A[0] = A[i];
                A[i] = theTmp;
                theHeapSize--;
                HeapMax(A, 0, theHeapSize);
            }
        }
        /// <summary>
        /// 取当前节点的左儿子
        /// </summary>
        /// <param name="i">当前节点索引</param>
        /// <returns>左儿子节点索引</returns>
        private static int HeapL(int i)
        {
            return i * 2 + 1;
        }
        /// <summary>
        /// 取当前节点的右儿子
        /// </summary>
        /// <param name="i">当前节点索引</param>
        /// <returns>右儿子节点索引</returns>
        private static int HeapR(int i)
        {
            return i * 2 + 2;
        }
        /// <summary>
        /// 取当前节点的父节点索引
        /// </summary>
        /// <param name="i">当前节点索引</param>
        /// <returns>父节点索引</returns>
        private static int HeapP(int i)
        {
            return (i + 1) / 2 - 1;
        }
        /// <summary>
        /// 向下调整指定节点的，使得当前堆保持最大堆性质。最多调整lgn次.
        /// </summary>
        /// <param name="A">要调整的堆数组</param>
        /// <param name="i">要调整的节点</param>
        /// <param name="HeapSize">堆大小</param>
        private static void HeapMax(int[] A, int i, int HeapSize)
        {
            int theL = HeapL(i);
            int theR = HeapR(i);
            int thelargest = i;
            if (theL < HeapSize && A[theL] > A[thelargest])
            {
                thelargest = theL;
            }
            if (theR < HeapSize && A[theR] > A[thelargest])
            {
                thelargest = theR;
            }
            if (thelargest != i)
            {
                int theTmp = A[i];
                A[i] = A[thelargest];
                A[thelargest] = theTmp;
                HeapMax(A, thelargest, HeapSize);
            }
        }
        /// <summary>
        /// 构建最大堆
        /// </summary>
        /// <param name="A">待排序数组</param>
        private static void HeapBuilder(int[] A)
        {
            int theHeapSize = A.Length;
            //满2叉树的性质，内节点数2^(H)-1,外节点数:2^H (H为树的高度)
            int theP = A.Length / 2 - 1;
            for (int i = theP; i >= 0; i--)
            {
                HeapMax(A,i,theHeapSize);
            }
        }
        #endregion
        #region 桶排序
        /// <summary>
        /// 桶排序：
        /// 性能：桶排序的期望时间为O(n),最坏时间为O(n^2).桶排序的性能依赖于输入序列的分布情况
        /// 如果重复元素或者分布不均匀的情况下，桶排序就不太适合.另外桶排序需要O(n)额外存储空间。
        /// 原地置换：非原地置换排序.
        /// 稳定性：桶排序的稳定性依赖于桶内排序算法。
        /// </summary>
        /// <param name="A"></param>
        public static void BucketSort(double[] A)
        {
            //double theMax = double.MinValue;   
            //for (int i = 0; i < A.Length; i++)
            //{
            //    if (theMax < A[i])
            //    {
            //        theMax = A[i];
            //    }
            //}
            int theLength = A.Length;
            //准备桶.O(n)
            List<List<double>> theBuckets = new List<List<double>>();
            for (int i = 0; i < theLength; i++)
            {
                theBuckets.Add(new List<double>());
            }
            //分桶O(n)
            for (int i = 0; i < theLength; i++)
            {
                int theIndex =Convert.ToInt32(Math.Floor(A[i] * theLength));
                theBuckets[theIndex].Add(A[i]);
            }
            //桶内排序期望：O(n)，如果分布均衡，则每个桶的元素都在个位数的情况下，
            //总的桶内排序时间可认为是线性的。
            for (int i = 0; i < theLength; i++)
            {
                InsertionSort(theBuckets[i]);
            }
            //桶合并.O(n)
            int theCurrIndex = 0;
            for (int i = 0; i < theLength; i++)
            {
                for (int j = 0; j < theBuckets[i].Count; j++)
                {
                    A[theCurrIndex] = theBuckets[i][j];
                    theCurrIndex++;
                }
                theBuckets[i].Clear();
            }
            theBuckets.Clear();
        }
        /// <summary>
        /// 插入排序算法,原地置换排序,O(n^2)
        /// </summary>
        /// <param name="Source">待排数组</param>
        private static void InsertionSort(List<double> Source)
        {
            int theLength = Source.Count;
            //从第2个开始，将当前数插入到0..i-1数组中去.
            for (int i = 1; i < theLength; i++)
            {
                double theCurrVal = Source[i];
                int j = i - 1;
                //找到插入位置，并后移元素.
                while (j >= 0 && theCurrVal < Source[j])
                {
                    Source[j + 1] = Source[j];
                    j--;
                }
                Source[j + 1] = theCurrVal;
            }
        }
        #endregion
    }