(动画版)排序算法 -希尔排序

news/2024/11/18 14:12:18/

文章目录

  • 1. 希尔排序(Shellsort)
    • 1.1 简介
    • 1.2 希尔排序的步骤
    • 1.3 希尔排序的C实现
    • 1.4 时间复杂度
    • 1.5 空间复杂度
    • 1.6 希尔排序动画

1. 希尔排序(Shellsort)

1.1 简介

希尔排序(Shell's Sort),又称缩小增量排序(Diminishing Increment Sort),是直接插入算法>排序算法的一种更高效的改进版本。希尔排序是非稳定算法>排序算法,其核心思想是通过逐渐减小元素之间的间隔,使得序列在初始阶段就呈现局部有序,从而减少插入排序的工作量。希尔排序的基本思想是将待排序的序列划分成若干个子序列,分别进行插入排序。随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个序列恰被分成一组,此时再对全体记录进行一次直接插入排序,排序完成。

1.2 希尔排序的步骤

  1. 选择一个增量序列,该序列通常是递减的正整数序列。常用的增量序列有希尔建议的序列、Hibbard序列、Sedgewick序列等。增量序列的选择会直接影响希尔排序的性能。
  2. 使用选定的增量序列进行外层循环,每次循环缩小增量。
  3. 在每一轮外层循环中,通过增量对元素进行分组,每组包含相隔一定间隔的元素。这一步骤旨在逐步减小元素之间的间隔,从而实现序列的局部有序。
  4. 在每一组内,通过插入排序对元素进行排序。这是希尔排序的关键步骤,通过比较相隔增量的元素,并在需要时交换它们的位置,逐步实现每个小组的局部有序。
  5. 重复外层循环和内层循环,逐渐减小增量,直到增量为1。最后一次外层循环使用增量为1,相当于进行一次标准的插入排序。此时,整个序列已经基本有序,最终完成排序。

1.3 希尔排序的C实现


#include <stdio.h>// 希尔排序函数(带步骤输出)
void shellSort(int arr[], int n) {// 初始增量设置为数组长度的一半for (int gap = n / 2; gap > 0; gap /= 2) {printf("当前间隔 (gap): %d\n", gap); // 输出当前的间隔// 对每个增量子数组进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;printf("  当前插入元素 (arr[%d]): %d\n", i, temp);// 在增量子数组中向前移动元素,直到找到合适的位置for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {printf("    比较并移动元素 (arr[%d] = %d) 到位置 arr[%d]\n", j - gap, arr[j - gap], j);arr[j] = arr[j - gap];}// 将当前元素放到合适的位置arr[j] = temp;printf("  将元素 %d 插入到位置 arr[%d]\n", temp, j);// 输出每次插入后的数组状态printf("  当前数组状态: ");for (int k = 0; k < n; k++) {printf("%d ", arr[k]);}printf("\n");}// 输出每次间隔完成后的数组状态printf("间隔 %d 排序后的数组: ", gap);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n\n");}
}// 打印数组函数
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {22, 48, 65, 68, 68, 10, 84, 45, 37, 88, 71, 89, 89, 13, 59};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组: \n");printArray(arr, n);shellSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

希尔排序(Shell Sort)的时间复杂度和空间复杂度分析如下:

1.4 时间复杂度

希尔排序的时间复杂度取决于所选的增量序列。对于不同的增量序列,希尔排序的性能可能会有很大的差异。
  1. 最坏情况:使用原始的希尔增量(即每次将增量减半,从 n 2 \frac{n}{2} 2n开始),希尔排序的时间复杂度在最坏情况下可以达到O(n2)。这通常发生在数据已经接近有序但尚未完全有序的情况下,因为此时的插入排序(希尔排序在增量为1时的特殊情况)可能会执行大量的元素移动。

  2. 平均情况:在实际应用中,希尔排序通常比简单的插入排序要快得多,特别是在处理大数据集时。虽然其最坏情况时间复杂度较高,但平均情况下,希尔排序的性能通常优于O(n2)的算法>排序算法

  3. 最优增量序列:通过选择更好的增量序列(如Hibbard增量、Sedgewick增量等),可以进一步改进希尔排序的性能。然而,找到最优的增量序列仍然是一个未解决的问题,因此希尔排序的时间复杂度在很大程度上仍然是一个开放性问题。

  4. 实验观察:实验结果表明,对于中等规模的数据集,希尔排序的性能通常与快速排序(Quick Sort)相当,甚至在某些情况下可能更快。然而,对于非常大的数据集,快速排序通常具有更好的性能。

1.5 空间复杂度

希尔排序是一种原地算法>排序算法(in-place sorting algorithm),这意味着它只需要一个与输入数组大小相同的额外空间来存储临时变量(在插入排序的每一步中用于保存要插入的元素)。因此,希尔排序的空间复杂度是O(1)。

1.6 希尔排序动画

在希尔排序的动画中,用三种颜色来帮助理解排序过程:
  1. 橙色:当前插入的元素,表示正在考虑插入排序的那个元素(i)。
  2. 绿色:正在比较或插入的位置,表示当前正在比较或准备插入的具体位置(j)。
  3. 紫色:属于同一间隔组的元素,用来表明在当前的间隔(gap)下,这些元素属于同一组,将通过插入排序在组内进行比较和排序。

shell


http://www.ppmy.cn/news/1548004.html

相关文章

Python虚拟环境入门:虚拟环境如何工作、如何自定义创建和管理管理工具venv、Virtualenv、conda

文章目录 一、虚拟环境介绍1.1 为什么需要虚拟环境1.2 什么是虚拟环境1.2.1 venv常用命令1.2.2 虚拟环境的文件夹结构1.2.3 虚拟环境的隔离性 二、虚拟环境是如何工作的2.1 复制结构和文件2.2 调整前缀查找过程2.2.1 系统前缀查找过程2.2.2 虚拟环境前缀查找过程 2.3 链接回标准…

pytest | 框架的简单使用

这里写目录标题 单个文件测试方法执行测试套件的子集测试名称的子字符串根据应用的标记进行选择 其他常见的测试命令 pytest框架的使用示例 pytest将运行当前目录及其子目录中test_*.py或 *_test.py 形式的所有 文件 文件内的函数名称可以test* 或者test_* 开头 单个文件测试…

二、神经网络基础与搭建

神经网络基础 前言一、神经网络1.1 基本概念1.2 工作原理 二、激活函数2.1 sigmoid激活函数2.1.1 公式2.1.2 注意事项 2.2 tanh激活函数2.2.1 公式2.2.2 注意事项 2.3 ReLU激活函数2.3.1 公式2.3.2 注意事项 2.4 SoftMax激活函数2.4.1 公式2.4.2 Softmax的性质2.4.3 Softmax的应…

【代码大模型】Compressing Pre-trained Models of Code into 3 MB论文阅读

Compressing Pre-trained Models of Code into 3 MB key word: code PLM, compression, GA算法 论文&#xff1a;https://dl.acm.org/doi/pdf/10.1145/3551349.3556964 代码&#xff1a;https://github.com/soarsmu/Compressor.git 【why】 1.问题描述&#xff1a; code LLM …

3. langgraph中的react agent使用 (在react agent添加系统提示)

环境准备 确保你已经安装了以下库&#xff1a; langchainlangchain_openailanggraph 你可以使用以下命令进行安装&#xff1a; pip install langchain langchain_openai langgraph代码实现 1. 初始化模型 首先&#xff0c;我们需要初始化智谱AI的聊天模型。 from langch…

从零到一:利用 AI 开发 iOS App 《震感》的编程之旅

在网上看到一篇关于使用AI开发的编程经历&#xff0c;分享给大家 作者是如何在没有 iOS 开发经验的情况下&#xff0c;借助 AI&#xff08;如 Claude 3 模型&#xff09;成功开发并发布《震感》iOS 应用。 正文开始 2022 年 11 月&#xff0c;ChatGPT 诞生并迅速引发全球关注。…

8. 基于 Redis 实现限流

在高并发的分布式系统中&#xff0c;限流是保证服务稳定性的重要手段之一。通过限流机制&#xff0c;可以控制系统处理请求的频率&#xff0c;避免因瞬时流量过大导致系统崩溃。Redis 是一种高效的缓存数据库&#xff0c;具备丰富的数据结构和原子操作&#xff0c;适合用来实现…

智能网页内容截图工具:AI助力内容提取与可视化

我们每天都会接触到大量的网页内容。然而&#xff0c;如何从这些内容中快速提取关键信息&#xff0c;并有效地进行整理和分享&#xff0c;一直是困扰我们的问题。本文将介绍一款我近期完成的基于AI技术的智能网页内容截图工具&#xff0c;它能够自动分析网页内容&#xff0c;截…