【数据结构】排序算法(一)—>插入排序、希尔排序、选择排序、堆排序

简介: 【数据结构】排序算法(一)—>插入排序、希尔排序、选择排序、堆排序

1.直接插入排序

直接插入排序的思想就是从左到右进行遍历,在遍历过程中将当前的元素插入到前面(已经有序)合适的位置,直到遍历完成。

直接插入排序的特性:

  • 元素集合越接近有序,直接插入排序算法时间效率越高;
  • 时间复杂度:O(N^2);
  • 空间复杂度:O(1);
  • 稳定性:稳定。

排序的稳定性:指的是保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

代码实现:

// 插入排序
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//因为此时前面已经是有序序列,如果tmp>当前值,证明比前面都大,所以break跳出即可
      {
        break;
      }
      end--;
    }
    a[end+1]= tmp;
  }
}

2.希尔排序

希尔排序与直接插入排序同属插入排序方法,也就是说希尔排序也是靠向前插入的思路进行的。

不同的是,希尔排序先进行预排序,将待排序序列调整的接近有序后,再进行一次直接插入排序。

希尔排序利用了插入排序的特性:待排序序列越接近有序,插入排序时间效率越高。

那么如何进行预排序呢?

希尔排序将待排序序列分组,假设定义一个变量 gap ,那么间隔gap的数据我们分为一组,如图:

预排序阶段:我们以分组情况为基础,每组内部进行直接插入排序,每完成一轮,gap=gap/3-1。


注意:预排序阶段的边界设计很多可以参照直接插入排序,就是将1改为了gap而已,不理解时可以代入直接插入排序进行理解。


直接插入排序阶段:直到gap的值为1的时候,我们发现此时就是直接插入排序了,经过这轮排序就能得到最终的有序序列。


希尔排序的特性总结:

希尔排序是对直接插入排序的优化。

当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定。大致为O(N^1.25)到O(1.6*N^1.25)。

稳定性:不稳定


代码实现:

// 希尔排序
void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;//gap递减普遍取这种,也有取gap=gap/2的
    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 -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}

3.直接选择排序

选择排序的思想是每遍历一遍选出最小的值,放到最开始的位置。

我们对该思想优化,每次遍历选出最大值和最小值,分别放到两边。

直接选择排序的特性:

  • 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  • 时间复杂度:O(N^2)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

代码实现:

// 选择排序
void SelectSort(int* a, int n)
{
  int left = 0;
  int right = n - 1;
  while (right > left)
  {
    int maxi = left;
    int mini = left;
    for (int i = left+1; i <=right ; i++)
    {
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    swap(&a[left], &a[mini]);
    if (maxi == left)//假设max被换走了,恢复一下
    {
      maxi = mini;
    }
    swap(&a[right], &a[maxi]);
    right--;
    left++;
  }
}

4.堆排序

堆排序首先要介绍的是向下调整算法。

向下调整算法的前提是左右子树是堆。

以小堆为例:

1.给定向下调整的起点(双亲节点下标)和节点总数,根据起点下标计算孩子节点下标。

注意:向下调整时,若有两个孩子节点,则需要确保调整的是较大的孩子节点。

2.比较孩子节点与双亲节点数值大小,若孩子节点小于双亲节点,则交换两者,并将双亲节点的下标更新为之前的孩子节点下标,根据最新的双亲节点下标重新计算孩子节点下标,重复这一过程直到孩子节点超出节点总数。

对于堆排序来说:

以升序为例:

首先构建大堆(推荐使用向下调整),此时堆顶元素一定为最大值,然后将堆顶元素与最后一个节点交换,此时最大值就放到了整个数组的最后面,然后除了最后一个值以外,其他的数据再向下调整,调整完成后堆顶元素为次大值,再与数组倒数第二个位置的值交换,这样依此往复就得到了升序数组。


注意:升序建大堆,降序建小堆。

堆排序的特性总结:

  • 堆排序擅于处理庞大数据。
  • 时间复杂度:O(N*logN)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

代码实现:

// 堆排序
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)
{
  // 向下调整建堆
  // O(N)
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  // O(N*logN)
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}
目录
打赏
0
0
0
0
1
分享
相关文章
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
84 10
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
124 1
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
141 0
数据结构与算法学习十八:堆排序
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
82 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
【初阶数据结构篇】插入、希尔、选择、堆排序介绍(上篇)
堆排序(Heapsort)是指利⽤堆积树(堆)这种数据结构所设计的⼀种排序算法,它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆,排降序建⼩堆。
44 0
|
8月前
|
【初阶数据结构篇】堆的应用(堆排序与Top-K问题)
即求数据结合中前K个最⼤的元素或者最⼩的元素,⼀般情况下数据量都⽐较⼤。
86 0
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
本程序基于免疫算法实现物流仓储点选址优化,并通过MATLAB 2022A仿真展示结果。核心代码包括收敛曲线绘制、最优派送路线规划及可视化。算法模拟生物免疫系统,通过多样性生成、亲和力评价、选择、克隆、变异和抑制机制,高效搜索最优解。解决了物流仓储点选址这一复杂多目标优化问题,显著提升物流效率与服务质量。附完整无水印运行结果图示。
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
基于GA遗传优化TCN-GRU时间卷积神经网络时间序列预测算法matlab仿真
本项目基于MATLAB2022a开发,提供无水印算法运行效果预览及核心程序(含详细中文注释与操作视频)。通过结合时间卷积神经网络(TCN)和遗传算法(GA),实现复杂非线性时间序列的高精度预测。TCN利用因果卷积层与残差连接提取时间特征,GA优化超参数(如卷积核大小、层数等),显著提升模型性能。项目涵盖理论概述、程序代码及完整实现流程,适用于金融、气象、工业等领域的时间序列预测任务。
基于遗传优化算法的多AGV栅格地图路径规划matlab仿真
本程序基于遗传优化算法实现多AGV栅格地图路径规划的MATLAB仿真(测试版本:MATLAB2022A)。支持单个及多个AGV路径规划,输出路径结果与收敛曲线。核心程序代码完整,无水印。算法适用于现代工业与物流场景,通过模拟自然进化机制(选择、交叉、变异)解决复杂环境下的路径优化问题,有效提升效率并避免碰撞。适合学习研究多AGV系统路径规划技术。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等