using System;

using System.Text;

namespace HuaTong.General.Utility

{

    /// <summary>

    /// 自定义排序类

    /// </summary>

    public class Sorter

    {

        /// <summary>

        /// 交换元素位置

        /// </summary>

        public static void Swap<T>(ref T[] arr, int i, int j)

        {

            T temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

        /// <summary>

        /// 冒泡排序

        /// </summary>

        public static T[] BubbleSort<T>(T[] arr) where T : IComparable

        {

            for (int i = arr.Length - ; i > ; --i)

            {

                for (int j = ; j < i; ++j)

                {

                    if (arr[j].CompareTo(arr[j + ]) > )

                    {

                        Swap(ref arr, j, j + );

                    }

                }

            }

            return arr;

        }

        /// <summary>

        /// 选择排序

        /// </summary>

        public static T[] SelectionSort<T>(T[] arr) where T : IComparable

        {

            for (int i = ; i < arr.Length; ++i)

            {

                int index = i;

                for (int j = i + ; j < arr.Length; ++j)

                {

                    if (arr[j].CompareTo(arr[index]) < ) index = j;

                }

                Swap(ref arr, i, index);

            }

            return arr;

        }

        /// <summary>

        /// 插入排序

        /// </summary>

        public static T[] InsertionSort<T>(T[] arr) where T : IComparable

        {

            for (int i = ; i < arr.Length; ++i)

            {

                int j = i;

                T value = arr[i];

                while (j >  && arr[j - ].CompareTo(value) > )

                {

                    arr[j] = arr[j - ];

                    --j;

                }

                arr[j] = value;

            }

            return arr;

        }

        /// <summary>

        /// 希尔排序

        /// </summary>

        public static T[] ShellSort<T>(T[] arr) where T : IComparable

        {

            for (int step = arr.Length >> ; step > ; step >>= )

            {

                for (int i = ; i < step; ++i)

                {

                    for (int j = i + step; j < arr.Length; j += step)

                    {

                        int k = j;

                        T value = arr[j];

                        while (k >= step && arr[k - step].CompareTo(value) > )

                        {

                            arr[k] = arr[k - step];

                            k -= step;

                        }

                        arr[k] = value;

                    }

                }

            }

            return arr;

        }

        /// <summary>

        /// 快速排序

        /// </summary>

        public static T[] QuickSort<T>(T[] arr, int startIndex, int endIndex) where T : IComparable

        {

            int i, j;

            T x, y;

            i = (startIndex <  ?  : startIndex);

            j = (endIndex > arr.Length -  ? arr.Length -  : endIndex);

            if (startIndex > endIndex) return null;

            x = arr[(i + j) / ];

            while (i <= j)

            {

                while (arr[i].CompareTo(x) <  && i < endIndex)

                {

                    i = i + ;

                }

                while (x.CompareTo(arr[j]) <  && j > startIndex)

                {

                    j = j - ;

                }

                if (i <= j)

                {

                    y = arr[i];

                    arr[i] = arr[j];

                    arr[j] = y;

                    i = i + ;

                    j = j - ;

                }

            }

            if (startIndex < j) QuickSort(arr, startIndex, j);

            if (i < endIndex) QuickSort(arr, i, endIndex);

            return arr;

        }

        /// <summary>

        /// 归并排序

        /// </summary>

        public static T[] MergeSort<T>(T[] arr, int startIndex, int endIndex, T[] arrF) where T : IComparable

        {

            startIndex = (startIndex <  ?  : startIndex);

            endIndex = (endIndex > arr.Length -  ? arr.Length -  : endIndex);

            arrF = new T[arr.Length];

            if (startIndex >= endIndex) return null;

            int m = (startIndex + endIndex) >> ;

            MergeSort(arr, startIndex, m, arrF);

            MergeSort(arr, m + , endIndex, arrF);

            for (int i = startIndex, j = startIndex, k = m + ; i <= endIndex; ++i)

            {

                arrF[i] = arr[(k > endIndex || j <= m && arr[j].CompareTo(arr[k]) < ) ? j++ : k++];

            }

            for (int i = startIndex; i <= endIndex; ++i) arr[i] = arrF[i];

            return arr;

        }

        /// <summary>

        /// 堆排序

        /// </summary>

        public static T[] HeapSort<T>(T[] arr) where T : IComparable

        {

            for (int i = ; i < arr.Length; ++i)

            {

                for (int j = i, k = (j - ) >> ; k >= ; j = k, k = (k - ) >> )

                {

                    if (arr[k].CompareTo(arr[j]) >= ) break;

                    Swap(ref arr, j, k);

                }

            }

            for (int i = arr.Length - ; i > ; --i)

            {

                Swap(ref arr, , i);

                for (int j = , k = (j + ) << ; k <= i; j = k, k = (k + ) << )

                {

                    if (k == i || arr[k].CompareTo(arr[k - ]) < ) --k;

                    if (arr[k].CompareTo(arr[j]) <= ) break;

                    Swap(ref arr, j, k);

                }

            }

            return arr;

        }

    }

}