细数排序（1）

void insertsort(int *arr, int n)
{
  int i;
  for (i = 0; i < n - 1; i++)
  {
    int end = i;
    int tmp = arr[end + 1];
    while (end >= 0)
    {
      if (tmp < arr[end])
      {
        arr[end + 1] = arr[end];
        end--;
      }
      else
      {
        break;
      }
        }
    arr[end+1] = tmp;//因为走到了要求的数的前一个位置，那么他的后一位就是我们要插入的位置
  }
}

// 时间复杂度是O(N*logN);
void shellsort(int *arr,int n)
{
  //为了应对假如说使用插入排序的时候，那个数过于无序，如我们对一个逆序的数组，将他排序成顺序的，
  //一个一个的排时间复杂度过于大，太浪费了
  //所以我们可以使用中间间隔多的为一组进行排序，尽量把大的数字放到后面去，小的数字放到前面去，做到尽量有序
  //当间隔为1的时候就是直接插入排序
  int gap = n;
  int i;
  while (gap > 1)
  {
    gap = gap / 2;//如果gap是%2的话，最后gap会变成1，就是直接插入排序
      //假如我们是gap=gap/3的话，最后可能就不能变成1变成直接插入排序了,希尔排序内部的算法可以类比，直接插入排序，只不过把原来的1变成了gap
    for (i = 0; i < n - gap; i++)
    {
      int end = i;
      int tmp = arr[end + gap];
      while (end >= 0)
      {
        if (tmp < arr[end])
        {
          arr[end + gap] = arr[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      arr[end + gap] = tmp;
    }
  }
}

void selectsort(int *arr, int n)
{
  int begin = 0, end = n - 1;//
  while (begin < end)//begin和end分别从两边开始走，begin一方找到的是最小的那些数，end一方找到的是最大的一些数，当两者相遇或者刚好走到挨着的时候，就排序完成了
  {
    int max=begin, min=begin;
    for (int i = begin; i <= end; i++)
    {
      if (arr[i] < arr[begin])
      {
        min = i;//把最小的下标存到min里面
      }
      if (arr[i] > arr[begin])
      {
        max = i;//把最大的下标存到max里面
      }
    }
    swap(&arr[begin], &arr[min]);//处理完后把找到的最小下标和begin进行交换
//假如说第一个就是最大的，那交换之后，最大的就和最小的交换了
if(begin==maxi)
{
maxi=mini;
}
    swap(&arr[end], &arr[max]);//把最大下标和end进行交换
    begin++;
    end--;
  }
}

void quicksort(int *arr, int left,int right)
{
  if (left >= right)//当left>right就算是不存在，=就是只有一个值，都是不用排
  {
    return;
  }
  int begin = left, end = right;
  int pivot = begin;//把左边做一个坑
  int key = arr[begin];//把左边的数作为关键字，保存起来
  //一趟的排序
  while (begin < end)//左边做坑则右边先动
  {
    //右边找小，放到左边
    while (begin < end&&arr[end] >= key)//大于就--，小于才停下来//同时end走的必须是在begin右边，因为begin左边都是以及处理过的，所以end要大于begin
    {
      --end;
    }
    //找到的小的，放到左边，从而自己形成了新的坑位
    arr[pivot] = arr[end];
    pivot = end;
    //现在去找大
    while (begin<end &&arr[begin] <= key)//始终保证begin<end的条件
    {
      ++begin;
    }
    //大的放到左边的坑，自己形成新的坑位
    arr[pivot] = arr[begin];
    pivot = begin;
  }
  pivot = begin;//到达了中间的位置
  arr[pivot] = key;
  //[在left，right]
  //每次调用这函数都被分成3部分
  //[left,pivot-1],pivot,[pivot+1,right]//始终被分成了这三个部分，pivot是已经有序的了
  //只要让左子区间和右子区间有序，我们就有序了，我们就用到了分治递归的思想
  quicksort(arr, left, pivot - 1);
  quicksort(arr, pivot + 1, right);
}