void shell_sort(int p[], int len)
{
 int i = 0, j = 0;
 int gap = len;
 
 do
 {
  gap = gap/3 + 1;
 
  for(i=gap; i<len; i++)
  {
   int tmp = p[i];
   
   /*可对比插入排序，插入排序即是 gap = 1的希尔排序*/
   for(j=i-gap; (j>=0) && (p[j] > tmp); j -= gap)
   {
    p[j+gap] = p[j];
   }
   
   p[j+gap] = tmp;
  }
 }while(gap > 1);

/*采用交换的方式，返回枢轴位置*/
int partition(int p[], int low, int high)
{
/直接采用第一元素做枢轴，有待优化。详见下文*/
 int pv = p[low];
 
 while(low < high)
 {
  while(low < high && p[high] >= pv)
  {
   high--;
  }
  swap(p, low, high);
 
  while(low < high && p[low] <= pv)
  {
   low++;
  }
  swap(p, low, high);
 }
 
 return low;
}


void q_sort(int p[], int low, int high)
{
 int pv = 0;
 
 if(low < high)
 {
  /*将传进来的序列一分为二，选出枢轴*/
  pv = partition(p, low, high);
 
  /*对低值序列进行递归排序*/
  q_sort(p, low, pv-1);
 
  /*对高值序列进行递归排序*/
  q_sort(p, pv+1, high);
 }
 
}

void quick_sort(int p[], int len)
{
 q_sort(p, 0, len-1);
}

void merge(int src[], int des[], int low, int mid, int high)
{
 int i = low;
 int j = mid + 1;
 int k = low;
 
 while( (i <= mid) && (j <= high) )
 {
  if(src[i] <= src[j])
  {
   des[k++] = src[i++];
  }
  else
  {
   des[k++] = src[j++];
  }
 }
 /*若 i 指向的序列还有剩余，则把剩余的搬过去*/
 while(i <= mid)
 {
  des[k++] = src[i++];
 }
 /*若 j 指向的序列还有剩余，则把剩余的搬过去*/
 while(j <= high)
 {
  des[k++] = src[j++];
 }
}

void m_sort(int src[], int des[], int low, int high, int max)
{
 /*划分到只有一个数据元素的情况
  递归划分、归并的终止条件*/
 if(low == high)
 {
  des[low] = src[low];
 }
 else
 {
  int mid = (low + high) / 2;
   
  /*辅助空间，每次递归都申请空间的话，消耗有点多*/
  int* space = (int*)malloc(sizeof(int) * max);
   
  if(space != NULL)
  {
   /*容易想到的在第一次划分后，一直是先对划分的左表进行划分、归并、排序*/
   m_sort(src, space, low, mid, max);
   
    /*之后对第一次划分后的右表进行划分、归并*/
   m_sort(src, space, mid+1, high, max);
   
   merge(space, des, low, mid, high);
  }
   
  free(space);
 }

}

void merge_sort(int p[], int len)
{
 /*将p数组中的无序序列 归并排序 到p数组中，
 中间过程需要使用辅助空间*/
 m_sort(p, p, 0, len-1, len);
}