手撕各种排序（下）-阿里云开发者社区

手撕各种排序（中）：https://developer.aliyun.com/article/1389401

🌙归并排序

这里讲述两种方法，一种是递归型另一种则是非递归

💫归并排序递归型

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：

void _MergeSort(int* a, int* tmp, int begin, int end)
{
  //尾小于头时
  if (end <= begin)
    return;
  //开始分割
  int mid = (end + begin) / 2;
  // [begin, mid][mid+1, end]
  _MergeSort(a, tmp, begin, mid);
  _MergeSort(a, tmp, mid + 1, end);
  //归并到tmp数据组，再拷贝回去
  //a->[begin, mid][mid+1, end]->tmp
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int index = begin;
  //开始拷贝
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[index++] = a[begin1++];
    }
    else
    {
      tmp[index++] = a[begin2++];
    }
  }
  //当第一段元素没有完全拷贝完就把剩下的拷贝进去
  while (begin1 <= end1)
  {
    tmp[index++] = a[begin1++];
  }
  //当第二段元素没有完全拷贝完就把剩下的拷贝进去
  while (begin2 <= end2)
  {
    tmp[index++] = a[begin2++];
  }
  //拷贝回原数组
  memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序（分路并归）
void MergeSort(int* a, int n)
{
  //开辟空间
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  //调用
  _MergeSort(a, tmp, 0, n - 1);
  //释放内存
  free(tmp);
}

💫归并排序非递归型

第一次当 gap 为 1 的时候，我们将距离为 1 的两个数组（其实就是两个元素为 1 的数）进行归并，得到了拥有两个元素的一个有序数组，然后通过循环将后面的元素全部用同样的方式归并。然后就得到了如上图所示蓝色表示的元素排布。同时我们在将这一步骤之后的数组拷贝回到原数组。在进行接下来的操作（这里的意思和上递归的是一样的）。接着每次将 gap 的值增加 2 倍，直到 gap 的值不小于 n 结束归并。这个过程我们将其称为小区间优化。

//归并排序（非递归）
void MergeSortNonR(int* a, int n)
{
  //开辟空间
  int* tmp = (int*)malloc(sizeof(int) * n);
  //判断
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  int gap = 1;
  while (gap < n)
  {
    for (int i = 0; i < n; i += 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
      // [begin1,end1] [begin2,end2] 归并
      // 如果第二组不存在，这一组不用归并了
      if (begin2 >= n)
      {
        break;
      }
      // 如果第二组的右边界越界，修正一下
      if (end2 >= n)
      {
        end2 = n - 1;
      }
      //printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
      int index = i;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[index++] = a[begin1++];
        }
        else
        {
          tmp[index++] = a[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[index++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[index++] = a[begin2++];
      }
      // 拷贝回原数组
      memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
    }
    printf("\n");
    gap *= 2;
  }
  free(tmp);
}

🌙计数排序

计数排序的朴素方法步骤：

1、从无序数组中取出最大值max，新建一个长度为max+1的数组。

2、遍历无序数组，取其中元素作为新建数组的索引，存在一个则新数组该索引所在的值自增。

3、遍历新数组，当存在不为0的元素，取该元素的索引放入最终数组，并且该元素自减，直到为0，返回最终数组。

上代码：

//计数排序测试
void CountSort(int* a, int n)
{
  //找最大值和最小值
  int min = a[0], max = a[0];
  for (size_t i = 0; i < n; i++)
  {
    if (a[i] < min)
      min = a[i];
    if (a[i] > max)
      max = a[i];
  }
  //找出区间
  int range = max - min + 1;
  //开辟（区间）
  int* count = (int*)malloc(sizeof(int) * range);
  printf("range:%d\n", range);
  //判断
  if (count == NULL)
  {
    perror("malloc fail");
    return;
  }
  //计入数字的个数
  memset(count, 0, sizeof(int) * range);
  // 统计数据出现次数
  for (int i = 0; i < n; i++)
  {
    count[a[i] - min]++;
  }
  //排序
  int j = 0;
  for (int i = 0; i < range; i++)
  {
    while (count[i]--)
    {
      a[j++] = i + min;
    }
  }
}

⭐总结

咱看看每种排序的复杂度和稳定性。

🌠Sort.h代码

#include<stdio.h>
//打印数据
void PrintArray(int* a, int n);
//冒泡排序测试
void BubbleSort(int* a, int n);
//插入排序测试
void InsertSort(int* a, int n);
//希尔排序测试
void ShellSort(int* a, int n);
//选择排序测试
void SelectSort(int* a, int n);
//堆排序测试
void HeapSort(int* a, int n);
//快排测试
void QuickSort1(int* a, int begin, int end);
void QuickSort2(int* a, int begin, int end);
//快排非递归测试
void QuickSortNonR(int* a, int begin, int end);
//归并排序测试
void MergeSort(int* a, int n);
//归并排序（非递归）测试
void MergeSortNonR(int* a, int n);
//计数排序测试
void CountSort(int* a, int n);

🌠Test.c代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<time.h>
#include<stdlib.h>
#include"Sort.h"
#include"Stack.h"
//希尔排序测试
void TestShellSort()
{
  int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
  ShellSort(a, sizeof(a) / sizeof(int));
  PrintArray(a, sizeof(a) / sizeof(int));
}
//冒泡排序测试
void TestBubbleSort()
{
  int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
  BubbleSort(a, sizeof(a) / sizeof(int));
  PrintArray(a, sizeof(a) / sizeof(int));
}
//堆排序测试
void TestHeapSort()
{
  int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
  HeapSort(a, sizeof(a) / sizeof(int));
  PrintArray(a, sizeof(a) / sizeof(int));
}
//选择排序测试
void TestSelectSort()
{
  int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
  SelectSort(a, sizeof(a) / sizeof(int));
  PrintArray(a, sizeof(a) / sizeof(int));
}
//测试代码
void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  int* a7 = (int*)malloc(sizeof(int) * N);
  for (int i = N - 1; i >= 0; --i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
    a7[i] = a1[i];
  }
  int begin1 = clock();
  //插入排序
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  //希尔排序测试
  ShellSort(a2, N);
  int end2 = clock();
  int begin7 = clock();
  //冒泡排序测试
  BubbleSort(a7, N);
  int end7 = clock();
  int begin3 = clock();
  //选择排序测试
  SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  //堆排序测试
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  //快排测试
  //QuickSort(a5, 0, N - 1);
  int end5 = clock();
  int begin6 = clock();
  //MergeSort(a6, N);
  //计数排序测试
  //CountSort(a6, N);
  int end6 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("BubbleSort:%d\n", end7 - begin7);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  printf("MergeSort:%d\n", end6 - begin6);
  printf("CountSort:%d\n", end6 - begin6);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
}
int main()
{
  TestOP();
  //TestBubbleSort();
  //TestHeapSort();
  //TestSelectSort();
  //TestQuickSort();
  //TestMergeSort();
  //TestCountSort();
  //printf("%d\n", Func(100000));
  return 0;
}

🌠Sort.c代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"Stack.h"
//交换函数
void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
//打印数据
void PrintArray(int* a, int n)
{
  //循环
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
}
//冒泡排序测试
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int exchange = 0;
    for (int j = 1; j < n - i; j++)
    {
      if (a[i - 1] > a[i])
      {
        //这里是一个交换函数
        Swap(&a[i - 1], &a[i]);
        exchange = 1;
      }
    }
    //这里进行一趟有序时，直接跳出循环
    if (exchange == 0)
    {
      break;
    }
  }
}
//插入排序
void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    int tmp = a[end + 1];
    //一个元素进行插入
    while (end >= 0)
    {
      if (tmp < a[end])
      {
        a[end + 1] = a[end];
      }
      else
      {
        break;
      }
      --end;
    }
    //最后把插入的元素赋值回去
    a[end + 1] = tmp;
  }
}
//希尔排序测试
void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)
  {
    //间隔gap的元素进行排序
    gap = gap / 3 + 1;
    //本质上是插入排序
    for (int i = 0; i < n - gap; ++i)
    {
      int end = i;
      int tmp = a[end + gap];
      //一个元素进行插入
      while (end >= 0)
      {
        if (tmp < a[end])
        {
          a[end + gap] = a[end];
          end = end - gap;
        }
        else
        {
          break;
        }
      }
      //最后把插入的元素赋值回去
      a[end + gap] = tmp;
    }
  }
}
//void ShellSort(int* a, int n)
//{
  /*int gap = 3;
  for (int j = 0; j < gap; j++)
  {
    for (int i = j; i < n - gap; i += gap)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (tmp < a[end])
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  } */
//选择排序测试
void SelectSort(int* a, int n)
{
  //初始化第一个元素 和 最后一个元素
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    //选出最大值和最小值
    int mini = begin, maxi = begin;
    for (int i = begin + 1; i <= end; i++)
    {
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    //最小值和最初的元素交换
    Swap(&a[begin], &a[mini]);
    //如果max被换走就需要重新赋值
    if (maxi == begin)
    {
      maxi = mini;
    }
    //最大值和最末的元素交换
    Swap(&a[end], &a[maxi]);
    ++begin;
    --end;
  }
}
//堆排序测试
//实现向下调整建大堆
void AdjustDown(int* a, int n, int parent)
{
  //孩子和父亲的关系 
  int child = parent * 2 + 1;
  while (child < n)
  {
    //找出小的那个孩子
    if (child + 1 < n && a[child + 1] < a[child])
    {
      ++child;
    }
    //实现向下调整元素
    if (a[child] < a[parent])
    {
      //元素交换
      Swap(&a[child], &a[parent]);
      // 继续往下调整
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//堆排序测试
void HeapSort(int* a, int n)
{
  //向下调整建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    //实现向下调整建大堆
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    //元素交换
    Swap(&a[0], &a[end]);
    //实现向下调整建大堆
    AdjustDown(a, end, 0);
    --end;
  }
}
//三数取中 （找出中间值）
int GetMidi(int* a, int left, int right)
{
  //中间值
  int mid = (left + right) / 2;
  //三个数比较找出中间值
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
// 右边找小，左边找大，交换，把左边的值跟a[keyi]交换
int PartSort1(int* a, int left, int right)
{
  //找中间值（相对）
  int midi = GetMidi(a, left, right);
  //把最左边（相对）跟中间值（相对）换
  Swap(&a[left], &a[midi]);
  //定位最左边（相对）
  int keyi = left;
  while (left < right)
  {
    //找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    //左右交换
    Swap(&a[left], &a[right]);
  }
  //此时左边走到中间了，开始交换
  Swap(&a[keyi], &a[left]);
  //返回
  return left;
};
//挖坑法
int PartSort2(int* a, int left, int right)
{
  //找中间值（相对）
  int midi = GetMidi(a, left, right);
  //把最左边（相对）跟中间值（相对）换
  Swap(&a[left], &a[midi]);
  //定位最左边（相对）
  int key = a[left];
  //保存key值以后，左边形成第一个坑
  int hole = left;
  while (left < right)
  {
    //右边先走，找小，填到左边的坑，右边形成新的坑位
    while (left < right && a[right] >= key)
    {
      --right;
    }
    a[hole] = a[right];
    hole = right;
    //左边再走，找大，填到右边的坑，左边形成新的坑位
    while (left < right && a[left] <= key)
    {
      ++left;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  return hole;
}
//前后指针
int PartSort3(int* a, int left, int right)
{
  //找中间值（相对）
  int midi = GetMidi(a, left, right);
  //把最左边（相对）跟中间值（相对）换
  Swap(&a[left], &a[midi]);
  //定义指针开头
  int prev = left;
  //定义指针开头后一个
  int cur = prev + 1;
  int keyi = left;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    ++cur;
  }
  //交换
  Swap(&a[prev], &a[keyi]);
  return prev;
}
//快排测试一
void QuickSort1(int* a, int begin, int end)
{
  if (begin >= end)
    return;
  //小区间优化，小区间不再递归分割排序，降低递归次数
  //当元素小于10时，采用插入排序
  if ((end - begin + 1) > 10)
  {
    //找值
    int keyi = PartSort3(a, begin, end);
    // [begin, keyi-1] keyi [keyi+1, end]
    QuickSort1(a, begin, keyi - 1);
    QuickSort1(a, keyi + 1, end);
  }
  else
  {
    //插入排序
    InsertSort(a + begin, end - begin + 1);
  }
}
//快排测试二
void QuickSort2(int* a, int begin, int end)
{
  if (begin >= end)
    return;
  //调用
  int keyi = PartSort3(a, begin, end);
  //[begin, keyi-1] keyi [keyi+1, end]
  QuickSort2(a, begin, keyi - 1);
  QuickSort2(a, keyi + 1, end);
}
//快排非递归（采用栈的形式）（先进后出）
void QuickSortNonR(int* a, int begin, int end)
{
  //定义
  ST st;
  //初始化
  STInit(&st);
  //添加元素
  STPush(&st, end);
  STPush(&st, begin);
  while (!STEmpty(&st))
  {
    //剥离元素  让left取先入但是后出的元素（区间的左边）
    int left = STTop(&st);
    STPop(&st);
    //让right取栈顶元素（是我们后入的区间的右边）
    int right = STTop(&st);
    STPop(&st);
    // 右边找小，左边找大，交换，把左边的值跟a[keyi]交换
    int keyi = PartSort1(a, left, right);
    //分割成段 
    // [lefy,keyi-1] keyi [keyi+1, right]
    if (keyi + 1 < right)
    {
      //添加元素
      STPush(&st, right);
      STPush(&st, keyi + 1);
    }
    if (left < keyi - 1)
    {
      //添加元素
      STPush(&st, keyi - 1);
      STPush(&st, left);
    }
  }
  //销毁
  STDestroy(&st);
}
void _MergeSort(int* a, int* tmp, int begin, int end)
{
  //尾小于头时
  if (end <= begin)
    return;
  //开始分割
  int mid = (end + begin) / 2;
  // [begin, mid][mid+1, end]
  _MergeSort(a, tmp, begin, mid);
  _MergeSort(a, tmp, mid + 1, end);
  //归并到tmp数据组，再拷贝回去
  //a->[begin, mid][mid+1, end]->tmp
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int index = begin;
  //开始拷贝
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[index++] = a[begin1++];
    }
    else
    {
      tmp[index++] = a[begin2++];
    }
  }
  //当第一段元素没有完全拷贝完就把剩下的拷贝进去
  while (begin1 <= end1)
  {
    tmp[index++] = a[begin1++];
  }
  //当第二段元素没有完全拷贝完就把剩下的拷贝进去
  while (begin2 <= end2)
  {
    tmp[index++] = a[begin2++];
  }
  //拷贝回原数组
  memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序（分路并归）
void MergeSort(int* a, int n)
{
  //开辟空间
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  //调用
  _MergeSort(a, tmp, 0, n - 1);
  //释放内存
  free(tmp);
}
//归并排序（非递归）
void MergeSortNonR(int* a, int n)
{
  //开辟空间
  int* tmp = (int*)malloc(sizeof(int) * n);
  //判断
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  int gap = 1;
  while (gap < n)
  {
    for (int i = 0; i < n; i += 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
      // [begin1,end1] [begin2,end2] 归并
      // 如果第二组不存在，这一组不用归并了
      if (begin2 >= n)
      {
        break;
      }
      // 如果第二组的右边界越界，修正一下
      if (end2 >= n)
      {
        end2 = n - 1;
      }
      //printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
      int index = i;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[index++] = a[begin1++];
        }
        else
        {
          tmp[index++] = a[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[index++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[index++] = a[begin2++];
      }
      // 拷贝回原数组
      memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
    }
    printf("\n");
    gap *= 2;
  }
  free(tmp);
}
//计数排序测试
void CountSort(int* a, int n)
{
  //找最大值和最小值
  int min = a[0], max = a[0];
  for (size_t i = 0; i < n; i++)
  {
    if (a[i] < min)
      min = a[i];
    if (a[i] > max)
      max = a[i];
  }
  //找出区间
  int range = max - min + 1;
  //开辟（区间）
  int* count = (int*)malloc(sizeof(int) * range);
  printf("range:%d\n", range);
  //判断
  if (count == NULL)
  {
    perror("malloc fail");
    return;
  }
  //计入数字的个数
  memset(count, 0, sizeof(int) * range);
  // 统计数据出现次数
  for (int i = 0; i < n; i++)
  {
    count[a[i] - min]++;
  }
  //排序
  int j = 0;
  for (int i = 0; i < range; i++)
  {
    while (count[i]--)
    {
      a[j++] = i + min;
    }
  }
}

🌟结束语

今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

手撕各种排序（下）