public class SortHelper
    {
        /// <summary>
        /// 交换排序 - 冒泡排序
        /// 描述：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，
        /// 则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值，接着对该数组除最右端的n-1个元素进行同样的
        /// 操作，再接着对剩下的n-2ge元素做同样的操作，直到整个数组有序排列。
        /// 
        /// 算法：
        /// 时间复杂度为 O(n^2)
        /// 空间复杂度为 O(1)
        /// </summary>
        public void bubbleSort(int[] arr)
        {
            //控制共比较多少轮
            for (int i = 0; i < arr.Length; i++)
            {
                //控制比较的次数
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    if (arr[j] > arr[j + 1])
                    {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }

        /// <summary>
        /// 交换排序 - 快速排序
        /// 描述：左右两端选择一个数作为游标，在挑选第一个数字为基准数，比较两端的值是否比基准数大，大的放右边，小的放左边。然后两端的游标往中间靠拢，
        /// 直到游标的值重合，停止。然后再次选择第二个数字为基准数，反复刚才的操作。
        /// 
        /// 算法：
        /// 时间复杂度为 O(nlog2n)
        /// 空间复杂度为 O(1)
        /// </summary>
        /// <param name="arr"></param>

        public void quickSort(int[] arr, int start, int end)
        {
            if (start < end)//结束标记，中间要有 元素
            {
                //把数组中的第0个数字作为标准数
                int stard = arr[start];
                //记录需要排序的游标
                int low = start;
                int high = end;
                //循环找比标准数大的数和比标准数小的数
                while (low < high)
                {
                    //右边的数字比标准数大
                    while (low < high && stard <= arr[high])
                    {
                        high--;
                    }
                    //使用右边的数字替换左边的数
                    arr[low] = arr[high];
                    //如果左边的数字比标准数小
                    while (low < high && arr[low] <= stard)
                    {
                        low++;
                    }
                    arr[high] = arr[low];
                }
                //把标准数赋给低所在的位置的元素
                arr[low] = stard;
                //处理所有的小的数字
                quickSort(arr, start, low);
                //处理所有的大的数字
                quickSort(arr, low + 1, end);
            }
        }


        /// <summary>
        /// 插入排序--直接插入排序
        /// 描述;从第二个数开始，依次比较前面的数是否比自己大，大的插入到前面，再依次比较，直到不比自己大。
        /// 处理过程，比自己大的数字依次后移，然后拿临时变量中的值，替换最初移动的那个
        /// 
        /// 算法：
        /// 时间复杂度为 O(n^2)
        /// 空间复杂度为 O(1)
        /// </summary>
        /// <param name="arr"></param>
        public void insertSort(int[] arr)
        {
            //遍历所有的数字
            for (int i = 1; i < arr.Length; i++)
            {
                //如果当前数字比前一个数字小
                if (arr[i] < arr[i - 1])
                {
                    //把当前遍历数字存起来
                    int temp = arr[i];
                    int j;
                    //遍历当前数字前面所有的数字
                    for (j = i - 1; j >= 0 && temp < arr[j]; j--)
                    {
                        //把前一个数字赋给后一个数
                        arr[j + 1] = arr[j];
                    }
                    //把临时变量（外层for循环的当前元素）赋给不满足条件的后一个元素。
                    arr[j + 1] = temp;
                }

            }
        }

        /// <summary>
        /// 插入排序--希尔排序
        /// 描述：解决直接插入排序较慢的问题，假设有一组顺序的数，突然来了一个元素比较小，依旧需要挨个比较前面的值，插入最前面，效率不高。
        /// 希尔排序引入步长概念，按步长划分组，组内进行排序
        /// 
        /// 算法：
        /// 时间复杂度为 O(n^2)
        /// 空间复杂度为 O(1)
        /// </summary>
        /// <param name="arr"></param>
        public void shellSort(int[] arr)
        {
            //遍历所有的步长
            for (int d = arr.Length / 2; d > 0; d /= 2)
            {
                //遍历所有元素
                for (int i = d; i < arr.Length; i++)
                {
                    //遍历本组中所有的元素
                    for (int j = i - d; j >= 0; j -= d)
                    {
                        //如果当前元素大于加上步长后的那个元素
                        if (arr[j] > arr[j + d])
                        {
                            int temp = arr[j];
                            arr[j] = arr[j + d];
                            arr[j + d] = temp;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 选择排序--简单选择排序
        /// 说明：找一个最小的数，移动到第一个位置，然后依次找其后第二小的数字移动到前面。
        /// 
        /// 算法：
        /// 时间复杂度为 O(n^2)
        /// 空间复杂度为 O(1)
        /// </summary>
        /// <param name="arr"></param>
        public void choiseSort(int[] arr)
        {
            //遍历所有的数
            for (int i = 0; i < arr.Length; i++)
            {
                int minIndex = i;
                //把当前遍历的数和后面所有的数依次进行比较，并记录下最小的数的下标
                for (int j = i + 1; j < arr.Length; j++)
                {
                    //如果后面比较的数比记录的最小的数小
                    if (arr[minIndex] > arr[j])
                    {
                        //记录下最小的那个数的下标
                        minIndex = j;
                    }
                }
                //如果最小的数和当前遍历数的下标不一致，说明下标为minindex的数比当前遍历的数更小。
                if (i != minIndex)
                {
                    int temp = arr[i];
                    arr[i] = arr[minIndex];
                    arr[minIndex] = temp;
                }
            }
        }

        //选择排序--堆排序


    }

        static void Main(string[] args)
        {
            int[] arr = {5,7,2,9,4,1,0,5,7 };
            Console.WriteLine("排序前：");
            Console.WriteLine(string.Join(",", arr));
            SortHelper sortHelper = new SortHelper();
            //sortHelper.BubbleSort(arr);
            //sortHelper.quickSort(arr,0,arr.Length-1);
            //sortHelper.insertSort(arr);
            //sortHelper.shellSort(arr);
            sortHelper.choiseSort(arr);

            //输出结果
            Console.WriteLine("排序后：");
            Console.WriteLine(string.Join(",", arr));
            Console.ReadLine();
        }