【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)

简介: 【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)

归并排序

归并过程如下:




 代码实现(递归)


//时间复杂度:O(N*logN)
//空间复杂度:O(N)
void _MergeSort(int* a,int begin, int end,int* tmp)
{
  if (begin >= end)
  return;
  int mid = (begin + end) / 2;
  //[begin,mid][mid+1,end]
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid+1, end, tmp);
  //[begin,mid][mid+1,end]归并
  int begin1 = begin, end1 = mid;
  int begin2 = mid+1, end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
  if (a[begin1] <= a[begin2])
  {
    tmp[i++] = a[begin1++];
  }
  else
  {
    tmp[i++] = a[begin2++];
  }
  }
  while (begin1 <= end1)
  {
  tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
  tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
  perror("malloc fail");
  return;
  }
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}


分析:因为是使用递归实现,开始时需要创建一个新的数组,且递归需要一个区间,因此我们要另外定义一个函数来实现递归。递归的过程跟二叉树的后序遍历类似,应当注意递归的取值范围和结束条件。归并时,我们把左右两个区间的数从头开始比较,小的就放到tmp数组中。第一个while循环的结束条件是直到某一边的数全部放到tmp就结束。然后就把另一个区间的数,全部依次放入tmp数组中,最后再把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 (end1 >= n || begin2 >= n)
    {
    break;
    }
    if (end2 >= n)
    {
    end2 = n - 1;
    }
    int j = begin1;
    while (begin1 <= end1 && begin2 <= end2)
    {
    if (a[begin1] <= a[begin2])
    {
      tmp[j++] = a[begin1++];
    }
    else
    {
      tmp[j++] = a[begin2++];
    }
    }
    while (begin1 <= end1)
    {
    tmp[j++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
    tmp[j++] = a[begin2++];
    }
    memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
  }
  gap *= 2;
  }
  free(tmp);
}


分析:gap表示每组数的个数。非递归的实现是,开始每组一个数,两两合一,后面比较的过程和递归一样。不过需要注意越界的问题,当end1或者begin2>=n时,就已经越界,这时候就结束循环。当只是end2>=n时,前面数据没有越界,只需要把end2改成n-1即可。一趟归并结束后,gap变为2倍,进行后面的归并,直到gap>=n就停止。


计数排序(非比较排序)

代码实现

void CountSort(int* a, int n)
{
  int min = a[0], max = a[0];
  for (int i = 1; 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*)calloc(range, sizeof(int));
  if (count == NULL)
  {
  perror("calloc fail");
  return;
  }
  //统计次数
  for (int i = 0; i < n; i++)
  {
  count[a[i] - min]++;
  }
  //排序
  int i = 0;
  for (int j = 0; j < range; j++)
  {
  while (count[j]--)
  {
    a[i++] = j + min;
  }
  }
}


分析:计数排序主要有两步:


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

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

计数排序需要我们新创建一个统计数组,按理来说,数组下标就可以用来当作统计的数,该位置就来存放该数出现的次数。但是,如果要排序的数是从一千多开始的,这样前面的空间就全部浪费了。所以我们采用相对映射的方法。即用待排序的数中,最大的数-最小的数+1就可以得到范围,从而减少空间浪费。接着用原数组的数减去最小值,将该值作为count数组的下标,即相对映射。最后进行排序,记得加回最小值min,这样数据才不会被改变。


排序算法的复杂度及稳定性

稳定性:指的是相同的数,在排序之后的相对位置没有改变。


分析:


                    时间                                    空间                                              


直接插入:明显的等差数列             无新空间开辟

希尔:前面文章已分析                          无  

选择:参考动图                                     无

堆排序:前面文章已分析                       无

冒泡:等差数列                                      无

快排:二分的思维                             看递归深度

归并:二分的思维                          开辟新的数组

稳定性通过假设来确定,只要有特例是不稳定的,那就是不稳定的。


目录
相关文章
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
1840 29
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
648 10
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
480 10
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
566 7
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
560 59
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
1399 77
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
386 0
栈区的非法访问导致的死循环(x64)
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
693 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】

热门文章

最新文章