十大排序算法动图（稳定的排序算法）

本文目录

• 稳定的排序算法
• 用选择法对10个整数由大到小排序要求画出流程图
• 十大经典排序算法（动图演示） 之 桶排序
• 基于比较的排序算法
• 风靡全球的十大算法
• 八大经典排序算法原理及实现

稳定的排序算法

基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，而且这个就是递增或递减的排列起来的操作。而且这个就是排序算法，就是如何使得记录按照要求排列的方法。而且这个就是排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。

排序（Sorting）是计算机程序设计中的一种重要操作，而且这个就是它的功能是将一个数据元素（或记录）的任意序列，而且这个就是重新排列成一个关键字有序的序列。

历史背景：

一个排序算法是稳定的，就是当有两个相等记录的关键字和，而且这个就是且在原本的列表中出现在之前，在排序过的列表中也将会是在之前。当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。而且这个就是然而，假设以下的数对将要以他们的第一个数字来排序。

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，而且这个就是但是稳定排序算法从来不会如此。而且这个就是不稳定排序算法可以被特别地实现为稳定。

作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，而且这个就是就会被决定使用在原先数据次序中的条目，而且这个就是当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

用选择法对10个整数由大到小排序要求画出流程图

选择排序的过程如下：

1. 从待排序的n个元素中找到最大的元素，将其与第n个元素交换位置。

2. 在剩余的n-1个元素中，再找到最大的元素，将其与第n-1个元素交换位置。

3. 重复上述步骤，直到只剩下一个元素为止。

其中，每经过一轮，就能确定出一个元素的位置。通过n-1轮选择，就能将这n个元素按照从大到小的顺序排好序。选择排序的时间复杂度为O(n^2)。

下面是使用C语言实现选择排序算法的示例代码：

#include 《stdio.h》

void selection_sort(int arr, int n)

{

int i, j, max_idx;

for (i = 0; i 《 n - 1; i++) {

max_idx = i;

for (j = i + 1; j 《 n; j++) {

if (arr) {

max_idx = j;

}

}

// 将找到的最大元素与当前位置交换

int temp = arr;

arr;

arr = temp;

}

}

int main()

{

int i, n;

int arr = {23, 4, 56, 77, 12, 45, 89, 34, 67, 90};

n = sizeof(arr) / sizeof(arr);

// 输出排序前的列表

printf("排序前：\n");

for (i = 0; i 《 n; i++) {

printf("%d ", arr);

}

printf("\n");

// 调用选择排序函数

selection_sort(arr, n);

// 输出排序后的列表

printf("排序后：\n");

for (i = 0; i 《 n; i++) {

printf("%d ", arr);

}

printf("\n");

return 0;

}

选排序流程图：

十大经典排序算法（动图演示） 之 桶排序

9、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法描述

9.2 图片演示

9.3 代码实现

9.4 算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

***隐藏网址***

基于比较的排序算法

基于比较的排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序。

1、冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历待排序的元素，比较相邻的两个元素，如果它们的顺序错误，就交换它们的位置。这个过程会一直重复，直到没有需要交换的元素为止。冒泡排序的时间复杂度为O（n^2），其中n是待排序元素的个数。

2、选择排序

选择排序的原理是首先在未排序的元素中找到最小（大）元素，将其与第一个元素交换位置。然后，再从剩余的未排序元素中找到最小（大）元素，将其与第二个元素交换位置。这个过程会一直重复，直到所有元素都排好序为止。选择排序的时间复杂度为O（n^2）。

3、插入排序

插入排序的原理是从第一个元素开始，该元素可以认为已经被排序。取出下一个元素，在已经排序的元素序列中从后向前扫描，找到相应的位置并插入。这个过程会一直重复，直到所有元素都排好序为止。插入排序的时间复杂度为O（n^2）。

4、希尔排序

希尔排序也称之为递减增量排序，是对插入排序的改进。它首先对待排序的元素按照一定的间隔进行分组，对每组元素进行插入排序。然后逐渐减小间隔，直到间隔为1时，就变成了普通的插入排序。希尔排序的时间复杂度为O（n log n）。

5、归并排序

归并排序是一种分治算法，它将待排序的元素每次分成两个子组，对每个子组进行排序，直至子组的元素个数为1。然后将排好序的子组合并成一个有序的数组。归并排序的时间复杂度为O（n log n）。

6、快速排序

快速排序也是一种分治算法，它选择一个基准元素，将待排序的元素分为小于基准元素的子数组和大于等于基准元素的子数组。然后对这两个子数组递归地进行快速排序。快速排序的时间复杂度为O（n log n）。

风靡全球的十大算法

作者 | George Dvorsky

编译 | 深度学习这件小事

1 排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。

稳定的

不稳定的

不实用的

2 傅立叶变换与快速傅立叶变换

傅立叶是一位法国数学家和物理学家，原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier于1807年在法国科学学会上发表了一篇论文，论文里描述运用正弦曲线来描述温度分布，论文里有个在当时具有争议性的决断：任何连续周期信号都可以由一组适当的正弦曲线组合而成。当时审查这个论文拉格朗日坚决反对此论文的发表，而后在近50年的时间里，拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号，如在方波中出现非连续变化斜率。直到拉格朗日死后15年这个论文才被发表出来。谁是对的呢？拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅立叶是对的。为什么我们要用正弦曲线来代替原来的曲线呢？如我们也还可以用方波或三角波来代替呀，分解信号的方法是无穷多的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。一个正余弦曲线信号输入后，输出的仍是正余弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的。且只有正余弦曲线才拥有这样的性质，正因如此我们才不用方波或三角波来表示。

3 Dijkstra 算法

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

4 RSA算法变换

RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。

5 安全哈希算法

一种对输入信息（例如消息）进行摘要的算法。摘要过程能够完成下列特点：不同的输入信息绝对不会具有相同的指纹：相近输入信息经过摘要之后的输出信息具有较大的差异，同时计算上很难生产一个与给定输入具有相同指纹的输入。（即不可逆）。

6 整数因式分解

这是在计算机领域被大量使用的数学算法，没有这个算法，信息加密会更不安全。该算法定义了一系列步骤，得到将一合数分解为更小因子的质数分解式。这被认为是一种FNP问题，它是NP分类问题的延伸，极其难以解决。许多加密协议（如RSA算法）都基于这样一个原理：对大的合数作因式分解是非常困难的。如果一个算法能够快速地对任意整数进行因式分解，RSA的公钥加密体系就会失去其安全性。量子计算的诞生使我们能够更容易地解决这类问题，同时它也打开了一个全新的领域，使得我们能够利用量子世界中的特性来保证系统安全。

7 链接分析

链接分析，源于对Web结构中超链接的多维分析。当前其应用主要体现在网络信息检索、网络计量学、数据挖掘、Web结构建模等方山。作为Google的核心技术之一，链接分析算法应用已经显现出j惊人的商业价值。

8 比例积分微分算法

你是否曾经用过飞机、汽车、卫星服务或手机网络？你是否曾经在工厂工作或是看见过机器人？如果回答是肯定的，那么你应该已经见识过这个算法了。大体上，这个算法使用一种控制回路反馈机制，将期望输出信号和实际输出信号之间的错误最小化。无论何处，只要你需要进行信号处理，或者你需要一套电子系统，用来自动化控制机械、液压或热力系统，这个算法都会有用武之地。可以这样说，如果没有这个算法，现代文明将不复存在。

9 数据压缩算法

在现今的电子信息技术领域，正发生着一场有长远影响的数字化革命。由于数字化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大，如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。

10 随机数生成

在统计学的不同技术中需要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模拟法计算的时候等等。

八大经典排序算法原理及实现

该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记录，每篇头部主要是另起博客的链接。

冒泡排序算法应该是大家第一个接触的算法，其原理都应该懂，但我还是想以自己的语言来叙述下其步奏：

按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2)
冒泡排序及其复杂度分析

空间复杂度就是在交换元素时那个临时变量所占的内存

给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为：

我们发现第一次外层循环之后就排序成功了，但是还是会继续循环下去，造成了不必要的时间复杂度，怎么优化？

冒泡排序都是相邻元素的比较，当相邻元素相等时并不会交换，因此冒泡排序算法是稳定性算法

插入排序是对冒泡排序的一种改进

插入排序的思想是数组是部分有序的，再将无序的部分插入有序的部分中去,如图：
（图片来自 这里 ）

空间复杂度就是在交换元素时那个临时变量所占的内存

插入排序的优化，有两种方案：

文章后面会给出这两种排序算法

由于插入排序也是相邻元素的比较，遇到相等的相邻元素时不会发生交换，也不会造成相等元素之间的相对位置发生变化

其原理是从未排序的元素中选出最小值(最大值)放在已排序元素的后面

空间复杂度就是在交换元素时那个临时变量所占的内存

选择排序是不稳定的，比如 3 6 3 2 4，第一次外层循环中就会交换第一个元素3和第四个元素2，那么就会导致原序列的两个3的相对位置发生变化

希尔排序算是改良版的插入排序算法，所以也称为希尔插入排序算法

其原理是将序列分割成若干子序列（由相隔某个 增量 的元素组成的），分别进行直接插入排序；接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序，我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理，真正的实现可以按下述步奏来：

希尔排序的效率取决于 增量值gap 的选取，这涉及到数学上尚未解决的难题，但是某些序列中复杂度可以为O(N 1.3)，当然最好肯定是O(N)，最坏是O(N 2)

空间复杂度就是在交换元素时那个临时变量所占的内存

希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化，所以希尔排序是不稳定的

理解堆排序，就必须得先知道什么是堆？

二叉树的特点：

当父节点的值总是大于子结点时为 最大堆 ；反之为 最小堆 ，下图就为一个二叉堆

一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2 i + 1)、(2 i + 2)

怎么将给定的数组序列按照堆的性质，调整为堆？

这里以建立最小堆为示例，

很明显对于其叶子结点来说，已经是一个合法的子堆，所以做堆调整时，子节点没有必要进行，这里只需从结点为A = 50的结点开始做堆调整，即从（n/2 - 1）位置处向上开始做堆调整：

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)，二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N * logN)。

空间复杂度就是在交换元素时那个临时变量所占的内存

由于堆排序也是跨越式的交换数据，会导致相同元素之间的相对位置发生变化，则算法不稳定。比如 5 5 5 ,堆化数组后将堆顶元素5与堆尾元素5交换，使得第一个5和第三个5的相对位置发生变化

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

快速排序在应该是大家经常看到、听到的算法，但是真正默写出来是有难度的。希望大家看了下面 挖坑填数 方法后，能快速写出、快速排序。

其原理就这么几句话，但是现实起来并不是这么简单，我们采取流行的一种方式 挖坑填数分治法

对于序列： 72 6 57 88 60 42 83 73 48 85

数组变为： 48 6 57 88 60 42 83 73 88 85
再重复上面的步骤，先从后向前找，再从前向后找：

数组变为： 48 6 57 42 60 72 83 73 88 85
可以看出a这二个子区间重复上述步骤就可以了

空间复杂度，主要是递归造成的栈空间的使用:

快速排序的优化主要在于基准数的选取

快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定

前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定
具体步骤，设数组为a：

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X》=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
所以，二分查找排序比较次数为：x=log2n
二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

二分查找排序在交换数据时时进行移动，当遇到有相等值插入时也只会插入其后面，不会影响其相等元素之间的相对位置，所以是稳定的

白话经典算法排序
冒泡排序选择排序
快速排序复杂度分析
优化的插入排序