八大排序算法（八大排序算法总结）

本篇文章给大家谈谈八大排序算法，以及八大排序算法总结对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、面试必会八大排序算法（Python）
• 2、常用的排序算法都有哪些？
• 3、排序方法有哪几种
• 4、几种排序算法的比较
• 5、八大算法
• 6、八大经典排序算法原理及实现

面试必会八大排序算法（Python）

一、插入排序

介绍

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

算法适用于少量数据的排序，时间复杂度为O(n^2)。

插入排算法是稳定的排序方法。

步骤

①从第一个元素开始，该元素可以认为已经被排序

②取出下一个元素，在已经排序的元素序列中从后向前扫描

③如果该元素（已排序）大于新元素，将该元素移到下一位置

④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤将新元素插入到该位置中

⑥重复步骤2

排序演示

算法实现

二、冒泡排序

介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

原理

循环遍历列表，每次循环找出循环最大的元素排在后面；

需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。

步骤

①比较相邻的元素。如果第一个比第二个大，就交换他们两个。

②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

③针对所有的元素重复以上的步骤，除了最后一个。

④持续每次对越来越少的元素态册重复上面的步骤，直到没有任何一对数字需要比较。

算法实现：

三、快速排序

介绍

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填数 + 分治法。

首先选出一个轴值(pivot，也有叫基准的)，帆租宏通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

实现步骤

①从数列中挑出一个元素，称为 “基准”（pivot）；

②重新排序数列，所有型没元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；

③对所有两个小数列重复第二步，直至各区间只有一个数。

排序演示

算法实现

四、希尔排序

介绍

希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。

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

·插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；

·但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。

基本思想

①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；

②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。

排序演示

算法实现

五、选择排序

介绍

选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。

基本思想

选择排序的基本思想：比较 + 交换。

第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；

第二趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；

以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

排序演示

选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。

算法实现

六、堆排序

介绍

堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

利用数组的特点快速指定索引的元素。

基本思想

堆分为大根堆和小根堆，是完全二叉树。

大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] =A[i]。

在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

排序演示

算法实现

七、归并排序

介绍

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

基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法思想

自上而下递归法（假如序列共有n个元素）

① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；

② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；

③ 重复步骤②，直到所有元素排序完毕。

自下而上迭代法

① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

④ 重复步骤③直到某一指针达到序列尾；

⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。

排序演示

算法实现

八、基数排序

介绍

基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m) ，其中 r 为采取的基数，而m为堆数。

在某些时候，基数排序法的效率高于其他的稳定性排序法。

基本思想

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。

LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

排序效果

算法实现

九、总结

各种排序的稳定性、时间复杂度、空间复杂度的总结：

平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；

从时间复杂度来说：

线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；

O(n1+§))排序，§是介于0和1之间的常数：希尔排序 ；

线性阶O(n)排序：基数排序，此外还有桶、箱排序。

常用的排序算法都有哪些？

排序算法 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

分类

在计算机科学所使用的排序算法通常被分类为：

计算的复杂度（最差、平均、和最好表现），依据串列（list）的大小（n）。一般而言，好的表现是O。(n log n)，且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。

记忆体使用量（以及其他电脑资源的使用）

稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且扮租在原本的串列中R出现在S之前，在排序过的串列中R也将会是在S之前。

一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。选择排序包含shaker排序和堆排序（heapsort）。

当相等的元素是冲缺拿无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1) (3, 1) (3, 7) (5, 6)

在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：

(3, 1) (3, 7) (4, 1) (5, 6) (维持次序)

(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个物件间之比较，就会被决定使用在原先资料次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

排列算法列表

在这个表格中，散搭n是要被排序的纪录数量以及k是不同键值的数量。

稳定的

冒泡排序（bubble sort） — O(n2)

鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)

插入排序 （insertion sort）— O(n2)

桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体

计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体

归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体

原地归并排序 — O(n2)

二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体

鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体

基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体

Gnome sort — O(n2)

Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体

不稳定

选择排序 （selection sort）— O(n2)

希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本

Comb sort — O(n log n)

堆排序 （heapsort）— O(n log n)

Smoothsort — O(n log n)

快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序

Introsort — O(n log n)

Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）

不实用的排序算法

Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。

Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体

Bead sort — O(n) or O(√n), 但需要特别的硬体

Pancake sorting — O(n), 但需要特别的硬体

排序的算法

排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

插入排序

冒泡排序

选择排序

快速排序

堆排序

归并排序

基数排序

希尔排序

插入排序

插入排序是这样实现的：

首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。

从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。

重复2号步骤，直至原数列为空。

插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。

冒泡排序

冒泡排序是这样实现的：

首先将所有待排序的数字放入工作列表中。

从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。

重复2号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。

选择排序

选择排序是这样实现的：

设数组内存放了n个待排数字，数组下标从1开始，到n结束。

i=1

从数组的第i个元素开始到第n个元素，寻找最小的元素。

将上一步找到的最小元素和第i位元素交换。

如果i=n－1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n²)的。

快速排序

现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。

堆排序

堆排序与前面的算法都不同，它是这样的：

首先新建一个空列表，作用与插入排序中的"有序列表"相同。

找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。

重复2号步骤，直至原数列为空。

堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。

看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。

平均时间复杂度

插入排序 O(n2)

冒泡排序 O(n2)

选择排序 O(n2)

快速排序 O(n log n)

堆排序 O(n log n)

归并排序 O(n log n)

基数排序 O(n)

希尔排序 O(n1.25)

冒泡排序

654

比如说这个，我想让它从小到大排序，怎么做呢？

第一步：6跟5比，发现比它大，则交换。564

第二步：5跟4比，发现比它大，则交换。465

第三步：6跟5比，发现比它大，则交换。456

[img]

排序方法有哪几种

排序方法有：

一、直接插入排序

原理携弯：从待排序的数中选出一个来，插入到前面的合适位置。

二、选择排序

与直接插入排序正好相反，选择排序是从待排序的数中选出最小的放在已经排好的后面，这个算法选数耗时。

三、快速排序

快速排序简称快排，是一种比较快的排序，适合基本无序的数据，为什么这么说呢？下面我说下快排的思路：设置两个指针：i和j，分别指向第一个和最后一个，i像后移动，j向前移动，选第一个数为标准（一般这样做，当然快排的关键就是这个“标准”的选取），从后面开始。

找到第一个比标准小的数，互换位置，然后再从前面，找到第一个比标准大的数，互换位置，第一趟的结果就是标准左边的都小于标准，右边的都大于标准（但不一定有辩搭闷序），分成两拨后，继续递归的使用上述方法，最终有序！

四、冒泡排序

冒泡排序是一种很简单，不论是理解还是时间起来都比较容易的一种排序算法，思路简单：小的数一点一点向前起泡，最终有序枝核。

五、归并排序

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

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

几种排序算法的比较

一、八大排序算法的总体比较

二、算法各自的特点（具体实现见后面博客）

1.快排

（1）算法思想

选择一个基准元素，将比基准元素小的元素放在其前面，比基准元素大的元素放在其后面，然后在将小于基准值元素的子数列和大于基准元素的子数列按原来的方法排序，直到整个序列有序;

（2）优缺点

优点：极快数据移动少；

缺点：不稳定；

（3）效率分析

此排序算法的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序；

（4）对于基准的选择

a.三数取中

具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴；

b.随机选取基准

引入原因：在待排序列是部分有序时，固定选取枢轴使快排效率低下；

具体思想：取在待排序列中任意一个元素作为基准；

（5）优化方法

a.当待排序序列的长度分割到一定大小后，使用插入排序；

原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排；

b.在一次分割结束后，可以把与key相等的元素聚集在一起，继续下次分割时，不必再对于key相等元素分割；

（6）应用场景

a.求数组中第k小的数

将数组中某一个元素m作为划分依据,即m=arr[0]。若m前面的元素个数大于k，则第k小的数一定在m前面的元素中，这时我们只需要继续在m前面的元素中找第k小的数；若m前面的元素小于k，则第k小的数一定在m后面的元素中，这时我们只需要在m后面的元素中找第k小的数；

2.冒泡排序

（1）基本原理灶埋镇

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。

（2）优缺点

优点：稳定

缺点：慢，每次只能移动两个相邻的数据；

3.插入排序

（1）基本思想

将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。即先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。

（2）优缺点

优点：稳定，快

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是数据量庞大的时候

4.堆排序

4.1、二叉堆定义：

二叉堆是完全二叉树或近似完全二叉树。二叉堆满足两个特性:

（1）父结点的键值总是大于或者等于（小于或者等于）任何一个子节点的键值；

（2）每个结点的左子树和右子树都是一个二叉堆；

当父结点的键值总是大于或者等于任何一个子节点的键值时为大根堆。当父结点的键值总是小于或等于任何一个子节点的键值时为小根堆；

4.2、堆的存储：

一般都用数组来表示堆，i结点的父结点下标就为（i-1）/2.它的左右子节点的下标分别为2*i+1和2*i+2.

4.3、堆的插入：

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中

（1）用大根堆排序的基本思想

先将初始数组建成一个大根堆，此对为初始的无序区；

再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足=的值；

由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值=的值，同样要将其调整为堆；

..........

直到无序区只有一个元素为止；

4.4：应用

寻找M个数中的前K个最小的数并保持有序；

时间复杂度：O(K)[创建K个元素最大堆的时间复杂度] +（M-K）*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

5.希尔排序

（1）基本思想

先将整个待排序元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）；

（2）适用场景

比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排液颤序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；

6.归并排序隐粗

（1）基本思想

首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止；

（2）适用场景

若n较大，并且要求排序稳定，则可以选择归并排序；

7.简单选择排序

（1）基本思想

第一趟：从第一个记录开始，将后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；

第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；

...........

第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到其中最小的记录和第i个记录进行交换；

以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录直接排在最后；

八大算法

算法中比较常用的有八种算法，基本算法的题，都是依靠这些基础算法或者结合使用出题的，所以要学会基础算法，才有可能去更好的掌握算法题。

插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。

基本思想：在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

希尔排序，又称缩小增量法。其基本思想是：

 1先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

    2当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

选择排序，即每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

如何进行堆排序呢？

步骤如下：

 1、将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但镇没是调整时被交换到最后的那个最大的数不参与向下调整。

 2、完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下型宴去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。

冒泡排序，该排序的命名非常形象，即一个个将气泡冒卜旅银出。冒泡排序一趟冒出一个最大（或最小）值。

快速排序是公认的排序之王，快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法，其基本思想为：

 任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。

归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。

计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。

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

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

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

按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为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[4] = 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[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了

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

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

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

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

具体步骤，设数组为a[0…n]：

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。

二分查找最坏时间复杂度：当2^X=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)

所以，二分查找排序比较次数为：x=log2n

二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

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

白话经典算法排序

冒泡排序选择排序

快速排序复杂度分析

优化的插入排序

关于八大排序算法和八大排序算法总结的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。