大数据管理的重要思想和算法总结----排序（下）

//Hoare版本的单趟快排
int PartSort1(int* arr1, int left,int right)//先进行单趟快排,这里对应的left和right都是下标，注意对于让其同时自动跳动位置的情况，使用循环去处理是最好的，而不是用if语句，那样适用于变化相同的情况
{
  int midi = GetMidi(arr1, left, right);
  swap(&arr1[left], &arr1[midi]);//取到中间数据的下标后，将其与left交换，即可让key的值为中间值，这样的话进行快速排序的速度就会避免n^2的情况了
  int key = left;//注意这里要操作key的下标
  while (left < right)//这便是单趟循环的过程
  {
    while (left<right&&arr1[right]>=arr1[key])//利用循环去处理这个过程，而不是利用if语句,要加上等于的情况，否则程序会死循环一直不动
    {
      right--;
    }
    while (left<right&&arr1[left]<=arr1[key])//同样加上等于防止程序死循环.加上left<right是为了防止，假设right访问的每一个数都比key大于等于，则这个循环会一直持续到遍历结束，然后越界，同样left也是同理，所以我们要控制left<right以保证访问不会越界
    {//即极端最坏情况下他们两个相遇就不循环了
      left++;
    }
      swap(&arr1[right], &arr1[left]);//跳出循环就交换
  }
  swap(&arr1[left], &arr1[key]);//相遇就跟key交换
  return left;//返回key下标方便下一步分治
}

/挖坑法版本的单趟快排
int PartSort2(int* arr1, int left, int right)//注意，坑位的值是可以忽略的，所以这里不要用交换，直接赋值覆盖即可，我写的交换很容易出现错误，倘若赋值为0就会出错
{
  int midi = GetMidi(arr1, left, right);
  swap(&arr1[left], &arr1[midi]); //注意不要赋值为0，除非你保证再调整一次指针，交换使用0会有bug，但假如是直接覆盖就不会出现这种情况
  int key = arr1[left];
  int hole = left;//注意，这里不能赋值为0，那样的话就没法递归了，直接写死了
  while (left < right)
  {
    while (left<right && arr1[right] >= key)
    {
      right--;
    }
    arr1[hole] = arr1[right];
    hole = right;
    while (left < right && arr1[left] <= key)
    {
      left++;
    }
    arr1[hole] = arr1[left];
    hole = left;
  }
  arr1[hole]=key;//循环结束后把数值放入坑位
  return left;
}

int midi = GetMidi(arr1, left, right);
  swap(&arr1[left], &arr1[midi]);

int GetMidi(int* arr1, int left, int right)//三数取中法函数，防止遇到全数据有序的情况快排受不了，由于有序。故取中值基本上就是最中间的数据，我们用三数取中的方法取的就是整个数据中的中间数据
{//注意啊，这里操作的是下标而不是具体的数值，但比较的是数值
  int mid = (left + right) / 2;
  if (arr1[left] > arr1[mid])  
  {
    if (arr1[right] < arr1[mid])
    {
      return mid;
    }
    else if (arr1[right] > arr1[left])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else//arr1[left]<arr1[mid]
  {
    if (arr1[mid] < arr1[right])
    {
      return mid;
    }
    else if (arr1[right] < arr1[left])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  //这里还是用逻辑判断法吧，假如要用比较函数需要在堆区开辟大量空间，会让堆区内存占满，所以还是用逻辑判断法比较好
}

//前后双指针版本的单趟快排
int PartSort3(int* arr1, int left, int right)
{
   int midi=GetMidi(arr1,left,right);
   Swap(&arr1[left],&arr1[midi]);
  int key = left;
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    if (arr1[cur] < arr1[key]&&++prev!=cur)//如果prev=cur就没必要交换了，这样可以优化运算速度,这里很细节，在判断的逻辑里对prev先++，哪怕判断为空，这是为了预防prev与cur初始的位置发生重合的情况，比如遇到两个数据都小于key，就会导致prev的移动后与cur的位置重合，此时不交换
    {
      swap(&arr1[++prev], &arr1[cur]);
    }
    cur++;
  }
  swap(&arr1[key], &arr1[prev]);
  return prev;
}

void QuickSort(int* arr1, int left,int right)//快速排序函数
{//我认为思路同直接选择排序差不多，都是直接操作下标来操作，其思路有点类似二叉树递归的思想，直接查找key，查找key左侧，查找key右侧这样的思路进行
  if (left >= right)//注意，结束传递开始回归的情况有两种，第一种为只有一个元素了，此时left==right了，第二种情况是，存在递归的过程中比如left 0,right 1的情况，此时右边的递归left=2而right仍为1，这样的话就存在left大于right的情况，所以我们返回的条件是left>=right
  {
    return;
  }
  if (right - left > 10)//注意这里我加上这句话的原因，考虑到递归快排越向下递归的次数越多，但对于10个数据来说，其排序已经基本确定好了，对于这种小范围的排序，直接插入排序的效率更高且可以省略更多大量的递归排序。
  {
        int keyi = PartSort3(arr1, left, right);
      QuickSort(arr1, left, keyi-1);//注意这里的思路，先递归左边，再递归右边，仿照二叉树前序遍历的方法去思考即可
      QuickSort(arr1, keyi+1, right);
  }
  else
  {
    InsertSort(arr1 + left, right - left + 1);///当数据量小于10的时候，直接用直接插入排序即可，传参注意第二个参数是个数，right-left后要加上1，这样才表示个数
  }//注意，一定要加else，否则这里会重复运算直接插入排序，效率十分低，要明确，这里是一种选择，直接插入排序不是必须要执行的，只有到小于等于10的情况下才执行。
}

void QuickSortNonR(int*arr1,int left,int right)//快速排序的非递归写法（辅助栈实现）
{
  ST st;
  STInit(&st);
  STPush(&st,right);
  STPush(&st, left);//首先把首位区间存进去，注意栈的特点，先进后出，所以我们进栈和出栈的顺序要对称
  while (!STEmpty(&st))
  {
    int begin = STTop(&st);//先获取左区间
    STPop(&st);//注意，一定要删除，这样方便左区间向右区间转化
    int end = STTop(&st);//再获取右区间
    STPop(&st);//这里要把左区间和右区间存起来，因为后续就要删除
    int keyi = PartSort3(arr1, begin, end);
    if (keyi+1 < end)//先入栈右区间
    {
      STPush(&st, end);
      STPush(&st, keyi +1);
    }
    if (keyi - 1 > begin)//跟递归的返回条件一样，不符合的数据就自动不入栈了，然后数据不入栈，就如同左访问结束去访问右边一样
    {
      STPush(&st, keyi - 1);
      STPush(&st, begin);//再入栈左区间，这样数据出栈的时候就是先出左区间，再去右区间
    }
  }
  STDestroy(&st);
}

void _MergeSort(int* arr1,int left,int right,int* tmp)//归并的分割子函数.传入tmp数组是用来进行归并过程的
{   
  if (left >= right)
  {
    return;
  }
  int mid = (left + right) / 2;
  _MergeSort(arr1,left, mid,tmp);//先分隔左边
  _MergeSort(arr1, mid+1,right,tmp);
  //归并到tmp数据组，然后将其拷贝回去
  int begin1 = left;
  int end1 = mid;
  int begin2 = mid + 1;
  int end2 = right;
  int newbegin = left;//注意，运用递归，要用递归的思路展开
  while (begin1 <= end1 && begin2 <= end2)//对数据继续归并排序进入tmp数据组并且排好序放入
  {
    if (arr1[begin1] <= arr1[begin2])//在这里加上一个等号，这样的话归排序就变成稳定的了，倘若不加的话归并排序是不稳定的
    {
      tmp[newbegin++] = arr1[begin1++];
    }
    else //注意，这里不要光用if,因为光用if会导致一旦遇到相等的情况，指针不会向后走，循环就会一直进行，这里是关于if语句的理解不到位，这里要注意，别弄错了
    {
      tmp[newbegin++] = arr1[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[newbegin++] = arr1[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[newbegin++] = arr1[begin2++];
  }
  memcpy(arr1 + left, tmp + left, (right - left + 1) * sizeof(int));//最后要把数据再从tmp拷贝回去到原字符串中，注意，这里传arr1+left和tmp+left是因为防止其tmp本身的数据覆盖造成乱序，让其对应好位置开始归并排序存入tmp中，也就是说，拷贝不一定是从0开始的，准确来说是从begin开始的
}
void MergeSort(int* arr1, int sz)//归并排序，核心思想是递归和两个数组的插入排序
{
  int* tmp = (int*)malloc(sizeof(int) * sz);//首先定义一个数组用来存储数据
  if (tmp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //归并排序，需要我们分割数组的位置，所以这里需要一个子函数用来递归
  _MergeSort(arr1, 0, sz - 1, tmp);
  free(tmp);
  tmp = NULL;
}

void MergeSortNonR(int* arr1, int sz)//归并排序非递归写法
{
  int* tmp = (int*)malloc(sizeof(int) * sz);//首先定义一个数组用来存储数据
  if (tmp== NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  int gap = 1;//定义一个长度值，控制gap使其变成11归 22归 44归这样的扩大递归的形式
  while(gap <sz)
  {
    for (int i = 0; i < sz; i += 2*gap)
    {
      int begin1 = i;
      int end1 = i + gap-1;//别忘了减一
      int begin2 = i + gap;
      int end2 = i + 2 * gap-1;//别忘了减一
      int newbegin = i;
      //如果第二组不存在，这一组就不用归并了
      if (begin2 >= sz)//注意，等于sz也算越界，千万别忘了，而且注意这里为什么我只判断begin2就好了，因为begin2倘若越界了，则end2一定越界，而end1与begin2差一，假设begin2恰好等于sz，则此时的end1正好在最后一个位置，这个时候直接跳出，排序也已经完成了，故直接break是合理的。
      {
        break;
      }
      //如果第二组右边界越界，修正一下即可
      if (end2 >= sz)
      {
        end2 = sz - 1;//将end2修正到sz-1，让其与前面的数字归并排序，这样不会越界了
      }
      while (begin1 <= end1 && begin2 <= end2)//对数据继续归并排序进入tmp数据组并且排好序放入
      {
        if (arr1[begin1] < arr1[begin2])
        {
          tmp[newbegin++] = arr1[begin1++];
        }
        else //注意，这里不要光用if,因为光用if会导致一旦遇到重复情况，指针不会向后走，循环就会一直进行，这里是关于if语句的理解不到位，这里要注意，别弄错了
        {
          tmp[newbegin++] = arr1[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[newbegin++] = arr1[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[newbegin++] = arr1[begin2++];
      }
      memcpy(arr1 + i,tmp +i,(end2-i+1)*sizeof(int));//注意这里的拷贝细节，由于begin1一直会变，但begin1的初始值是等于i的，故我们直接让其利用i来计数即可，比如这里,对于数据个数来说，就是从end2到i+1即为数据个数，两个数组的头从arr1+1和tmp+i开始即可。
    }//注意，数组下标，左闭右闭形式，下标相减后要加一才是对应的元素个数
    gap *= 2;//使递归开始11 22 44递归形式
  }
  free(tmp);
  tmp = NULL;
  //但目前只能处理偶数个情况，对于奇数要设置特殊情况去判断
}

if (begin2 >= sz)//注意，等于sz也算越界，千万别忘了，而且注意这里为什么我只判断begin2就好了，因为begin2倘若越界了，则end2一定越界，而end1与begin2差一，假设begin2恰好等于sz，则此时的end1正好在最后一个位置，这个时候直接跳出，排序也已经完成了，故直接break是合理的。
      {
        break;
      }
      //如果第二组右边界越界，修正一下即可
      if (end2 >= sz)
      {
        end2 = sz - 1;//将end2修正到sz-1，让其与前面的数字归并排序，这样不会越界了
      }

memcpy(arr1 + i,tmp +i,(end2-i+1)*sizeof(int));

void CountSort(int* arr1, int sz)//计数排序
{
  int max = arr1[0];
  int min = arr1[0];
  int i = 0;
  for (i = 0; i < sz; i++)//首先对数据进行最大值最小值的取得，从而确定相对映射的数值和开辟的动态数组的大小
  {
    if (arr1[i] > max)
    {
      max = arr1[i];
    }
    if (arr1[i] < min)
    {
      min = arr1[i];
    }
  }
  int range = max - min + 1;
  int* count = (int*)calloc(sizeof(int), range);//动态开辟一段数组且初始化每一个元素为0，这里使用memmset也可以，但我这里使用了calloc直接开辟并初始化了。
  if (count == NULL)
  {
    perror("calloc failed");
    exit(-1);
  }
  for (i = 0; i < sz; i++)
  {
    count[arr1[i] - min]++;
  }
  int j = 0;
  for (i = 0; i < range; i++)//注意这里，别搞错了，用range大小开辟的数组当然要用range遍历，这个range和sz可是不相同的，别理解错了。
  {
    while (count[i]--)
    {
      arr1[j++] = i + min;
    }
  }
  free(count);
  count = NULL;
}