排序算法(一)

显示全部楼层 · 2013-3-6 22:18:15

之前关于扩展数组的时候，想到了一个排序的Sort方法，然后就联想到把常用的排序算法都总结一下吧。毕竟面试的时候对于算法还是有一定要求的。关于算法的时间复杂度和空间复杂度就不在这里面介绍了，可以参考相关的资料。先给出比较简单的三个，都不适合大规模的数据排序。

[C#] 纯文本查看 复制代码

 /// <summary>
        /// 插入排序，适合千级别或是更小级别的排序，不推荐大数据的排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="originArray"></param>
        /// <returns></returns>
        public static T[] Insert_Sort<T>(T[] originArray, Compare<T> compare)
        {
            if (originArray.Length == 0 || originArray.Length == 1)
            {
                return originArray;
            }

            for (int i = 1; i < originArray.Length; i++)
            {
                T temp = originArray[i];
                int tempIndex = i;

                while (tempIndex > 0 && compare(temp, originArray[tempIndex-1]))
                {
                    originArray[tempIndex] = originArray[tempIndex - 1];
                    tempIndex--;
                }
                originArray[tempIndex] = temp;
            }

            return originArray;
        }

        /// <summary>
        /// 冒泡法，比较简单的排序算法，效率比较低，不适合大量数据的排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="originArray"></param>
        /// <param name="compare"></param>
        /// <returns></returns>
        public static T[] Bubble_Sort<T>(T[] originArray, Compare<T> compare)
        {
            if (originArray.Length == 0 || originArray.Length == 1)
            {
                return originArray;
            }

            for (int i = 0; i < originArray.Length; i++)
            {
                for (int j = originArray.Length - 1; j > i; j--)
                {
                    if (compare(originArray[j], originArray[j - 1]))
                    {
                        T temp = originArray[j];
                        originArray[j] = originArray[j - 1];
                        originArray[j - 1] = temp;
                    }
                }
            }

            return originArray;
        }

        /// <summary>
        /// 选择排序，和冒泡排序比较像，同样不适合大数据的排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="originArray"></param>
        /// <param name="compare"></param>
        /// <returns></returns>
        public static T[] Select_Sort<T>(T[] originArray, Compare<T> compare)
        {
            if (originArray.Length == 0 || originArray.Length == 1)
            {
                return originArray;
            }

            for (int i = 0; i < originArray.Length; i++)
            {
                for (int j = i + 1; j < originArray.Length; j++)
                {
                    if (compare(originArray[j], originArray[i]))
                    {
                        T temp = originArray[i];
                        originArray[i] = originArray[j];
                        originArray[j] = temp;
                    }
                }
            }

            return originArray;
        }