转-各种排序动图

2023-11-16

1 快速排序

介绍:

  快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

步骤:

  • 从数列中挑出一个元素,称为 "基准"(pivot),
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

排序效果:

详细过程:

 

 

2 归并排序

介绍:

  归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用

步骤:

  • 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  • 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  • 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  • 重复步骤3直到某一指针达到序列尾
  • 将另一序列剩下的所有元素直接复制到合并序列尾

排序效果:

详细过程:

 

 

3 堆排序

介绍:

  堆积排序(Heapsort)是指利用这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

步骤:

(比较复杂,自己上网查吧)

排序效果:

详细过程:

(暂无)

4 选择排序

介绍:

  选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

排序效果:

详细过程:

 

 

5 冒泡排序

介绍:

  冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

步骤:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

排序效果:

详细过程:

 

 

6 插入排序

介绍:

  插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

步骤:

  • 从第一个元素开始,该元素可以认为已经被排序
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置中
  • 重复步骤2

排序效果:

 (暂无)

详细过程:

 

 

7 希尔排序

介绍:

  希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。

  希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  • 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

排序效果:

详细过程:

 

 

----------------------------------------------------------------------------------------------------------------------

Over!

希望对大家有帮助!


原文来自:http://yingyingol.iteye.com/blog/1334891

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

转-各种排序动图 的相关文章

  • Zlib的安装与测试

    官方网址 http www zlib net 进入官网看到 如图所示 最新版本为zlib 1 2 11 然后你用wget http www zlib net zlib 1 2 11或者wget http www zlib net zlib
  • 快速排序————非递归实现

    二 递归实现快速排序 2 1 为什么我们要去通过递归实现我们的快速排序呢 大家有可能会想是不是因为递归非常的占用空间 我们都知道我们的局部变量是保存在栈上的我们的函数参数也是在栈上开辟的 所以说递归是不是会占用我们非常多的栈空间 同时呢我们
  • 数据结构之快速排序算法

    文章目录 快速排序的思想 快速排序的递归实现 快速排序的非递归实现 快速排序的思想 设置两个变量i j 排序开始的时候 令i 0 j length 1 以第一个数组元素作为比较 赋值给temp 即temp nums 0 从j开始向前扫描 找
  • CH1-绪论

    文章目录 算法时间复杂度的计算 一 冒泡排序简介 从小到大排序 算法时间复杂度的计算 我们一般只关心随着问题规模n趋于无穷时 函数中对函数结果影响最大的项 比如说 T n 3n 3 当n非常大的时候 常数3和n的系数3对函数结果的影响就很小
  • 快速排序(C语言简单实现)

    快速排序 C语言简单实现 快速排序 Quick Sort 是冒泡排序的升级版 基本思想 通过一趟排序将待排记录分割成独立的两部分 其中一部分记录的关键字均比另一部分记录的关键字小 则可分别对这两部分记录继续进行排序 以达到整个序列有序的目的
  • 【算法入门】什么是时间复杂度和空间复杂度,最优解

    如何评价算法复杂度 时间复杂度 额外空间复杂度 常数操作 常数操作 常数操作 执行时间固定和数据量没有关系的运算操作 如果和数据量有关就不是常数操作 运算 数组寻址 数组里获取3位置和3000w位置数据时间相等 1 1 和100w 100w
  • 【Java】5大排序算法总结(插入排序+希尔排序+选择排序+堆排序+冒泡排序)

    快速导航 1 稳定性 2 插入排序 3 希尔排序 4 选择排序 5 堆排序 6 冒泡排序 1 稳定性 两个相等的数据 如果经过排序后 排序算法能保证其相对位置不发生变化 则我们称该算法是具备稳定性的排序算法 图中排序后a仍然在b前面 此时这
  • C++ 快速排序

    快速排序是比较常用的一种排序 平均时间复杂度为O nlogn 最坏的时间复杂度为O n 话不多说 上代码 include
  • c++用vector先按学生的年级排序,再按学生的分数排序算法

    VectorSort cpp 定义控制台应用程序的入口点 include stdafx h include stdio h include string h include
  • 数据结构——哈希排序

    哈希排序 就是用空间换取时间的一种排序方式 空间利用率达O n 算法思想 如果一个元素序列a里没有重复的元素 而我们需要找最大值或者前几个最大值时 怎么办呢 1 将这个a序列排序 然后直接选出目标值 2 开辟一个b数组 a里的每一个元素对应
  • python算法中的机器学习算法之无监督学习知识点(详解)

    目录 学习目标 学习内容 K均值聚类 K Means Clustering 层次聚类 Hierarchical Clustering
  • QString转const char*

    QString str hello world 转成const char const char arr str toStdString c str const char arr str toLatin1 constData toUtf8 转
  • 如何学好C语言的数据结构与算法?

    C语言的数据结构与算法 难就难在链表 学会了链表 可能后面就一点都不难了 书籍推荐 数据结构与算法分析 C语言描述版 要深入学习的话可以选择这本书 因为针对链表的讲解是比较详细的 所以可以很快理解链表 跟着书上一点点实现基本操作 增删改查
  • 堆排序的topk问题+归并排序+六大排序总结

    回忆一下堆排序 思路 sift函数 调整 将父亲和孩子 左孩子和右孩子中最大的那个数 然后和父亲比较 如果孩子大就将孩子的位子变为下一个父亲 往下拉 并且将孩子的值赋给他的父亲 j lt high 条件认可 防止父亲在最后一层 魔法般的对应
  • C语言冒泡排序和选择排序

    一 冒泡排序法 假设从小到大排序 例一数组 int arr 2 1 34 5 arr 0 先跟相邻的arr 1 比较大小 如果比它大则交换两个数值位置 大的数值放在后面 然后比较arr 1 和arr 2 的大小 以此类推 直至第n 2个和第
  • LeetCode -- 1833. 雪糕的最大数量

    使用的算法 计数排序 贪心算法 计数排序 1 基于比较的排序算法 2 在对一定范围内的整数排序时 它的复杂度为 n k 其中k是整数的范围 快于任何比较排序算法 当O k gt O nlog n 的时候其效率反而不如基于比较的排序 基于比较
  • Java 常用的大算法详解

    Java 常用的大算法详解 排序算法是计算机科学中的重要主题之一 Java 提供了许多常用的排序算法 本文将详细介绍其中的几种 并提供相应的源代码实现 冒泡排序 Bubble Sort 冒泡排序是一种简单直观的排序算法 它重复地遍历待排序的
  • 八大排序(希尔排序)

    上篇文章我们来看了看插入排序是怎么实现的 本章内容就是在插入排序的基础上完成希尔排序 希尔排序是一个比较强大的排序 我们希尔排序的时间复杂度是比较难算的 这里直接给出的结论就是时间复杂度就是O N 1 3 比较难算的原因就是我们每一次的次数
  • 数组对象排序 (arr.sort())

    前端面试题库 面试必备 推荐 地址 前端面试题库 对象排序 arr sort 描述 方法sort 将在原数组上对 数组元素 进行排序 即排序时不创建新的数组副本 如果想按照别的顺序进行排序 就必须提供比较函数 该函数要比较两个值 然后返回一
  • 冒泡排序/选择排序/插入排序/快速排序/归并排序/桶排序/堆排序/希尔排序/计数排序/基数排序/二分查找/广度优先搜索/深度优先搜索

    排序算法 冒泡排序 Bubble Sort 通过重复地比较相邻的元素并交换它们 使得最大 或最小 的元素逐渐移动到列表的一端 从而实现排序 选择排序 Selection Sort 在未排序的部分中 选择最小 或最大 的元素 并将其放置在已排

随机推荐