必会基础排序算法，C#实现

using System;
using System.Text;

namespace SortFunctions
{
    class Program
    {
        static void Main(string[] args)
        {
            //生成测试数据
            Random random = new Random();
            int[] arr = new int[10];
            for(int i = 0; i < 10; i++)
            {
                arr[i] = random.Next(0, 100);
            }

            Program pg = new Program();
            Console.WriteLine("排序前:");
            pg.PrintArray(arr);


            //pg.BubbleSort(arr);
            //pg.SelectSort(arr);
            //pg.InsertSort(arr);
            //pg.QuickSort(arr, 0, arr.Length - 1);
            //pg.MergeSort(arr, 0, arr.Length - 1);
            pg.ShellSort(arr);

            Console.WriteLine("排序后:");
            pg.PrintArray(arr);
        }

        //打印数组
        void PrintArray(int[] arr)
        {
            StringBuilder sb = new StringBuilder();
            foreach(int v in arr)
            {
                sb.Append(v.ToString() + ", ");
            }
            Console.WriteLine(sb);
        }

        //交换数组中两个元素
        void SwapItem(int[] arr, int i, int j)
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }


        //冒泡排序
        //核心：从前往后邻位比较，大的数不断往后冒，冒到最后面的的就不再管了
        void BubbleSort(int[] arr)
        {
            for(int i = 0; i < arr.Length; i++)
            {
                for(int j = 0; j < arr.Length - i - 1; j++)
                {
                    if(arr[j] > arr[j + 1])
                    {
                        SwapItem(arr, j, j + 1);
                    }
                }
            }
        }

        //选择排序
        //核心：每次都从剩余未排序元素里找出最小的，放到已排序的末尾
        void SelectSort(int[] arr)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                int minIdx = i;
                for(int j = i + 1; j < arr.Length; j++)
                {
                    if(arr[j] < arr[minIdx])
                    {
                        minIdx = j;
                    }
                }
                if(minIdx != i)
                {
                    SwapItem(arr, minIdx, i);
                }
            }
        }

        //插入排序
        //核心：把后面未排序序列的第一个元素，往前面已经排序的序列里冒泡
        void InsertSort(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                for(int j = i; j > 0; j--)
                {
                    if(arr[j] < arr[j - 1])
                    {
                        SwapItem(arr, j, j - 1);
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        //快速排序
        //核心：不断切片，使左侧小于基准值，右侧大于基准值，递归
        void QuickSort(int[] arr, int first, int last)
        {
            //1.左右碰头结束
            if (first >= last) return;

            int i = first;
            int j = last;
            //2.这里选最后一个位置为基准值
            int k = arr[last];

            while(i < j)
            {
                //3.左往右走，找到大于k的值塞到右边坑位
                while (i < j && arr[i] <= k)
                {
                    i++;
                }
                arr[j] = arr[i];

                //4.右往左走，找到小于k的值塞到左边坑位
                while (i < j && arr[j] >= k)
                {
                    j--;
                }
                arr[i] = arr[j];
            }

            //5.把基准回归，此时i，j已相等
            arr[j] = k;

            //6.分别递归处理两侧的序列
            QuickSort(arr, first, j - 1);
            QuickSort(arr, j + 1, last);
        }


        //归并排序
        //核心：两个有序子列的归并
        void MergeSort(int[] arr, int first, int last)
        {
            if (first >= last) return;

            int mid = (first + last) / 2;
            //左侧有序
            MergeSort(arr, first, mid);
            //右侧有序
            MergeSort(arr, mid + 1, last);
            //将两个有序数列合并
            MergeCore(arr, first, mid, last);
        }

        void MergeCore(int[] arr, int first, int mid, int last)
        {
            int[] tmp = new int[last - first + 1];
            //3指针
            //左子序列起始位置
            int m = first;
            //右子序列起始位置
            int n = mid + 1;
            //合并序列起始位置
            int k = 0;

            //两个子序列都有元素s
            while(m <= mid && n <= last)
            {
                if(arr[m] < arr[n])
                {
                    tmp[k++] = arr[m++];
                }
                else
                {
                    tmp[k++] = arr[n++];
                }
            }

            //两个子序列只剩一个序列还有元素
            while(m <= mid)
            {
                tmp[k++] = arr[m++];
            }
            while(n <= last)
            {
                tmp[k++] = arr[n++];
            }

            //把tmp中排序好的元素放回arr中
            for(int i = 0; i < k; i++)
            {
                arr[first + i] = tmp[i];
            }
        }

        //希尔排序
        //核心：定义增量序列，不断递减增量至1，做插入排序
        void ShellSort(int[] arr)
        {
           //增量h，等于1时最后一次排序
            int h = arr.Length / 2;
            while(h >= 1)
            {
                //这里开始是简单插入排序算法，把简单插入排序算法的1换成h
                for(int i = h; i < arr.Length; i++)
                {
                    for(int j = i; j >= h; j -= h)
                    {
                        if(arr[j] < arr[j - h])
                        {
                            SwapItem(arr, j, j - h);
                        }
                        else
                        {
                            break;
                        }
                    }
                }

                h /= 2;
            }
        }

    }
}