[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)

news/2024/5/20 7:58:32

 

文章涉及具体代码gitee: 登录 - Gitee.com

目录

1.插入排序

1.直接插入排序

 总结

 2.希尔排序

总结 

 2.选择排序

1.选择排序

​编辑

总结 

2.堆排序

总结 

3.交换排序

1.冒泡排序

总结 

2.快速排序

总结 

4.归并排序

总结 

5.总的分析总结 


1.插入排序

具体分析过程见我的博客插入排序:

[数据结构]——排序——插入排序-CSDN博客

1.直接插入排序

void InsertSort(int* a, int n)
{// [0, end] end+1for (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];--end;}else{break;}}a[end + 1] = tmp;}
}

 总结

直接插入排序是一种简单观的排序算法,它基本思想是将待排序的元逐个插入到已经排好序的序列中,直到所有元素都插入完成为止下面是对直接插入排序的析总结:

  1. 时间复杂度:

    • 最好情况下待排序序列已经是有序的此时只需要比较n-1次,时间复杂度为O(n)。
    • 最坏情况下,待排序序列是逆序的,此时需要比较和移动元素的次数最多,时间复杂度为O(n^2)。
    • 平均情况下,假设待排序序列中的每个元素都等概率地出现在任何位置,那么平时间复杂度为O(n^2)。
  2. 空间复杂度: 直接插入排序是一种原地排序算法,不需要额外的空间存储数据,所以空间复杂度为O(1)。

  3. 稳定性: 直接插入排序是一种稳定的排序算法,相等元素的相对位置在排序前后不会发生改变。

  4. 适用性:

    • 对于小规模的数据或者基本有序的数据,直接插入排序是一种简单高效的排序算法。
    • 但对于大规模乱序的数据,直接插入排序的性能较差,不如快速排序、归并排序等高效。

 2.希尔排序

void ShellSort(int* a, int n)
{int gap = n;// gap > 1时是预排序,目的让他接近有序// gap == 1是直接插入排序,目的是让他有序while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;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;}}}

总结 

希尔排序是一种基于插入排序的排序算法,它通过将待排序的元素按照一定的间隔分组,对每个分组进行插入排序,然后逐渐缩小间隔,直到间隔为1,最后进行一次完整的插入排序。希尔排序的主要思想是通过较大的步长先将数组局部有序,然后逐渐减小步长,最终使得整个数组有序。

希尔排序的分析总结如下:

  1. 时间复杂度:希尔排序的时间复杂度与步长序列的选择有关。最好情况下,当步长序列为1时,希尔排序的时间复杂度为O(nlogn);最坏情况下,当步长序列为2^k-1时,希尔排序的时间复杂度为O(n^2);平均情况下,希尔排序的时间复杂度为O(nlogn)。
  2. 空间复杂度:希尔排序的空间复杂度为O(1),即不需要额外的空间存储数据。
  3. 稳定性:希尔排序是不稳定的排序算法,即相同元素的相对位置可能会发生改变。
  4. 对于大规模数据和中等规模数据,希尔排序相对于其他简单的排序算法(如插入排序、冒泡排序)具有较好的性能。

 2.选择排序

具体分析过程见我的博客插入排序:

[数据结构]———选择排序-CSDN博客

1.选择排序

// 时间复杂度:O(N^2)
// 最好的情况下:O(N^2)
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

总结 

选择排序是一种简单直观的排序算法,其基本想是每次从待排序的元素中选择最小(或最大)的元素,放到已排序序列的末尾。选择排序的分析总结如下:

  1. 时间复杂度:选择排序的时间复杂度为O(n^2),其中n是待排序序列的长度。因为每次都需要在剩余的未排序元素中找到最小(或最大)的元素,需要进行n-1次比较和交换操作。

  2. 空间复杂度:选择排序的空间复杂度为O(1),即不需要额外的空间来存储数据。

  3. 稳定性:选择排序是一种不稳定的排序算法。在每次选择最小(或最大)元素时,可能会改变相同元素之间的相对顺序。

  4. 适用性:选择排序适用于小规模数据的排序,但对于大规模数据效率较低。由于其简单直观的思想,选择排序在教学和理解排序算法的过程中具有一定的价值。

2.堆排序

void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假设左孩子小,如果解设错了,更新一下if (child + 1 < size && 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;}
}

总结 

堆排序是一种高效的排序算法,它利用了堆这种数据结构的特性来进行排序。下面是对堆排序的分析总结:

  1. 堆的构建:首先需要将待排序的数组构建成一个堆。堆是一个完全二叉树,可以使用数组来表示。通过从最后一个非叶子节点开始,依次向上调整每个节点,使得每个节点都满足堆的性质。

  2. 堆的调整:构建好堆之后,将堆顶元素(最大值或最小值)与最后一个元素交换位置,并将堆的大小减一。然后再对堆顶元素进行调整,使得剩余元素重新满足堆的性质。重复这个过程,直到堆的大小为1,即完成了排序。

  3. 时间复杂度:堆排序的时间复杂度为O(nlogn),其中n是待排序数组的长度。堆的构建需要O(n)的时间复杂度,而每次调整堆的操作需要O(logn)的时间复杂度,总共需要进行n-1次调整。

  4. 空间复杂度:堆排序的空间复杂度为O(1),只需要常数级别的额外空间来存储中间变量。

  5. 稳定性:堆排序是一种不稳定的排序算法,因为在调整堆的过程中,可能会改变相同元素的相对顺序。

3.交换排序

具体分析过程见我的博客插入排序:

[数据结构]———交换排序-CSDN博客

1.冒泡排序

// 时间复杂度:O(N^2)
// 最好情况是多少:O(N)
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}}

总结 

冒泡排序是一种简单的排序算法,它通过多次比较和交换相邻元素的方式将最大(或最小)的元素逐渐“冒泡”到数组的末尾。下面是对冒泡排序的分析总结:

  1. 基本思想:冒泡排序的基本思想是通过相邻元素的比较和交换来实现排序。每一轮比较都会将当前未排序部分的最大(或最小)元素“冒泡”到末尾。

  2. 时间复杂度:冒泡排序的时间复杂度为O(n^2),其中n是待排序数组的长度。这是因为冒泡排序需要进行n-1轮比较,每轮比较需要遍历未排序部分的元素。

  3. 空间复杂度:冒泡排序的空间复杂度为O(1),即不需要额外的空间来存储数据。

  4. 稳定性:冒泡排序是一种稳定的排序算法,即相等元素的相对顺序在排序后不会改变。

  5. 最佳情况和最差情况:无论是最佳情况还是最差情况,冒泡排序的时间复杂度都是O(n^2)。最佳情况是待排序数组已经有序,此时只需要进行n-1轮比较即可。最差情况是待排序数组逆序,需要进行n-1轮比较,并且每轮比较都需要交换元素。

2.快速排序

// 挖坑法
int PartSort2(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int key = a[begin];int hole = begin;while (begin < end){// 右边找小,填到左边的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左边找大,填到右边的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

总结 

快速排序是一种常用的排序算法,它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据小,然后再按此方法对这两部分数据分别进行快速排序,整个过程递归进行,以达到整个数据变成有序序列的目的。

快速排序的分析总结如下:

  1. 时间复杂度:平均情况下,快速排序的时间复杂度为O(nlogn),最坏情况下为O(n^2)。最坏情况发生在待排序序列已经有序或基本有序的情况下,此时每次划分只能减少一个元素,需要进行n-1次划分,因此时间复杂度较高。但是通过优化措施(如随机选择基准元素),可以避免最坏情况的发生。
  2. 空间复杂度:快速排序的空间复杂度为O(logn),主要是由于递归调用造成的栈空间使用。
  3. 稳定性:快速排序是一种不稳定的排序算法,因为在交换元素的过程中可能改变相同元素的相对顺序。
  4. 应用场景:快速排序在实际应用中广泛使用,特别适用于大规模数据的排序。它的性能优于其他常见的排序算法,如冒泡排序和插入排序。

4.归并排序

具体分析过程见我的博客插入排序:

[数据结构]———归并排序-CSDN博客

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);
}

总结 

归并排序是一种经典的排序算法,它采用分治的思想来实现排序。下面是对归并排序的分析总结:

  1. 算法思想:归并排序将待排序的序列不断地分割成两个子序列,直到每个子序列只有一个元素,然后将这些子序列两两合并,直到最终得到有序的序列。

  2. 时间复杂度:归并排序的时间复杂度为O(nlogn),其中n是待排序序列的长度。这是因为每次合并操作都需要O(n)的时间,而分割操作需要O(logn)次。

  3. 空间复杂度:归并排序需要额外的O(n)空间来存储临时数组,用于合并操作。

  4. 稳定性:归并排序是一种稳定的排序算法,即相等元素的相对顺序在排序后保持不变。

  5. 优点:归并排序具有稳定性和适应性好的特点,适用于各种数据类型和数据规模。

  6. 缺点:归并排序需要额外的空间来存储临时数组,对于大规模数据排序时可能会占用较多的内存。

5.总的分析总结 

插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素逐个插入到已排序序列中的适当位置,直到全部元都插入完毕。插入排序包直接插入排序和希尔排序。

  1. 直接插入排序:

    • 算法思想:将待排序序列分为已排序和未排序两部分,初始时已排序部分只有一个元素。然后从未排序部分依次取出元素,与已排序部分的元素进行比较并插入到合适的位置。
    • 时间复杂度:最好情况下为O(n),最坏情况下为O(n^2),平均情况下为O(n^2)。
    • 空间复杂度:O(1)。
    • 稳定性:稳定。
  2. 希尔排序:

    • 算法思想:希尔排序是直接插入排序的改进版,通过设置一个增量序列,将待排序序列分割成若干个子序列,对每个子序列进行直接插入排序。然后逐步缩小增量,最终完成整个序列的排序。
    • 时间复杂度:平均情况下为O(nlogn),最坏情况下为O(n^2)。
    • 空间复杂度:O(1)。
    • 稳定性:不稳定。

选择排序是一种简单直观的排序算法,它的基本思想是每次从待排序序列中选择最小(或最大)的元素放到已排序序列的末尾。选择排序包括选择排序和堆排序。

  1. 选择排序:

    • 算法思想:将待排序序列分为已排序和未排序两部分,初始时已排序部分为空。每次从未排序部分选择最小(或最大)的元素,放到已排序部分的末尾。
    • 时间复杂度:最好情况下为O(n^2),最坏情况下为O(n^2),平均情况下为O(n^2)。
    • 空间复杂度:O(1)。
    • 稳定性:不稳定。
  2. 堆排序:

    • 算法思想:堆排序利用堆这种数据结构进行排序。首先将待排序序列构建成一个大顶堆(或小顶堆),然后依次将堆顶元素与末尾元素交换,并重新调整堆,直到整个序列有序。
    • 时间复杂度:平均情况下为O(nlogn),最坏情况下为O(nlogn)。
    • 空间复杂度:O(1)。
    • 稳定性:不稳定。

交换排序是一种通过元素之间的交换来进行排序的算法,包括冒泡排序和快速排序。

  1. 冒泡排序:

    • 算法思想:冒泡排序通过依次比较相邻的元素,并交换它们的位置,使得每一轮循环都能将最大(或最小)的元素移动到末尾。重复这个过程,直到整个序列有序。
    • 时间复杂度:最好情况下为O(n),最坏情况下为O(n^2),平均情况下为O(n^2)。
    • 空间复杂度:O(1)。
    • 稳定性:稳定。
  2. 快速排序:

    • 算法思想:快速排序通过选择一个基准元素,将待排序序列分成两部分,一部分小于基准元素,一部分大于基准元素。然后对这两部分分别进行快速排序,直到整个序列有序。
    • 时间复杂度:平均情况下为O(nlogn),最坏情况下为O(n^2)。
    • 空间复杂度:平均情况下为O(logn),最坏情况下为O(n)。
    • 稳定性:不稳定。

归并排序是一种基于分治思想的排序算法。

  1. 归并排序:
    • 算法思想:归并排序将待排序序列递归地分成两个子序列,对每个子序列进行归并排序,然后将两个有序子序列合并成一个有序序列。重复这个过程,直到整个序列有序。
    • 时间复杂度:平均情况下为O(nlogn),最坏情况下为O(nlogn)。
    • 空间复杂度:O(n)。
    • 稳定性:稳定。

优缺点和注意实现分析总结:

  • 直接插入排序和冒泡排序简单易懂,但对于大规模数据排序效率较低。
  • 希尔排序通过设置增量序列,可以在一定程度上提高排序效率。
  • 选择排序和堆排序的时间复杂度较高,但堆排序在大规模数据排序时相对较快。
  • 快速排序是一种高效的排序算法,但在最坏情况下可能会退化为O(n^2)的时间复杂度。
  • 归并排序具有稳定性和较高的时间复杂度,适用于大规模数据排序。

http://www.mrgr.cn/p/25743421

相关文章

二进制转为HEX数组小工具

在使用RA8889时&#xff0c;JPG的解码只能从FLASH的DMA通道获取&#xff0c;那么如果要从远端、或者SD卡等处读取JPG图片出来显示怎么办&#xff1f; RA8889支持JPG图片硬解码&#xff0c;但数据流是从FLASH进行DMA读取的&#xff0c;然后再进行解码。因此这种情况下&#xff…

redis自学(42)Lua语法

接下来要实现Nginx的本地缓存,而Nginx是用Lua语言来开发,下面简单理解一下Lua初始Lua Lua是一种轻量小巧的脚本语言,用标准C语言编写并以源代码形式开放,其设计目的是为了嵌入应用程序中,从而为应用程序提供灵活的扩展和定制功能。 安装,centOS自带Lua语言了,不需要安装…

Stable-Diffusion ControlNet插件 DWPose模型下载及使用

webui Version: v1.9.3 DWPose项目地址: https://huggingface.co/yzd-v/DWPose 国内镜像: https://gitee.com/hf-models/DWPose 先安装 git-lfs,下载git仓库大文件会用到 文档: https://help.gitee.com/enterprise/code-manage/code-hosting/large-file-manage/git-lfs 然后确保…

力扣437. 路径总和 III

Problem: 437. 路径总和 III 文章目录 题目描述思路复杂度Code 题目描述 思路 1.定义int类型函数rootSum(root, targetSum)&#xff0c;用于求取每一个节点等于目标函数的路径数&#xff1a; 1.1.易知rootSum(root, targetSum)求出的数量等于rootSum(root.left, targetSum - va…

ISCC线上赛2023

ISCC线上赛2023 web web1双重base解码得到flag web3 F12控制台查看可找到loveStory.php Enc.php download.php,loveStory.php为反序列源码 boy::__destruct() -->girl()::__call()-->helper()::__isset()-->boy()::__toString()-->helper()::__get()-->love_st…

python教程6.4-excel处理模块

第三方开源模块安装 创建文件打开已有文件写数据选择表保存表遍历表 按行遍历按列遍历遍历指定行列遍历指定第几列数据删除表设置单元格样式字体对齐设置行高列宽

无处不在的AI:被科技巨头盯上的Agent智能体的崭新时代

&#x1f97d;一.Agent AI智能体 Agent AI 智能体是一种基于人工智能技术的智能代理&#xff0c;它可以自主地执行任务、与环境进行交互&#xff0c;并根据环境的变化做出决策。 OpenAI将AI Agent定义为以大语言模型&#xff08;LLM&#xff09;为大脑驱动具有自主理解、感知、…

24/05/08 图论

能做的仍然只有 stO Liuhl_weifang Orz。\(\color{purple}(1)\) CF746G New Roads构造一棵 \(n\) 个点的深度为 \(t\) 的树,以 \(1\) 为根,使其中深度为 \(i\) 的点有 \(a_i\) 个且叶节点有 \(k\) 个。或报告无解。 \(t, k \le n \le 2 \times 10^5\)。为了方便,我们令根节点…

Rust开发工具有哪些?

目录 一、JetBrains公司的RustRover​编辑 二、微软公司的Visual Studio Code 三、Rust编译工具 一、JetBrains公司的RustRover RustRover是由JetBrains开发的一款专为Rust开发量身定制的新兴IDE&#xff0c;目前还处于早期访问阶段。它支持Rust、Cargo、TOML、Web和数据库等…

2024-05-08:用go语言,给定一个由正整数组成的数组 nums, 找出数组中频率最高的元素, 然后计算该元素在数组中出现的总次数。 输入:nums = [1,2,2,3,1,4]。 输出:4。

2024-05-08:用go语言,给定一个由正整数组成的数组 nums, 找出数组中频率最高的元素, 然后计算该元素在数组中出现的总次数。 输入:nums = [1,2,2,3,1,4]。 输出:4。 答案2024-05-08: chatgpt 题目来自leetcode3005。 大体步骤如下: 1.创建一个空的字典 cnt 用于存储每个…

报错:Error: Cannot find module

报错详情: 解决方法: 1、正确安装版本号的nodejs 2、删除项目根文件夹下的node_modules和“package-lock.json”, 3、重新执行npm install

上课学习(无线网络)

考红色部分:如什么协议采用集中式架构

UG NX二次开发(C#)-获取Part中对象创建时的序号(*)

文章目录 1、前言2、UG NX的对象序号讲解3、采用UG NX二次开发或者建模序号4、注意事项1、前言 在UG NX中,我们创建任意一个对象,都会在模型历史中添加一个创建对象的编号,即是对象序号,这个是递增的,当删除中间产生的对象时,其序号会重新按照建模顺序重新排布。今天一个…

2024CVPR_Low-light Image Enhancement via CLIP-Fourier Guided Wavelet Diffusion(CFWD)

一、Motivation 1、单模态监督问题:大多数方法往往只考虑从图像层面监督增强过程,而忽略了图像的详细重建和多模态语义对特征空间的指导作用。这种单模态监督导致不确定区域的次优重建和较差的局部结构,导致视觉结果不理想的出现。------》扩散模型缺乏有效性约束,容易出现…

PDF批量编辑技巧:高效PDF转txt批量处理,轻松管理大量文档

随着信息技术的飞速发展&#xff0c;文档管理已成为日常工作中不可或缺的一部分。特别是当我们需要处理大量的PDF文件时&#xff0c;如何高效地进行编辑、转换和管理成为了一个重要的问题。本文将介绍一些PDF批量编辑的技巧&#xff0c;特别是如何将PDF批量转换为txt格式&#…

Redis单机安装

1.编译 cd redis安装目录 makemake install2.修改配置文件redis.conf #端口修改 port 6379 #后台进程启动 yes daemonize yes # daemonize no #注释掉 为了可以远程连接 #bind 127.0.0.1 #设置密码 requirepass pwd3.启动 ./redis-server ../redis.conf查看进程 [rootlocal…

『ZJUBCA Collaboration』WTF Academy 赞助支持

非常荣幸宣布&#xff0c;浙江大学区块链协会收到WTF Academy的赞助与支持&#xff0c;未来将共同开展更多深度合作。 WTF Academy是开发者的Web3开源大学&#xff0c;旨在通过开源教育让100,000名开发者进入到Web3。截止目前&#xff0c;WTF开源教程在GitHub收获超15,000 ⭐&a…

【GPT调用】本地使用python调用GPT接口

python调用GPT接口 环境变量设置主调用方法执行结果 环境变量设置 .env文件中配置GPT环境变量 api_key"你的GPT-API-KEY" urlhttps://ai-proxy.ksord.com/wps.openai.azure.com/openai/deployments/gpt-4-32k/chat/completions?api-version2023-09-01-preview主调…

Jmeter-线程组下篇

线程组 线程组作为JMeter测试计划的核心组件之一,对于模拟并发用户的行为至关重要。线程组元件是整个测试计划的入口,所有的取样器和控制器必须放置在线程组下。 可以将线程组视为一个虚拟用户池,其中每个线程可被理解为一个虚拟用户,多个虚拟用户同时执行相同的一批任务。…

stable diffusion 之云端部署攻略

本文主要介绍stable diffusion云端产品以及使用步骤 ℹ️整合安装包、模型资源见文末~ megaease cloud&#xff08;强烈推荐&#xff09; 优点&#xff1a; 集成了常用大模型和插件、VAE3080显卡配置&#xff0c;费用大概0.48元/小时&#xff0c;可随时暂停&#xff0c;暂停…