当前位置: 首页 > news >正文

异世界历险之数据结构世界(排序(插入,希尔,堆排))

前言

在这里插入图片描述

介绍

插入排序

基本知识:
直接插入排序是一种简单的插入排序法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列

在这里插入图片描述

直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

实现

void InsertSort(int*arr,int n)
{for (int i = 1; i < n; i++){int tmp = arr[i];int end = i - 1;while (tmp < arr[end]){arr[end + 1] = arr[end];end--;}arr[end + 1] = tmp;}}

解析:1.外层 for 循环控制遍历每个待插入的元素,从下标 1 开始(因为下标 0 视为初始的已排序区)
2. tmp 暂存当前要插入的元素。
end 表示已排序部分的末尾元素下标,用来向左比较寻找插入位置。
3.当当前元素 tmp 小于已排序区的元素 arr[end],说明还没找到插入位置:
将较大的元素右移一位,给 tmp 腾出空间;
end-- 继续向左查找。

4.找到插入位置后,将 tmp 放入空出来的位置,即 end + 1

希尔排序

基本知识:
希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个
组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序

在这里插入图片描述

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经 接近有序的了,这样就会很快。

实现

void ShellSort(int*arr,int n)
{ for(int gap = n/2;gap>0;gap/=2){  for(int i = gap;i<n;i++){ int tmp = arr[i];int end = i-gap;while(end>=0 && arr[end]>tmp){arr[end+gap] =arr[end];end -= gap;}arr[end+gap] = tmp;}}
}
解析
for(int gap = n/2;gap>0;gap/=2)

设定初始间隔 gap = n/2,后续每次缩小一半。
这样每轮都能把当前数组变得更“接近有序”。
最后当 gap == 1 时,其实就是普通的插入排序,但效率更高!

for (int i = gap; i < n; i++)

从当前 gap 开始往后遍历数组。
为啥不是 i=0?因为我们要比较 arr[i] 和它 gap 之前的数,即 arr[i - gap],所以 i 至少得 ≥ gap。

arr[end + gap] = arr[end];
end -= gap;

把大的元素往后挪出一个 gap 的位置。
指针继续往前 gap 个单位看下一个数。

arr[end + gap] = tmp;

找到该插入的位置了,把 tmp 插进去。
完成一个元素在当前 gap 下的插入排序。

实战演示

数组排序OJ
在这里插入图片描述

解答
void ShellSort(int*arr,int n)
{ for(int gap = n/2;gap>0;gap/=2){  for(int i = gap;i<n;i++){ int tmp = arr[i];int end = i-gap;while(end>=0 && arr[end]>tmp){arr[end+gap] =arr[end];end -= gap;}arr[end+gap] = tmp;}}
}int* sortArray(int* nums, int numsSize, int* returnSize) {int* arr = (int*)malloc(sizeof(int)*numsSize);for(int i = 0;i<numsSize;i++){arr[i]=nums[i];}InsertSort(arr,numsSize);*returnSize = numsSize;return arr;
}

希尔排序总结:

核心思路:先按大 gap 做分组插入排序,逐步缩小 gap 到 1。
时间复杂度:平均 ≈ O(n¹·³~n¹·⁵),最坏 O(n²);效率取决于 gap 序列。
空间复杂度:O(1) 原地排序。
稳定性:不稳定,同值元素位置可能改变。

希尔排序补充

1.反向插排希尔
void HalfShellSort(int* arr, int n)
{int gap = 3;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[i + gap];while (end >= 0 && arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}arr[end + gap] = tmp;}
}

差异:

for (int i = 0; i < n - gap; i++)
{int end = i;int tmp = arr[i + gap];
}
for(int i = gap;i < n;i++){ int tmp = arr[i];int end = i-gap;}

解释:
方案一是正常思维以0为起点,即end为主角,end+gap 是tmp的位置,故为了不越界·i<n-gap。
方案二是以第二个gap为i的开始,即tmp为主角,tmp始终是end的后一个gap,所以i<n,不存在越界问题。

2.多重循环希尔
void ShellSort(int* arr, int n)
{for (int gap = n / 2; gap > 0; gap /= 2){for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i+=gap){int tmp = arr[i+gap];int end = i;while (end >= 0 && arr[i] > tmp){arr[end + gap] = arr[end];end -= gap;}arr[end + gap] = tmp;}}}
}

差异:

for (int j = 0; j < gap; j++)for (int i = j; i < n - gap; i+=gap)
for(int i = 0;i<n-gap;i++)

方案一比方案二多了一层循环
原因分析: 方案一是以gap将全部分为gap个集合,每个集合内进行希尔排序。
例如:以gap==3 为例:
分为:0开头集合,1开头集合,2开头集合 以这种形式进行排序。
方案二则是按顺序一个一个排。
二者没有任何区别,时间复杂度和空间复杂度一样。

堆排序

基本知识:
堆排序即利用堆的思想来进行排序,总共分为两个步骤:

  1. 建堆
    升序:建大堆
    降序:建小堆
  2. 利用堆删除思想来进行排序

堆的复习
向上调整函数(AdjustUp)
向下调整函数(AdjustDown)
堆插入

实现

1.建堆
方案一:

void AdjustUp(int* arr,int child)
{int parent = (child - 1) / 2;while (child>0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapSort(int*arr,int n)
{for (int i = 1; i < n; i++){AdjustUp(arr, i);}
}

类似于堆插入,从第二个数组中元素开始插入,调整。

方案二:

void AdjustDown(int* arr, int n, int parent)
{int child = 2 * parent + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HeapSort(int*arr,int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr,n,i);}
}

i == (n-1-1)/2 是尾(最后)叶子的父节点。
向下调整建堆的原理是:
从最后一个非叶子节点开始,逐个对子树进行向下调整,把局部小堆变成大堆,逐层向上构造,最终整个数组就成了一个大堆结构。

在这里插入图片描述

总结:
方法一:向上调整(AdjustUp)
从第1个元素往后扫,每插入一个元素就“向上冒泡”一次,维护堆
时间复杂度:O(n log n)
方法二:向下调整(AdjustDown)
从最后一个非叶子节点开始,逐个节点向下调整整个子树
最终堆顶就是整个数组的最大值(如果建大堆)
时间复杂度:O(n) 更优!

2.排序

void HeapSort(int*arr,int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr,n,i);}int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}

在这里插入图片描述
排序如图所示。
1.交换根和尾叶子,把大数放在后面。
2.向下调整,在形成大根堆。
3.循环往复。

总结

八大排序我们学了三个,其余的将逐渐补充丰富。

http://www.lryc.cn/news/591915.html

相关文章:

  • CentOS7下的ElasticSearch部署
  • 2025年6月电子学会全国青少年软件编程等级考试(Python一级)真题及答案
  • TL1A靶点:自免炎症领域的“潜力之星”
  • chainlink VRF中文教程(含mock),解决error: Arithmetic Underflow in createSubscription
  • Elasticsearch 和 solr 的区别
  • Prometheus错误率监控与告警实战:如何自定义规则精准预警服务器异常
  • 大数据时代下的时序数据库选型指南:基于工业场景的IoTDB技术优势与适用性研究
  • LiteCloud超轻量级网盘项目基于Spring Boot
  • 如何解决pip安装报错ModuleNotFoundError: No module named ‘django’问题
  • 第2章通用的高并发架构设计——2.5 高并发读场景总结:CQRS
  • JavaScript中的Window对象
  • 个人笔记(初级Linux运维设计脚本编写任务)
  • 微信小程序151~160
  • stl-string模拟
  • Solr7升级Solr8全攻略:从Core重命名到IK分词兼容,零业务中断实战指南
  • Java零基础快速入门
  • 闲庭信步使用图像验证平台加速FPGA的开发:第二十一课——高斯下采样后图像还原的FPGA实现
  • 缓存雪崩、缓存穿透,缓存击穿
  • 神经网络构建
  • 【Reinforcement Learning】强化学习常用算法
  • python爬虫入门(小白五分钟从入门到精通)
  • Leetcode 494. 目标和
  • FFmpeg 直播推流
  • java-字符串和集合
  • 基础算法题
  • 开源 python 应用 开发(八)图片比对
  • CMake-gdb调试,解决LLVM ERROR: out of memory
  • 2021市赛复赛 初中组
  • docker重新搭建redis集群
  • 闲庭信步使用图像验证平台加速FPGA的开发:第二十课——图像还原的FPGA实现