三大初級排序算法

1、冒泡排序 冒泡排序是最慢的排序算法。在實(shí)際運(yùn)用中它是效率最低的算法。它通過一趟又一趟地比較數(shù)組中的每一個(gè)元素，使較大的數(shù)據(jù)下沉，較小的數(shù)據(jù)上升。它是O(n^2)的算法。2、插入排序 插入排序通過把序列中的值插入一個(gè)已經(jīng)排序好的序列中，直到該序列的結(jié)束。3、Shell排序 Shell排序通過將數(shù)據(jù)分成不同的組，先對每一組進(jìn)行排序，然后再對所有的元素進(jìn)行一次插入排序，以減少數(shù)據(jù)交換和移動(dòng)的次數(shù)。平均效率是O(nlogn)。

冒泡排序C#實(shí)現(xiàn)：

    /// <summary>    /// 冒泡排序    /// </summary>    public class BubbleSort : ISort    {        public int[] Sort(int[] array)        {            if (array != null)            {                for (int i = 0; i < array.Length; i++)                {                    for (int j = 1; j < array.Length - i; j++)                    {                        Swap(ref array[j - 1], ref array[j]);                    }                }            }            return array;        }        public static void Swap(ref int int1, ref int int2)        {            if (int1 > int2)            {                int temp = int1;                int1 = int2;                int2 = temp;            }        }    }

插入排序C#實(shí)現(xiàn)：

    /// <summary>    /// 插入排序    /// </summary>    public class InsertSort : ISort    {        public int[] Sort(int[] array)        {            if (array != null)            {                int k = 1;//使用k變量，后面更好的擴(kuò)展到Shell排序                for (int i = k; i < array.Length; i++)                {                    int current = array[i];                    int PReIndex = i - k;                    while (preIndex >= 0 && preIndex < array.Length && current < array[preIndex])                    {                        array[preIndex + k] = array[preIndex];                        preIndex = preIndex - k;                    }                    array[preIndex + k] = current;                }            }            return array;        }    }

Shell排序C#實(shí)現(xiàn)：

    /// <summary>    /// shell排序    /// </summary>    public class ShellSort : ISort    {        public int[] Sort(int[] array)        {            if (array != null)            {                int[] list = { 9, 5, 3, 2, 1 };                foreach (int k in list)                {                    for (int i = k; i < array.Length; i++)                    {                        int current = array[i];                        int preIndex = i - k;                        while (preIndex >= 0 && preIndex < array.Length && current < array[preIndex])                        {                            array[preIndex + k] = array[preIndex];                            preIndex = preIndex - k;                        }                        array[preIndex + k] = current;                    }                }            }            return array;        }    }

性能測試代碼：

    class Program    {        public static Random re = new Random();        static void Main(string[] args)        {            Stopwatch stw1 = new Stopwatch();            Stopwatch stw2 = new Stopwatch();            Stopwatch stw3 = new Stopwatch();            int[] intArray1 = GetArray(int.MaxValue/100000);            int[] intArray2 = GetArray(int.MaxValue/100000);            int[] intArray3 = GetArray(int.MaxValue/100000);            ISort sort1 = new BubbleSort();//冒泡排序            stw1.Start();            int[] result1 = sort1.Sort(intArray1);            stw1.Stop();            Console.WriteLine("輸出排序的結(jié)果(冒泡排序)");            Console.WriteLine("程序共運(yùn)行時(shí)間:" + stw1.Elapsed.ToString());            ISort sort2 = new InsertSort();//插入排序            stw2.Start();            int[] result2 = sort2.Sort(intArray2);            stw2.Stop();            Console.WriteLine("輸出排序的結(jié)果(插入排序)");            Console.WriteLine("程序共運(yùn)行時(shí)間:" + stw2.Elapsed.ToString());            ISort sort3 = new ShellSort();//Shell排序            stw3.Start();            int[] result3 = sort3.Sort(intArray3);            stw3.Stop();            Console.WriteLine("輸出排序的結(jié)果(Shell排序)");            Console.WriteLine("程序共運(yùn)行時(shí)間:" + stw3.Elapsed.ToString());            //輸出排序的結(jié)果            //OutputResult(result1, result2, result3);            Console.ReadKey();        }    }

結(jié)果截圖：