/// <summary>    /// 排序算法    /// 作者：仓储大叔    /// 代码来源：部分自写，部分网上摘录，都经过测试可以放心使用    /// </summary>    public class SortHelper    {        #region Public Methods        /// <summary>        /// 插入排序        /// </summary>        public static void InsertSort(List<int> list)        {            /*             * 复杂度 O（n^2）             * 插入排序从根本上来说，就是每次从未排序的数据集中取出一个元素，插入已排好序的数据集中。在以下所展示的实现中，两个数据集都存放在data中，data是一块连接的存储区域。最初，data包含size个无序元素。随着issort的运行，data逐渐被有序数据集所取代，直到issort返回（此时，data已经是一个有序数据集）。虽然实现插入排序用到连续的存储空间，但它也能用链表来实现（并不是所有的排序都可以使用链表来实现），并且效率不差。             */            for (int j = 1; j < list.Count; j++)            {                int i = j - 1;                int currnet = list[j];                while (i >= 0 && currnet > list[i])                {                    list[i + 1] = list[i];                    i--;                }                list[i + 1] = currnet;            }        }        /// <summary>        /// 快速排序        /// </summary>        /// <param name="list">目标数组</param>        /// <param name="left">子表的起始位置</param>        /// <param name="right">子表的终止位置</param>        public static void QuickSort(List<int> list, int left, int right)        {            /*           * 复杂度 O（nlg^n）           * 描述　利用快速排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分，其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当qksort返回时，data包含已排序的元素           */            if (left < right)            {                int i = Division(list, left, right);                //对枢轴的左边部分进行排序                QuickSort(list, i + 1, right);                //对枢轴的右边部分进行排序                QuickSort(list, left, i - 1);            }        }        /// <summary>        /// 归并排序        /// </summary>        /// <param name="array">目标数组</param>        /// <param name="first">子表的起始位置</param>        /// <param name="last">子表的终止位置</param>        public static void MergeSortFunction(List<int> array, int first, int last)        {            /*             * 复杂度　O（nlg^n）             * 描述　利用归并排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分，其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当mgsort返回时，data中包含已排序的元素。             */            if (first < last)   //子表的长度大于1，则进入下面的递归处理            {                int mid = (first + last) / 2;   //子表划分的位置                MergeSortFunction(array, first, mid);   //对划分出来的左侧子表进行递归划分                MergeSortFunction(array, mid + 1, last);    //对划分出来的右侧子表进行递归划分                MergeSortCore(array, first, mid, last); //对左右子表进行有序的整合（归并排序的核心部分）            }        }        /// <summary>          /// 计数排序          /// </summary>          /// <param name="arrayToSort">要排序的数组</param>          /// <param name="maxValue">数组的最大值加一</param>          /// <returns>计数排序后的结果</returns>          public static List<int> CountingSort(List<int> arrayA, int arrange)        {            /* 复杂度　O（n+k），n为要排序的元素的个数，k为data中最大的整数加1。             * 计数排序是一种高效的线性排序，它通过计算一个集合中元素出现的次数来确定集合如何排列。不同于之前介绍的一些算法是基于比较的，计数排序不需要进行元素比较，而且它的运行效率要比效率为O（nlg n）比较排序高。              */            int[] arrayResult = new int[arrayA.Count];            int[] arrayTemp = new int[arrange + 1];            for (int i = 0; i <= arrange; i++)            {                arrayTemp[i] = 0;            }            for (int j = 0; j < arrayA.Count; j++)            {                arrayTemp[arrayA[j]] += 1;            }            for (int k = 1; k <= arrange; k++)            {                arrayTemp[k] += arrayTemp[k - 1];            }            for (int m = arrayA.Count - 1; m >= 0; m--)            {                arrayResult[arrayTemp[arrayA[m]] - 1] = arrayA[m];                arrayTemp[arrayA[m]] -= 1;            }            return arrayResult.ToList();        }        /// <summary>        /// 冒泡排序        /// </summary>        /// <param name="arr"></param>        public void EbullitionSort(List<int> arr)        {            /*             * 复杂度O(n^2)              * 对1至n个记录，在第i趟排序中设置标志flag:=true，未排序的标志。从下往上扫描，以j作为内层循环变量，共做n-i次比较。在第j趟比较中，若r[j+1]<r[j]则交换，并至flag为false。在一趟排序结束后，若flag为true，则终止排序。             */            int i, j, temp;            bool done = false;            j = 1;            while ((j < arr.Count) && (!done))//判断长度                {                done = true;                for (i = 0; i < arr.Count - j; i++)                {                    if (arr[i] > arr[i + 1])                    {                        done = false;                        temp = arr[i];                        arr[i] = arr[i + 1];//交换数据                            arr[i + 1] = temp;                    }                }                j++;            }        }        #endregion        #region Private Methods        /// <summary>        /// 归并排序的核心部分：将两个有序的左右子表（以mid区分），合并成一个有序的表        /// </summary>        /// <param name="array"></param>        /// <param name="first"></param>        /// <param name="mid"></param>        /// <param name="last"></param>        private static void MergeSortCore(List<int> array, int first, int mid, int last)        {            int indexA = first; //左侧子表的起始位置            int indexB = mid + 1;   //右侧子表的起始位置            int[] temp = new int[last + 1]; //声明数组（暂存左右子表的所有有序数列）：长度等于左右子表的长度之和。            int tempIndex = 0;            while (indexA <= mid && indexB <= last) //进行左右子表的遍历，如果其中有一个子表遍历完，则跳出循环            {                if (array[indexA] <= array[indexB]) //此时左子表的数 <= 右子表的数                {                    temp[tempIndex++] = array[indexA++];    //将左子表的数放入暂存数组中，遍历左子表下标++                }                else//此时左子表的数 > 右子表的数                {                    temp[tempIndex++] = array[indexB++];    //将右子表的数放入暂存数组中，遍历右子表下标++                }            }            //有一侧子表遍历完后，跳出循环，将另外一侧子表剩下的数一次放入暂存数组中（有序）            while (indexA <= mid)            {                temp[tempIndex++] = array[indexA++];            }            while (indexB <= last)            {                temp[tempIndex++] = array[indexB++];            }            //将暂存数组中有序的数列写入目标数组的制定位置，使进行归并的数组段有序            tempIndex = 0;            for (int i = first; i <= last; i++)            {                array[i] = temp[tempIndex++];            }        }        /// <summary>        /// 获取按枢轴值左右分流后枢轴的位置        /// </summary>        /// <param name="list"></param>        /// <param name="left"></param>        /// <param name="right"></param>        /// <returns></returns>        private static int Division(List<int> list, int left, int right)        {            while (left < right)            {                int num = list[left]; //将首元素作为枢轴                if (num > list[left + 1])                {                    list[left] = list[left + 1];                    list[left + 1] = num;                    left++;                }                else                {                    int temp = list[right];                    list[right] = list[left + 1];                    list[left + 1] = temp;                    right--;                }            }            return left; //指向的此时枢轴的位置        }        #endregion    }