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

namespace Sort
{
   public class Sort
   {
      ///<summary>
      /// 插入排序--稳定排序
      ///</summary>
      ///<param name="list"></param>
      public static void InsertSort(List<int> list)
      {
         int j, tmp;
         for (int i =1; i < list.Count; i++)
         {
            j = i;
            tmp = list[i];
            while (j >0&& tmp <= list[j -1])
            {
               list[j] = list[j -1];
               j--;
            }
            list[j] = tmp;
         }
      }
      ///<summary>
      /// 希尔排序
      ///</summary>
      ///<param name="list"></param>
      public static void ShellSort(List<int> list)
      {
         int j, tmp;
         int h =3;
         while (h>0)
         {
            for (int i = h; i < list.Count; i++)
            {
               tmp = list[i];
               j = i;
               while ((j > h -1) && tmp < list[j - h])
               {
                  list[j] = list[j - h];
                  j -= h;
               }
               list[j] = tmp;
            }
            h = (h -1) %3;
         }
      }

      ///<summary>
      /// 冒泡排序--稳定排序
      ///</summary>
      ///<param name="list"></param>
      public static void BubbleSort(List<int> list)
      {
         if (list ==null|| list.Count <1)
         {
            return;
         }
         int tmp;
         for (int i =0; i < list.Count; i++)
         {
            bool flag=false;
            for (int j = i+1; j <list.Count; j++)
            {
               if (list[i] > list[j])
               {
                  tmp = list[i];
                  list[i] = list[j];
                  list[j] = tmp;
                  flag=true;
               }
               if(flag==false)
               {
                  return;
               }
            }
         }
      }
      ///<summary>
      /// 选择排序--直接选择排序
      ///</summary>
      ///<param name="list"></param>
      public static void SelectSort(List<int> list)
      {
         int min, tmp;
         for (int i =0; i < list.Count; i++)
         {
            min = i;
            for (int j = i +1; j < list.Count; j++)
            {
               if (list[j] < list[min])
               {
                  min = j;
               }
            }
            if (i != min)
            {
               tmp = list[i];
               list[i] = list[min];
               list[min] = tmp;
            }
         }
      }

      ///<summary>
      /// 堆排序
      ///</summary>
      ///<param name="list"></param>
      public static void HeapSort(List<int> list)
      {
         int n = list.Count;
         for (int i = n/2-1; i >=0; i--)
         {
            Sift(list, i, n -1);
         }
         for (int i = n -1; i >=1; i--)
         {
            int tmp = list[0];//取堆顶元素
            list[0] = list[i];//让堆中最后一个元素上移到堆顶位置
            list[i] = tmp;//此时list[i]已不在堆中，用于存放排好序的元素
            Sift(list, 0, i -1);//重新调整堆
         }
      }

      private static void Sift(List<int> list, int low, int high)//建堆过程
      {
         //i为欲调整子树的根结点的索引号，j为这个结点的左孩子
         int i = low, j =2* i +1;
         int tmp = list[i];//记录双亲结点的值
         while (j<=high)
         {//如果左孩子小于右孩子，则将欲交换的孩子结点指向右孩子
            if (j < high && list[j] < list[j +1])
            {
               j++;//j指向右孩子
            }
            if (tmp < list[j])//如果双亲结点小于它的孩子结点
            {
               list[i] = list[j];//交换双亲结点和它的孩子结点
               i = j;//以交换后的孩子结点为根，继续调整它的子树
               j =2* i +1;//j此时代表交换后的孩子结点的左孩子
            }
            else//调整完毕
            {
               break;
            }
         }
         list[i] = tmp;//使最初被调整的结点放入正确的位置
      }

      ///<summary>
      /// 归并排序--稳定排序
      ///</summary>
      ///<param name="list"></param>
      ///<param name="low"></param>
      ///<param name="high"></param>
      public static void MergeSort(List<int> list, int low, int high)
      {
         if (low < high)
         {
            int mid = (low + high) /2;
            MergeSort(list, low, mid);
            MergeSort(list, mid +1, high);
            Merge(list, low, mid, high);
         }
      }

      private static void Merge(List<int> list, int low, int mid, int high)
      {//listTmp为临时存放空间，存放合并后的数据
         List<int> listTmp =new List<int>(high - low +1);
         int i = low, j = mid +1, k =0;//k为listTmp的下标
         while (i <= mid && j <= high)
         {
            listTmp[k++] = (list[i] < list[j]) ? list[i++] : list[j++];
         }
         while (i <= mid)
         {
            listTmp[k++] = list[i++];
         }
         while (j <= high)
         {
            listTmp[k++] = list[j++];
         }
         for (i = low, k=0; i <= high;i++,k++ )
         {
            list[i] = listTmp[k];
         }
      }

      ///<summary>
      /// 快速排序
      ///</summary>
      ///<param name="list"></param>
      public static void QuickSort(List<int> list)
      {
         QuickSort(list, 0, list.Count -1);
      }
      public static void QuickSort(List<int> list, int low, int high)
      {
         if (low < high)
         {
            int i = low, j = high, tmp = list[i];
            while (i < j)
            {
               while (i < j && list[j] >= tmp)
               {
                  j--;
               }
               list[i] = list[j];
               while (i < j && list[i] <= tmp)
               {
                  i++;
               }
               list[j] = list[i];
            }
            list[i] = tmp;
            QuickSort(list, low, i -1);
            QuickSort(list, i +1, high);
         }
      }
   }
}