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

namespace demo
{
    class Program
    {
        private int[] arr;
        private int upper;
        private int numElements;

        public Program(int size) {
            arr = new int[size];
            upper = size - 1;
            numElements = 0;
        }

        public void Insert(int item) {
            arr[numElements] = item;
            numElements++;
        }

        public void DisplayElement() {
            for (int i = 0; i <= upper; i++)
            {
                Console.Write(arr[i] + "  ");

            }  Console.WriteLine();
        }

        public void Clear() {
            for (int i = 0; i <= upper; i++)
            {
                arr[i] = 0;
                numElements = 0;
            }
        }
        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="arr"></param>
         void MpSort() {
            int temp;
            for (int outer = upper; outer >=1; outer--)
            {
                for (int inner = 0; inner <=outer-1; inner++)
                {
                    if (arr[inner]>arr[inner+1])
                    {
                        temp = arr[inner];
                        arr[inner] = arr[inner + 1];
                        arr[inner + 1] = temp;
                    }
                }
                this.DisplayElement();
            }
            
        }

        //选择排序 假设第一个最小
        public void XzSort() {
            int min, temp;
            for (int outter = 0; outter <= upper; outter++)
            {
                min = outter;
                for (int inner = outter+1; inner <= upper; inner++)
                {
                    if (arr[inner]< arr[min])
                    {
                        min = inner;
                    }
                }
                temp = arr[outter];
                arr[outter] = arr[min];
                arr[min] = temp;
                this.DisplayElement();
            }
        }

        //插入排序
        public void ChaRuSort() {
            int inner, temp;

            for (int outer = 1; outer <=upper; outer++)
            {
                temp = arr[outer];
                inner = outer;
                while (inner>0&&arr[inner-1]>=temp)
                {
                    arr[inner] = arr[inner-1];
                    inner -= 1;
                }
                arr[inner] = temp;
                this.DisplayElement();
            }
        }
        static void Main(string[] args)
        {

            Program nums = new Program(10);

            Random rnd = new Random(100);
            for (int i = 0; i <=9; i++)
            {
                nums.Insert(rnd.Next(0,100));
            }
            Console.WriteLine("排序前");
            nums.DisplayElement();
            Console.WriteLine();
            Console.WriteLine("排序中");
            //nums.MpSort(); //冒泡排序
            //nums.XzSort();//选择排序
            nums.ChaRuSort();//插入排序
            Console.WriteLine("排序后");
            nums.DisplayElement();  
            Console.Read();
        }
    }
}