void InsertSort(int* arr, int n)
{
  for (int i = 0; i < n-1; i++)
  {
    int end = i;//end是指有序序列最后一个数字的下标
    int tmp = arr[end+1];//需要暂存一下尾部位置的元素
    while (end >= 0)
    {
      if (arr[end] > tmp)
      {
        arr[end + 1] = arr[end];
        end--;
      }
      else
      {
        break;
      }
    }
    arr[end+1] = tmp;
  }
}

void ShellSort(int* arr, int n)//我的希尔排序一点问题都没有
{
  int gap = n;
  while (gap > 1)//当while循环里面gap为1时，排序一次之后，循环结束，排序结束
  {
    gap = gap / 3 + 1;//保证我们的最后一次排序为直接插入排序，而不是预排序
    for (int i = 0; i < n - gap; i++)//实现gap组并排，并且最后一次排序为直接插入排序
    {
      int end = i;//end为最后一个有序数字的下标
      int tmp = arr[end + gap];
      while (end >= 0)
      {
        if (arr[end] > tmp)
        {
          arr[end + gap] = arr[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      arr[end + gap] = tmp;
    }
  }
}

void AdjustDownTeach(HPDataType* array, int n, int parent)
{
  int child = parent * 2 + 1;//上来我们就先假设最大的孩子是左孩子
  while (child<n)//我们想的是循环结束的条件，写的是循环继续的条件
  {
    //保证有右孩子的同时，看看我们的假设是否正确，错误就调整
    if (child + 1 < n && array[child + 1] > array[child])
    //如果假设错误，我们将孩子改为右孩子，并且你也有可能没有右孩子，没有右孩子，默认左孩子就是最大的
    //这里其实不用担心没有孩子的问题，因为如果parent没有孩子，child被赋值过后肯定大于n了直接跳出循环了就。
    {
      ++child;//将下标自增，左孩子就变为右孩子
    }
    if (array[parent] < array[child])//我们这里建的是大堆
    {
      Swap(&array[parent], &array[child]);
      parent = child;
      child = parent * 2 + 1;//这里再重新假设左孩子是大的，下一次循环就是先看看我们的假设是否正确，若不正确就进行调整。
    }
    else
    {
      break;
    }
  }
}
void HeapSort(int* arr, int n)
{
  for (int i = 1; i < n; i++)
  {
    Swap(&arr[0], &arr[n - i]);
    AdjustDownTeach(arr, n - i, 0);//我们传过去的数组大小是需要逐渐减小的，所以传的是n-i
  }
}

void BubbleSort(int* arr, int n)
{
  for (int i = 0; i < n; i++)
  {
    int exchange = 0;
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        Swap(&arr[j], &arr[j + 1]);
        exchange = 1;
      }
    }
    if (exchange == 0)
    {
      break;//数组元素已经有序，不用继续排序了，跳出循环即可。
    }
  }
}

int PartSort1(int* arr, int left, int right)
{
  //1.默认左边的数为key值
  //2.先让右边的数走，找小。再让左边的数走，找大，交换两个元素
  //3.当两边相遇的时候，相遇位置一定是比key要小的值，交换key和相遇位置
  int key = left;
  while (left<right)
  {
    while (left < right && arr[right] >= arr[key])
    {
      right--;
    }
    while (left < right && arr[left] <= arr[key])
    {
      left++;
    }
    Swap(&arr[left], &arr[right]);
  }
  Swap(&arr[key], &arr[left]);
  key = left;
  return key;
void QuickSort(int* arr, int begin, int end)
{
  if (begin>=end)//递归结束条件
  {
    return;
  }
  int key = PartSort1(arr, begin, end);
  QuickSort(arr, begin, key - 1);
  QuickSort(arr, key + 1, end);
}
}

int GetMidIndex(int *arr, int begin, int end)
{
  int mid = (begin + end) / 2;
  if (arr[begin] > arr[end])
  {
    if (arr[end] > arr[mid])
    {
      return end;
    }
    else if (arr[begin] < arr[mid])
    {
      return begin;
    }
    else
    {
      return mid;
    }
  }
  else// arr[begin] < arr[end]
  {
    if (arr[mid] < arr[begin])
    {
      return begin;
    }
    else if (arr[end] > arr[mid])
    {
      return mid;
    }
    else
    {
      return end;
    }
  }
}

void QuickSort(int* arr, int begin, int end)
{
  if ((end - begin) < 1)//递归结束条件
  {
    return;
  }
  if ((end - begin + 1) < 15)
  {
    InsertSort(arr + begin, end - begin + 1);
  }
  else
  {
    int key = PartSort1(arr, begin, end);
    QuickSort(arr, begin, key - 1);
    QuickSort(arr, key + 1, end);
  }
}

int PartSort2(int* arr, int left, int right)
{
  int mid = GetMidIndex(arr, left, right);
  Swap(&arr[left], &arr[mid]);
  int hole = left;
  int key = arr[left];
  while (left<right)
  {
    while (left < right && arr[right] >= key)
    {
      --right;
    }
    arr[hole] = arr[right];
    hole = right;
    while (left < right && arr[left] <= key)
    {
      ++left;
    }
    arr[hole] = arr[left];
    hole = left;
  }
  arr[hole] = key;
  return hole;
}

int PartSort3(int* arr, int left, int right)
{
  int mid = GetMidIndex(arr, left, right);
  Swap(&arr[left], &arr[mid]);
  int key = left;
  int prev = left, cur = left + 1;
  while (cur <= right)
  {
    if (arr[cur] < arr[key] && ++prev != cur)//逻辑与后面的条件就是为了防止交换同一个位置的元素，这时交换没有必要
    {
      Swap(&arr[cur], &arr[++prev]);
    }
    cur++;
  }
  Swap(&arr[key], &arr[prev]);
  return prev;
}

void QuickSortPlus(int* arr, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  if ((end - begin + 1) < 15)
  {
    InsertSort(arr + begin, end - begin + 1);
  }
  else
  {
    int mid = GetMidIndex(arr, begin, end);
    Swap(&arr[begin], &arr[mid]);
    int key = arr[begin];
    int left = begin, right = end, cur = begin + 1;
    while (cur <= right)
    {
      if (arr[cur] < key)
      {
        Swap(&arr[left], &arr[cur]);
        left++;
        cur++;
      }
      else if (arr[cur] > key)
      {
        Swap(&arr[cur], &arr[right]);
        right--;
      }
      else//arr[cur]==key时
      {
        cur++;
      }
    }
    QuickSortPlus(arr, begin, left - 1);
    QuickSortPlus(arr, right + 1, end);
  }
}