void BubbleSort(int* arr, int n)
{
  int j;
  for (j = 0; j < n - 1; j++)
  {
    int exchange = 0;
    int i;
    for (i = 0; i < n - 1 - j; i++)//遍历
    {
      if (arr[i] > arr[i + 1])//每个数比较，大的数往后走
      {
        Swap(&arr[i], &arr[i + 1]);
        exchange = 1;
      }
    }
    if (exchange == 0)//此时就是防止数组已经是有序的，然后还进行比较，所以我们为了防止，就可以这样写，交换了就不满足这个条件，就正常比较，没有交换就满足这个条件，就跳出循环
    {
      break;
    }
  }
}

void BubbleSort(int* arr, int n)
{
  int end = n;
  while (end > 0)
  {
    int i;
    for (i = 0; i < n - 1; i++)
    {
      if (arr[i] > arr[i + 1])
      {
        Swap(&arr[i], &arr[i + 1]);
      }
    }
    //写完单趟，然后我为了控制次数，可以用上述的for循环，也可以直接用while循环，只要把比较的次数给控制好了，怎样写都行
    end--;//反正就是n次而已
  }
}

//void QuickSort(int* arr, int n)
//为了使用我的分治递归现在我的这个函数的作用就不单单是一个值了，是一段数组中的值，所以就不可以按照上面这样写，应该要写成下面的形式
void QuickSort(int* arr, int left, int right)
{
  if (left >= right)//递归的停止条件（就是当我的区间只有一个值或不存在）大于表示只有一个值，等于表示区间不存在
  {
    return;
  }
  //int begin = 0;//就是最左边的意思
  //int end = n - 1;//就是最右边的意思
  //此时为了实现分治递归，我们就要把上面的begin和end写成下面的这个样子
  int begin = left;
  int end = right;
  int pivot = begin;//按照原理，此时的这个pivot可以给最左边的位置或者最右边的位置
  int key = arr[begin];//按照原理，此时的这个pivot可以给最左边的位置或者最右边的位置
  while (begin < end)//因为待会会进行begin++ end--的操作，所以当它们相等之后，我就已经实现了把比key大的放在key的右边，比key小的放在key的左边，所以只要begin!=end 这个循环就要继续
  {
    //右边找小，放到左边(在key的右边找，自然是从最右边开始)
    while (begin < end && arr[end] >= key)
    {
      end--;
    }
    //程序来到这里说明我找到比key小的元素了（然后此时按照原理：就是把找到的这个值放到key的pivot位置，然后重新把这个找到的元素的位置赋值成pivot（便于待会把左边的元素放过来））
    arr[pivot] = arr[end];
    pivot = end;
    //此时我的左边的坑被右边的元素占据了，所以现在就要在左边找比key大的数据放到右边的坑中，然后左边再形成一个坑
    while (begin < end && arr[begin] <= key)
    {
      begin++;
    }
    //程序来到这个位置说明我找到比key大的元素了，然后把它放到右边的坑中就行，顺便把自己原来的位置重新赋值为坑,使左边又有一个新的坑，便于待会后面比key小的值放进来
    arr[pivot] = arr[begin];
    pivot = begin;
  }
  //此时程序来到这个位置就是说明：begin和end相遇了（此时就可以把我的key的位置直接放到最后的这个pivot中）
  pivot = begin;//此时就是找最后一个坑的位置
  arr[pivot] = key;//然后把key放到这个坑里面去
  //此时这边我们为了可以使用我的分治递归，按照原理就是要把这个数组分成三部分：
  //[left,right]
  //                                                [pivot]
  //                                                   |                                     
  //[left,pivot-1][pivot][pivot+1,right] =>  5 1 2 4 3 6 9 7 10 8
  //因为此时只要左子区间有序了，右子区间有序了，我的整个数组就有序了，所以此时就是把左子区间和右子区间都拿去递归就行了
  QuickSort(arr, left, pivot - 1);
  QuickSort(arr, pivot + 1, right);
}