一些排序算法源码

快速排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _01_快速排序
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] data = { 123, 654, 21, 40, 4, 32, 7, 57, 575, 49, 16, 549, 648, 52, 49, 21, 897, 21, 1 };
            QuickSort(data);

            foreach (int i in data)
            {
                Console.Write(i.ToString() + "\t");
            }

            Console.ReadKey();
        }

        static void QuickSort<T>(T[] data)
            where T : IComparable
        {
            if (data == null)
            {
                return;
            }

            QuickSortCore(data, 0, data.Length - 1);
        }

        static void QuickSortCore<T>(T[] data, int beginIndex, int endIndex)
            where T : IComparable
        {
            if (beginIndex < endIndex)
            {
                int begin = beginIndex;
                int end = endIndex;
                T baseT = data[begin];
                while (begin < end)
                {
                    while (begin < end && baseT.CompareTo(data[end]) <= 0)
                    {
                        end--;
                    }
                    if (begin < end)
                    {
                        data[begin++] = data[end];
                    }

                    while (begin < end && baseT.CompareTo(data[begin]) > 0)
                    {
                        begin++;
                    }
                    if (begin < end)
                    {
                        data[end--] = data[begin];
                    }
                }

                data[begin] = baseT;

                QuickSortCore(data, beginIndex, begin - 1);
                QuickSortCore(data, begin + 1, endIndex);
            }
        }
    }
}

归并排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _02_归并排序
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 31, 4, 691, 674, 16, 165, 16, 14, 1, 3, 45, 849, 68, 64, 645, 79, 17 };
            MergeSort(array);
            foreach (int n in array)
            {
                Console.WriteLine(n);
            }

            Console.ReadKey();
        }

        private static void MergeSort<T>(T[] data)
            where T : IComparable
        {
            if (data == null)
            {
                return;
            }

            T[] temp = new T[data.Length];
            MergeSortCore(data, 0, data.Length - 1, temp);
        }

        static void MergeSortCore<T>(T[] data, int beginIndex, int endIndex, T[] temp)
            where T : IComparable
        {
            if (beginIndex < endIndex)
            {
                int mid = (beginIndex + endIndex) / 2;
                MergeSortCore(data, beginIndex, mid, temp);
                MergeSortCore(data, mid + 1, endIndex, temp);
                MergeArray(data, beginIndex, mid, endIndex, temp);
            }
        }

        static void MergeArray<T>(T[] data, int beginIndex, int midIndex, int endIndex, T[] temp)
            where T:IComparable
        {
            int i = beginIndex, j = midIndex + 1;
            int m = midIndex, n = endIndex;
            int index = 0;

            while (i <= m && j <= n)
            {
                temp[index++] = data[i].CompareTo(data[j]) < 0 ? data[i++] : data[j++];
            }

            while (i <= m)
            {
                temp[index++] = data[i++];
            }

            while (j <= n)
            {
                temp[index++] = data[j++];
            }

            for (i = 0; i < index; i++)
            {
                data[beginIndex + i] = temp[i];
            }
        }
    }
}

插入排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _03_插入排序
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 31, 4, 691, 674, 16, 165, 16, 14, 1, 3, 45, 849, 68, 64, 645, 79, 17 };
            InsertSort(null);
            foreach (int n in array)
            {
                Console.WriteLine(n);
            }

            Console.ReadKey();
        }

        static void InsertSort<T>(T[] data)
            where T:IComparable
        {
            if (data == null)
            {
                return;
            }

            for (int i = 1; i < data.Length; i++)
            {
                T tempT = data[i];
                int j = i - 1;
                while (j >= 0 && data[j].CompareTo(tempT) > 0)
                {
                    data[j + 1] = data[j];
                    j--;
                }
                data[j + 1] = tempT;
            }
        }
    }
}

冒泡排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _04_冒泡排序
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 31, 4, 691, 674, 16, 165, 16, 14, 1, 3, 45, 849, 68, 64, 645, 79, 17 };
            BubbleSort(array);
            foreach (int n in array)
            {
                Console.WriteLine(n);
            }

            Console.ReadKey();
        }

        static void BubbleSort<T>(T[] data)
            where T : IComparable
        {
            if (data == null)
            {
                return;
            }

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

堆排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _05_堆排序
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] data = { 123, 654, 21, 40, 4, 32, 7, 57, 575, 49, 16, 549, 648, 52, 49, 21, 897, 21, 1 };
            HeapSort(data);

            foreach (int i in data)
            {
                Console.Write(i.ToString() + "\t");
            }

            Console.ReadKey();
        }

        static void HeapSort<T>(T[] data)
            where T : IComparable
        {
            if (data == null)
            {
                return;
            }

            for (int i = data.Length / 2 - 1; i >= 0; i--)
            {
                AdjastHeap(data, i, data.Length);
            }

            for (int i = data.Length - 1; i > 0; i--)
            {
                T tempT = data[i];
                data[i] = data[0];
                data[0] = tempT;

                AdjastHeap(data, 0, i);
            }
        }

        static void AdjastHeap<T>(T[] data, int index, int length)
            where T : IComparable
        {
            T tempT = data[index];
            for (int i = index * 2 + 1; i < length; i = i * 2 + 1)
            {
                if (i + 1 < length && data[i + 1].CompareTo(data[i]) > 0)
                {
                    i++;
                }

                if (tempT.CompareTo(data[i]) < 0)
                {
                    data[index] = data[i];
                    index = i;
                }
                else
                {
                    break;
                }
            }
            data[index] = tempT;
        }
    }
}

希尔排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _06_希尔排序
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] data = { 123, 654, 21, 40, 4, 32, 7, 57, 575, 49, 16, 549, 648, 52, 49, 21, 897, 21, 1 };
            SeeleSort(data);

            foreach (int i in data)
            {
                Console.Write(i.ToString() + "\t");
            }

            Console.ReadKey();
        }

        static void SeeleSort<T>(T[] data)
            where T : IComparable
        {
            int length = data.Length;
            for (int h = length / 2; h > 0; h = h / 2)
            {
                for (int i = h; i < length; i++)
                {
                    T temp = data[i];
                    if (temp.CompareTo(data[i - h]) < 0)
                    {
                        for (int j = 0; j < i; j += h)
                        {
                            if (temp.CompareTo(data[j]) < 0)
                            {
                                temp = data[j];
                                data[j] = data[i];
                                data[i] = temp;
                            }
                        }
                    }
                }
            }
        }
    }
}