DS：八大排序之归并排序、计数排序-阿里云开发者社区

创作不易，感谢三连支持！！

一、归并排序

1.1 思想

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

还有一个关键点就是：归并一定要先拷贝到一个新数组里面，再拷贝到原数组！！

1.2 递归实现归并排序

根据上面的思路，我们来实现代码：

void _MergeSort(int* a, int begin, int end, int* temp)
{
  if (begin == end)
    return;//设置递归返回条件
  int mid = (begin + end) / 2;
  //开始分解
  _MergeSort(a, begin, mid, temp);//左区间归并
  _MergeSort(a, mid+1, end, temp);//右区间归并
  //开始进行总归并
  int begin1 = begin, end1 = mid;//设置指针指向左区间
  int begin2 = mid + 1, end2 = end;//设置指针指向右区间
  int i = begin;//用来遍历拷贝数组
  while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
  {
    //谁小谁尾插
    if (a[begin1] < a[begin2])
      temp[i++] = a[begin1++];
    else
      temp[i++] = a[begin2++];
  }
  //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
  //以下两个while只会执行一个
  while (begin1 <= end1)
    temp[i++] = a[begin1++];
  while (begin2<=end2)
    temp[i++] = a[begin2++];
  //归并完成，将temp的数据拷贝回去
  memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//因为递归，拷贝的不一定就是从头开始的,左闭右闭个数要+1;
}
void MergeSort(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功，开始进行递归
  _MergeSort(a, 0, n - 1, temp);
}

要注意：递归的返回条件是begin==end！！因此归并排序每次拆分都是从中间拆分的，所以不可能会出现区间不存在的情况！！只有可能是区间只有一个元素的情况

1.3 非递归实现归并排序

怎么去思考非递归实现归并排序呢？？我们来画图理解：

那我们其实可以通过指针来实现各个子区间的有序,直接在原数组上建立两个指针

我们设置一个gap来分割区间

这里的问题就是，如何控制每次归并的子序列的范围？以及什么时候结束归并？

一、gap 控制几个为一组归并（gap一开始从1开始），则：

第一个子序列的起始是begin1 = i, end1 = i + gap -1;

第二个子序列的起始是begin2 = i+gap, end2 = i + 2 *gap - 1;

其中i是遍历一遍待排序的数组的下标，i从0开始。i每次应该跳2*gap步。

二、gap控制的是每次几个为一组我们一开始是1个，2个、4个、8个，显然是2的倍数，所以gap每次乘等2即可！也不能一直让gap*=2下去，gap不可能大于等于数组的长度，所以当超过数组的长度是结束！

代码实现：

void MergeSortNonR(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功
  int gap = 1;
  while (gap < n)
  {
    int j = 0;//用来遍历拷贝数组
    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;
      while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
      {
        //谁小谁尾插
        if (a[begin1] < a[begin2])
          temp[j++] = a[begin1++];
        else
          temp[j++] = a[begin2++];
      }
      //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
      //以下两个while只会执行一个
      while (begin1 <= end1)
        temp[j++] = a[begin1++];
      while (begin2 <= end2)
        temp[j++] = a[begin2++];
      //归并完成，将temp的数据拷贝回去
    }
    memcpy(a, temp, sizeof(int) * n);//一起拷贝回去
    gap *= 2;//设置条件
  }
}

这样对吗？测试一下

如果我们将数加到10个呢？？

越界了！！因为我们之前那个情况是8个元素恰好是2的次方，所以无论怎么分割再归并，都不会越界，所以这个时候我们要考虑边界情况！！

修正版本1：

void MergeSortNonR(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功
  int gap = 1;
  while (gap < n)
  {
    int j = 0;//用来遍历拷贝数组
    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;
      if (end1 >= n || begin2 >= n)
        break;
      if (end2 >= n)//修正
        end2 = n - 1;
      while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
      {
        //谁小谁尾插
        if (a[begin1] <= a[begin2])
          temp[j++] = a[begin1++];
        else
          temp[j++] = a[begin2++];
      }
      //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
      //以下两个while只会执行一个
      while (begin1 <= end1)
        temp[j++] = a[begin1++];
      while (begin2 <= end2)
        temp[j++] = a[begin2++];
      //归并一次，拷贝一次
      memcpy(a + i, temp + i, sizeof(int) * (end2-i+1));//一起拷贝回去
    }
    gap *= 2;//设置条件
  }
}

修改版本2：

void MergeSortNonR2(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功
  int gap = 1;
  while (gap < n)
  {
    int j = 0;//用来遍历拷贝数组
    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;
      if (end1 >= n)
      {
        end1 = n - 1;//修正end1
        //然后为了让begin2和end2不走循环，直接让他们区间不存在
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        //不存在区间
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      { //修正end2
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
      {
        //谁小谁尾插
        if (a[begin1] <= a[begin2])
          temp[j++] = a[begin1++];
        else
          temp[j++] = a[begin2++];
      }
      //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
      //以下两个while只会执行一个
      while (begin1 <= end1)
        temp[j++] = a[begin1++];
      while (begin2 <= end2)
        temp[j++] = a[begin2++];
    }
    gap *= 2;//设置条件
    memcpy(a, temp, sizeof(int) * n);
  }
}

1.4 归并排序的优化

假设我们的数据非常大，比如100万个数据，一开始的拆分效率是很高的，但是当数据变得很少的时候比如8个，这个时候再继续拆，效率其实很低的

我们当递归只剩大概10个元素的时候，停止递归，使用直接插入排序

void _MergeSort(int* a, int begin, int end, int* temp)
{
  if (begin == end)
    return;//设置递归返回条件
  if (end - begin + 1 < 10)
  {
    InsertSort(a+begin, end - begin + 1);//优化
    return;
  }
  int mid = (begin + end) / 2;
  //开始分解
  _MergeSort(a, begin, mid, temp);//左区间归并
  _MergeSort(a, mid+1, end, temp);//右区间归并
  //开始进行总归并
  int begin1 = begin, end1 = mid;//设置指针指向左区间
  int begin2 = mid + 1, end2 = end;//设置指针指向右区间
  int i = begin;//用来遍历拷贝数组
  while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
  {
    //谁小谁尾插
    if (a[begin1] < a[begin2])
      temp[i++] = a[begin1++];
    else
      temp[i++] = a[begin2++];
  }
  //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
  //以下两个while只会执行一个
  while (begin1 <= end1)
    temp[i++] = a[begin1++];
  while (begin2<=end2)
    temp[i++] = a[begin2++];
  //归并完成，将temp的数据拷贝回去
  memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//因为递归，拷贝的不一定就是从头开始的,左闭右闭个数要+1;
}
void MergeSort(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功，开始进行递归
  _MergeSort(a, 0, n - 1, temp);
}

1.5 复杂度分析

时间复杂度：O(N*logN)

他像二叉树的后序遍历，高度是logN，每一层合计归并时O(N)遍历一遍数组

空间复杂度：O(N)

N为辅助数组的长度，和原数组的长度一样！

二、计数排序

2.1 思想

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，是一种非比较排序！

步骤：

1、统计相同元素的出现次数

2、根据统计的结果将序列回收到原来的序列中

2.2 计数排序的实现

代码实现：

void CountSort(int* a, int n)
{
  int min = a[0], max = a[0];//根据最值来确定范围
  //遍历原数组找范围
  for (int 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* temp = (int*)calloc(range, sizeof(int));//因为要初始化0，所以用calloc
  //也可以先用malloc，然后用memset(temp,0,sizeof(int)*range)
  if (temp == NULL)
  {
    perror("calloc fail");
    exit(1);
  }
  //开辟成功后，开始遍历原数组计数
  for (int i = 0; i < n; i++)
    temp[a[i] - min]++;
  //遍历完后，计数也完成了，开始遍历计数数组，恢复原数组
  int k = 0;//用来恢复原数组
  for (int j = 0; j < range; j++)
    while (temp[j]--)//一直减到0，就会跳下一层循环，直到遍历完！！
      a[k++] = j + min;
}

2.3 复杂度分析

时间复杂度：O(MAX(N,范围))
空间复杂度：O(范围)

2.4 计数排序的缺陷

1，只适合范围相对集中的数据

2、只适用与整型，因为只有整型才能和下标建立联系

三、内排序和外排序

四、稳定性

五、八大排序对比

4.1 代码实现测速度

void TestOP()//测试速度
{
  srand((unsigned int)time(NULL));
  const int N = 10000;
  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);
  int* a8 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++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];
    a8[i] = a1[i];
  }
  //clock计入程序走到当前位置的时间
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  SelectSort(a3, N); 
  int end3 = clock();
  int begin4 = clock();
  BubbleSort(a4, N); 
  int end4 = clock();
  int begin5 = clock();
  HeapSort(a5, N);
  int end5 = clock();
  int begin6 = clock();
  QuickSort(a6, 0, N - 1);
  int end6 = clock();
  int begin7 = clock();
  MergeSort(a7, N);
  int end7 = clock();
  int begin8 = clock();
  CountSort(a8, N);
  int end8 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("BubbleSort:%d\n", end4 - begin4);
  printf("HeapSort:%d\n", end5 - begin5);
  printf("QuickSort:%d\n", end6 - begin6);
  printf("MergeSort:%d\n", end7 - begin7);
  printf("CountSort:%d\n", end8 - begin8);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
  free(a8);
}
int main()
{
  TestOP();
}

测试一下：

N=10000

N=100000

我们发现：

希尔排序、堆排序、快排、归并排、计数牌是一个量级的

N=10000000

直接插入排、选择排序、冒泡排序是一个量级的

4.2 复杂度稳定性比较

六、八大排序全部代码

建议大家把博主的有关八大排序的代码都看一下

主要是前三个文件，后面四个文件是为了快排的栈实现和队列实现准备的！！

6.1 sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
void ArrPrint(int* a, int n);//用来打印结果
void Swap(int* p1, int* p2);//进行交换
void InsertSort(int* a, int n);//直接插入排序
void ShellSort(int* a, int n);//希尔排序
void SelectSort(int* a, int n);//选择排序
void AdjustDown(int* a, int n, int parent);//向下调整算法
void HeapSort(int* a, int n);//堆排序
void BubbleSort(int* a, int n);//冒泡排序
int GetMidIndex(int* a, int left, int right);//快排优化——三数取中
int GetMidIndex2(int* a, int left, int right);//三数取中再优化
int PartSort1(int* a, int left, int right);//hoare基准排序
int PartSort2(int* a, int left, int right);//挖坑基准排序
int PartSort3(int* a, int left, int right);//前后指针基准排序
void QuickSort(int* a, int left, int right);//递归快排
void QuickSort2(int* a, int left, int right);//三路归并快排
void QuickSortNonR1(int* a, int left, int right);//栈实现非递归快排
void QuickSortNonR2(int* a, int left, int right);//队列实现非递归快排
void HeapSort(int* a, int n);//堆排序
void BubbleSort(int* a, int n);//冒泡排序
void _MergeSort(int* a, int begin, int end,int *temp);//归并排序的子函数（用来递归）
void MergeSort(int* a, int n);//归并排序
void MergeSortNonR(int* a, int n);//归并排序非递归
void MergeSortNonR2(int* a, int n);//归并排序非递归版本2
void CountSort(int* a, int n);//计数排序

6.2 sort.c

#include"Sort.h"
#include"Stack.h"
#include"Queue.h"
void ArrPrint(int* a, int n)
{
  for (int i = 0; i < n; i++)
    printf("%d ", a[i]);
}
void Swap(int* p1, int* p2)
{
  int temp = *p1;
  *p1 = *p2;
  *p2 = temp;
}
void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    int temp = a[i+1];
    while (end >= 0)
    {
      if (a[end] > temp)//如果前面的数比后面的数大，就前面元素插入到后面的位置
        a[end + 1] = a[end];
      else
        break;
      --end;
    }
    a[end + 1] = temp;//不写在循环里面，是避免end减成-1，此时说明新加入的牌是最小的，正好放在一开始的位置
  }
}
void ShellSort(int* a, int n)
{
  //gap>1  预排序
  //gap=1 直接插入排序
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;//这是为了保证gap最后一定为1
    for (int i = 0; i < n - gap; i++)
    {
      int end = i;
      int temp = a[i + gap];
      while (end >= 0)
      {
        if (a[end] > temp)//如果前面的数比后面的数大，就前面元素插入到后面的位置
          a[end + gap] = a[end];
        else
          break;
        end -= gap;
      }
      a[end + gap] = temp;
    }
  }
}
//
void SelectSort(int* a, int n)
{
  int left = 0; 
  int right = n - 1;
  while (left < right)
  {
    int min = left;
    int max = left;
    for (int i = left+1; i <= right; i++)
    {
    
      if (a[min] > a[i])
          min = i;
        if (a[max] < a[i])
        max = i;
    }
    //这里要考虑一种情况，就是如果最大的数恰好就在最左端，那么就会导致第二次swap换到后面的就不是最大的数而是最小的数了
    Swap(&a[min], &a[left]);
    //如果max和begin重叠，修正一下
    if (max == left)
      max = min;
    Swap(&a[max], &a[right]);
    left++;
    right--;
  }
}
int GetMidIndex(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[right] < a[left])
      return left;
    else
      return right;
  }
  else//a[left] >a[mid]
  {
    if (a[mid] > a[right])
      return mid;
    else if (a[right] > a[left])
      return left;
    else
      return right;
  }
}
int GetMidIndex2(int* a, int left, int right)
{
  int mid = left + (rand() % (right - left));
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
      return mid;
    else if (a[right] < a[left])
      return left;
    else
      return right;
  }
  else//a[left] >a[mid]
  {
    if (a[mid] > a[right])
      return mid;
    else if (a[right] > a[left])
      return left;
    else
      return right;
  }
}
int PartSort1(int* a, int left, int right)//hoare基准排序
{
  int mid=GetMidIndex(a, left, right);
  Swap(&a[mid], &a[left]);
  int keyi = left;
  while (left < right)
  {
  //右先找比key大的
    while (left < right&&a[right] >= a[keyi])
      right--;
  //左找比key小的
    while (left < right && a[left] <= a[keyi])
      left++;
    //找到后，就交换
    Swap(&a[left], &a[right]);
  }
  //此时相遇了，把相遇的位置和keyi的位置交换
  Swap(&a[left], &a[keyi]);
  return left;
}
int PartSort2(int* a, int left, int right)//挖坑基准排序
{
  int mid = GetMidIndex(a, left, right);
  Swap(&a[mid], &a[left]);
  int key = a[left];//记住key的值
  int hole = left;//开始挖坑
  while (left < right)
  {
    //右先找比key大的
    while (left < right && a[right] >= key)
      right--;
    //找到后，填坑，然后挖新坑
    a[hole] = a[right];
    hole = right;
    //左找比key小的
    while (left < right && a[left] <= key)
      left++;
    //找到后，填坑，然后挖新坑
    a[hole] = a[left];
    hole = left;
  }
  //此时相遇了，把key值放在坑里
  a[hole] = key;
  return hole;
}
int PartSort3(int* a, int left, int right) //前后指针基准排序
{
  int mid = GetMidIndex(a, left, right);
  Swap(&a[mid], &a[left]);
  int prev = left;
  int cur = left + 1;
  int keyi = left;
  while (cur <= right)//cur走出数组循环停止
  {
    //cur一直在走，如果遇到比keyi小的，就停下来等perv走一步后交换，再接着走
    if (a[cur] < a[keyi]&&++prev!=cur)
      Swap(&a[prev], &a[cur]);
    cur++;
  }
  //cur出去后，prev的值和keyi交换
  Swap(&a[keyi], &a[prev]);
  return prev;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
  int keyi = PartSort1(a, left, right);
  //根据基准值去分割区间，继续进行基准排序
  QuickSort(a, left, keyi - 1);
  QuickSort(a, keyi+1,right);
}
void QuickSort2(int* a, int left, int right)
{
  if (left >= right)
    return;
  int mid = GetMidIndex2(a, left, right);
  Swap(&a[mid], &a[left]);
  int phead = left;
  int pcur = left + 1;
  int ptail = right;
  int key = a[left];
  while (pcur <= ptail)
  {
    if (a[pcur] < key)
    {
      Swap(&a[pcur], &a[phead]);
      pcur++;
      phead++;
    }
    else if (a[pcur] > key)
    {
      Swap(&a[pcur], &a[ptail]);
      ptail--;
    }
    else//a[pcur] = key
      pcur++;
  }
  QuickSort2(a, left, phead - 1);
  QuickSort2(a, ptail+1,right);
}
void QuickSortNonR1(int* a, int left, int right)
{
  Stack st;
  StackInit(&st);
  //把区间压进去,一定要先压右区间！！
  StackPush(&st, right);
  StackPush(&st, left);
  while (!StackEmpty(&st))
  {
    //将数据弹出来进行进准计算
    int left = StackTop(&st);
    StackPop(&st);
    int right= StackTop(&st);
    StackPop(&st);
    //进行基准计算
    int keyi = PartSort3(a, left, right);
      //分割区间（left keyi-1）keyi（keyi+1，right）
    //如果对应的区间还能分割，就继续压,要注意要先压后面在压前面
    if (keyi + 1 < right)
    {
      StackPush(&st, right);
      StackPush(&st, keyi+1);
    }
    if (keyi - 1 > left)
    {
      StackPush(&st, keyi-1);
      StackPush(&st,left);
    }
  }
  //会一直到栈为空，此时就拍好序了！！
  StackDestory(&st);
}
void QuickSortNonR2(int* a, int left, int right)
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, left);
  QueuePush(&q, right);
  while (!QueueEmpty(&q))
  {
    int left = QueueFront(&q);
    QueuePop(&q);
    int right = QueueFront(&q);
    QueuePop(&q);
    int keyi = PartSort3(a, left, right);
    if (keyi - 1 > left)
    {
      QueuePush(&q, left);
      QueuePush(&q, keyi-1);
    }
    if (keyi + 1 <right)
    {
      QueuePush(&q, keyi +1);
      QueuePush(&q, right);
    }
  }
  QueueDestory(&q);
}
//向下调整算法
void AdjustDown(int* a, int n, int parent)//升序要建大堆
{
  int child = parent * 2 + 1;//假设左孩子比右孩子大
  while (child < n)
  {
  //如果假设错误，就认错
    if (child + 1 < n && a[child] < a[child + 1])
      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--;
  }
}
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
    //每一趟拍好一个，最后排完n-1个，最后一个数就没必要比了
  {
    int flag = 1;//假设有序
    for (int j = 0; j < n - i - 1; j++)//第一趟需要比较的n-1次，第二次需要比较n-2次……
      //所以结束条件跟着i变化
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
        flag = 0;//如果没有发生交换，说明不符合有序
      }
    }
    if (flag == 1)
      break;
  }
}
void _MergeSort(int* a, int begin, int end, int* temp)
{
  if (begin == end)
    return;//设置递归返回条件
  if (end - begin + 1 < 10)
  {
    InsertSort(a+begin, end - begin + 1);//优化
    return;
  }
  int mid = (begin + end) / 2;
  //开始分解
  _MergeSort(a, begin, mid, temp);//左区间归并
  _MergeSort(a, mid+1, end, temp);//右区间归并
  //开始进行总归并
  int begin1 = begin, end1 = mid;//设置指针指向左区间
  int begin2 = mid + 1, end2 = end;//设置指针指向右区间
  int i = begin;//用来遍历拷贝数组
  while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
  {
    //谁小谁尾插
    if (a[begin1] < a[begin2])
      temp[i++] = a[begin1++];
    else
      temp[i++] = a[begin2++];
  }
  //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
  //以下两个while只会执行一个
  while (begin1 <= end1)//等于才能保证稳定性！！
    temp[i++] = a[begin1++];
  while (begin2<=end2)
    temp[i++] = a[begin2++];
  //归并完成，将temp的数据拷贝回去
  memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//因为递归，拷贝的不一定就是从头开始的,左闭右闭个数要+1;
}
void MergeSort(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功，开始进行递归
  _MergeSort(a, 0, n - 1, temp);
}
void MergeSortNonR(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功
  int gap = 1;
  while (gap < n)
  {
    int j = 0;//用来遍历拷贝数组
    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;
      if (end1 >= n || begin2 >= n)
        break;
      if (end2 >= n)//修正
        end2 = n - 1;
      while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
      {
        //谁小谁尾插
        if (a[begin1] <= a[begin2])
          temp[j++] = a[begin1++];
        else
          temp[j++] = a[begin2++];
      }
      //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
      //以下两个while只会执行一个
      while (begin1 <= end1)
        temp[j++] = a[begin1++];
      while (begin2 <= end2)
        temp[j++] = a[begin2++];
      //归并一次，拷贝一次
      memcpy(a + i, temp + i, sizeof(int) * (end2-i+1));//一起拷贝回去
    }
    gap *= 2;//设置条件
  }
}
void MergeSortNonR2(int* a, int n)
{
  int* temp = (int*)malloc(sizeof(int) * n);
  if (temp == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  //开辟成功
  int gap = 1;
  while (gap < n)
  {
    int j = 0;//用来遍历拷贝数组
    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;
      if (end1 >= n)
      {
        end1 = n - 1;//修正end1
        //然后为了让begin2和end2不走循环，直接让他们区间不存在
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        //不存在区间
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      { //修正end2
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环
      {
        //谁小谁尾插
        if (a[begin1] <= a[begin2])
          temp[j++] = a[begin1++];
        else
          temp[j++] = a[begin2++];
      }
      //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了
      //以下两个while只会执行一个
      while (begin1 <= end1)
        temp[j++] = a[begin1++];
      while (begin2 <= end2)
        temp[j++] = a[begin2++];
    }
    gap *= 2;//设置条件
    memcpy(a, temp, sizeof(int) * n);
  }
}
void CountSort(int* a, int n)
{
  int min = a[0], max = a[0];//根据最值来确定范围
  //遍历原数组找范围
  for (int 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* temp = (int*)calloc(range, sizeof(int));//因为要初始化0，所以用calloc
  //也可以先用malloc，然后用memset(temp,0,sizeof(int)*range)
  if (temp == NULL)
  {
    perror("calloc fail");
    exit(1);
  }
  //开辟成功后，开始遍历原数组计数
  for (int i = 0; i < n; i++)
    temp[a[i] - min]++;
  //遍历完后，计数也完成了，开始遍历计数数组，恢复原数组
  int k = 0;//用来恢复原数组
  for (int j = 0; j < range; j++)
    while (temp[j]--)//一直减到0，就会跳下一层循环，直到遍历完！！
      a[k++] = j + min;
}

6.3 test.c

#include"Sort.h"
void TestOP()//测试速度
{
  srand((unsigned int)time(NULL));
  const int N = 1000000;
  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);
  int* a8 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++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];
    a8[i] = a1[i];
  }
  //clock计入程序走到当前位置的时间
  int begin1 = clock();
  //InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  //SelectSort(a3, N); 
  int end3 = clock();
  int begin4 = clock();
  //BubbleSort(a4, N); 
  int end4 = clock();
  int begin5 = clock();
  HeapSort(a5, N);
  int end5 = clock();
  int begin6 = clock();
  QuickSort(a6, 0, N - 1);
  int end6 = clock();
  int begin7 = clock();
  MergeSort(a7, N);
  int end7 = clock();
  int begin8 = clock();
  CountSort(a8, N);
  int end8 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("BubbleSort:%d\n", end4 - begin4);
  printf("HeapSort:%d\n", end5 - begin5);
  printf("QuickSort:%d\n", end6 - begin6);
  printf("MergeSort:%d\n", end7 - begin7);
  printf("CountSort:%d\n", end8 - begin8);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
  free(a8);
}
int main()
{
  TestOP();
}

6.4 stack.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{
  STDataType* a;
  int top;//栈顶
  int capacity;//栈容量
}Stack;
void StackInit(Stack* ps);//初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素个数
bool StackEmpty(Stack* ps);//检测栈是否为空，为空返回true
void StackDestory(Stack* ps);//销毁栈

6.5 stack.c

#include"Stack.h"
void StackInit(Stack* ps)
{
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType x)
{
  assert(ps);
  //判断是否需要扩容
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    STDataType* temp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
    if (temp == NULL)
    {
      perror("realloc fail");
      exit(1);
    }
    ps->a = temp;
    ps->capacity = newcapacity;
  }
  //压栈
  ps->a[ps->top++] = x;
}
void StackPop(Stack* ps)
{
  assert(ps);
  //如果栈为空，则没有删除的必要
  assert(!StackEmpty(ps));
  ps->top--;
}
STDataType StackTop(Stack* ps)
{
  assert(ps);
  //如果栈为空，不可能有栈顶元素
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
void StackDestory(Stack* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}

6.6 queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{
  QDatatype data;//存储数据
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;//指向队头，用于出队（头删）
  QNode* ptail;//指向队尾，用于入队（尾插）
  int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队（尾插）
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁

6.7 queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);//判断传的是不是空指针
  pq->phead = pq->ptail = NULL;
  pq->size = 0;//因为队列不像栈一样，有一个top表示栈顶元素的下标
  //所以如果我们想知道这个队列的有效数据个数，就必须遍历队列
  //由于其先进先出的特性，我们默认只能访问到头元素和尾元素
  //所以必须访问一个头元素，就出队列一次，这样才能实现遍历
  //但是这样的代价太大了，为了方便，我们直接用size
}
void QueuePush(Queue* pq, QDatatype x)
{
  assert(pq);
    //入队必须从队尾入！
  QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点
  if (newnode==NULL)//如果新节点申请失败，退出程序
  {
    perror("malloc fail");
  }
  //新节点创建成功，给新节点初始化一下
  newnode->data = x;
  newnode->next = NULL;
  //开始入队
  //如果直接尾插的话，由于会用到ptail->next,所以得考虑队列为空的情况
  if (pq->ptail== NULL)//如果为空，直接把让新节点成为phead和ptail
  {
    //按道理来说，如果ptail为空，phead也应该为空
    // 但是有可能会因为我们的误操作使得phead不为空，这个时候一般是我们写错的问题
    //所以使用assert来判断一下，有问题的话会及时返回错误信息
    assert(pq->phead == NULL);
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  //如果队列为空，没有删除的必要
  assert(!QueueEmpty(pq));
  //队列中的出队列相当于链表的头删
  //如果直接头删，那么如果队列只有一个有效数据的话，那么我们将phead的空间释放掉，但是没有将ptail给置空
  //这样会导致ptail成为一个野指针，所以我们需要考虑只有一个节点多个节点的情况
  if (pq->phead->next == NULL)//一个节点的情况,直接将这个节点释放并置空即可
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;//置空，防止野指针
  }
  else//多个节点的情况，直接头删
  {
    QNode* next = pq->phead->next;//临时指针记住下一个节点
    free(pq->phead);
    pq->phead = next;//让下一个节点成为新的头
  }
  pq->size--;
}
QDatatype QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//队列如果为空，则不可能找得到队列头元素
  //队列不为空的时候，直接返回phead指向的数据
  return pq->phead->data;
}
QDatatype QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//队列如果为空，则不可能找得到队尾元素
  //队列不为空的时候，直接返回ptail指向的数据
  return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
bool QueueEmpty(Queue* pq)//链表为空的情况，可以根据容量，也可以根据ptail==NULL&&phead==NULL
{
  assert(pq);
  return pq->ptail == NULL && pq->phead == NULL;
}
void QueueDestory(Queue* pq)
{
  assert(pq);//判断传的是不是空指针
  //要逐个节点释放
  QNode* pcur = pq->phead;
  while (pcur)
  {
    QNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

DS：八大排序之归并排序、计数排序

一、归并排序

1.1 思想

1.2 递归实现归并排序

1.3 非递归实现归并排序

1.4 归并排序的优化

1.5 复杂度分析

二、计数排序

2.1 思想

2.2 计数排序的实现

2.3 复杂度分析

2.4 计数排序的缺陷

三、内排序和外排序

四、稳定性

五、八大排序对比

4.1 代码实现测速度

4.2 复杂度稳定性比较

六、八大排序全部代码

6.1 sort.h

6.2 sort.c

6.3 test.c

6.4 stack.h

6.5 stack.c

6.6 queue.h

6.7 queue.c

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

DS：八大排序之归并排序、计数排序

一、归并排序

1.1 思想

1.2 递归实现归并排序

1.3 非递归实现归并排序

1.4 归并排序的优化

1.5 复杂度分析

二、计数排序

2.1 思想

2.2 计数排序的实现

2.3 复杂度分析

2.4 计数排序的缺陷

三、内排序和外排序

四、稳定性

五、八大排序对比

4.1 代码实现测速度

4.2 复杂度稳定性比较

六、八大排序全部代码

6.1 sort.h

6.2 sort.c

6.3 test.c

6.4 stack.h

6.5 stack.c

6.6 queue.h

6.7 queue.c

热门文章

最新文章

相关电子书