基本概念

数据排序 – 将一个文件的记录按关键字不减（或不增）次序排列，使文件成为有序文件，此过程称为排序。

稳定排序 – 若排序后，相同关键字的记录保持它们原来的相对次序，则此排序方法称为 稳定排序。

如果在一个待排序的序列中，存在2个相等的数，在排序后这2个数的相对位置保持不变，那么该排序算法是稳定的；否则是不稳定的。 举个例子 　　对五个学生（A,B,C,D,E）进行成绩排序，他们的成绩分别为：80，98，89，98，72，按成绩从高到低排（98,98,89,80,72）

若排序结果是：B,D,C,A,E 代表算法是稳定的（B,D的相对位置没有变化）

若排序结果是：D,B,C,A,E 代表算法是不稳定的（B,D的相对位置发生了变化）

不稳定排序 – 若排序后，相同关键字的记录 不能 保持它们原来的相对次序，则此排序方法称为 不稳定排序。

排序类型（使用存储的角度）： 1.内部排序：全部数据存于内存 2.外部排序：需要对外存进行访问的排序过程

排序的分类及常用算法：

1.直接插入排序

插入排序算法可以对指定序列完成升序（从小到大）或者降序（从大到小）排序，对应的时间复杂度为O(n2)

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
5. 若待排序的记录数量非常大的时候，一般不选用直接排序。

以下内容来自于：http://c.biancheng.net/algorithm

个人觉得内容已经非常详尽了。

插入排序算法的实现思路是：初始状态下，将待排序序列中的第一个元素看作是有序的子序列。从第二个元素开始，在不破坏子序列有序的前提下，将后续的每个元素插入到子序列中的适当位置。

举个简单的例子，用插入排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的过程如下：

1. 将第一个元素 14 看作是一个有序的子序列 {14}，将剩余元素逐个插入到此序列的适当位置：

2. 将 33 插入到 {14} 中，由于 33 > 14，所以 33 应该插入到 14 的后面，新的有序序列变为 {14, 33}；

3. 将 27 插入到 {14, 33} 中，由于 27 < 33 同时 27 > 14，所以 27 应该插入到 14 和 33 的中间，新的有序序列变为 {14, 27, 33}；

4. 将 10 插入到 {14, 27, 33} 中，经过依次和 33、27、14 比较，最终断定 10 应该插入到 14 之前，新的有序序列变为 {10, 14, 27, 33}；

5. 将 35 插入到 {10, 14, 27, 33} 中，由于 35 > 33，所以 35 应该插入到 33 之后，新的有序序列变为 {10, 14, 27, 33, 35}；

6. 将 19 插入到 {10, 14, 27, 33, 35} 中，经过依次和 35、33、27、14 比较，最终断定 19 应该插入到 14 和 27 之间，新的有序序列变为 {10, 14, 19, 27, 33, 35}；

7. 将 42 插入到 {10, 14, 19, 27, 33, 35} 中，由于 42 > 35，所以 42 应插入到 35 之后，新的有序序列变为 {10, 14, 19, 27, 33, 35, 42}；

8. 将 44 插入到 {10, 14, 19, 27, 33, 35, 42} 中，由于 44 > 42，所以 44 应插入到 42 之后，新的有序序列变为 {10, 14, 19, 27, 33, 35, 42, 44}。

经过将各个待排序的元素插入到有序序列的适当位置，最终得到的就是一个包含所有元素的有序序列。

特点：插入排序算法是通过比较元素大小和交换元素存储位置实现排序的，比较大小和移动元素的次数越多，算法的效率就越差。

例题：

2.希尔排序

希尔排序又叫做缩小增量排序，它通过比较相距一定间隔（gap=x）的元素来工作，间隔随着算法的进行而减小，知道只比较相邻元素（gap=1）的最后一趟为止。

所以希尔排序不是唯一的，他会根据增量序列的不同而不同。希尔排序有一个性质：使用大增量序列排好的顺序，在变成小增量序列时不会改变之前的有序性。

希尔排序实际上是插入排序的一种优化。

希尔排序算法又叫缩小增量排序算法，是一种更高效的插入排序算法。和普通的插入排序算法相比，希尔排序算法减少了移动元素和比较元素大小的次数，从而提高了排序效率。

希尔排序算法的实现思路是：

• 将待排序序列划分成多个子序列，使用普通的插入排序算法对每个子序列进行排序；
• 按照不同的划分标准，重复执行第一步；
• 使用普通的插入排序算法对整个序列进行排序。

按照这个思路，我们尝试对 {35, 33, 42, 10, 14, 19, 27, 44} 做升序排序，具体的实现流程是：

1. 间隔 4 个元素，将整个序列划分为 4 个子序列：

采用插入排序算法分别对 {35, 14}、{33, 19}、{42, 27}、{10, 44} 进行排序，最终生成的新序列为：

2. 间隔 2 个元素，再次划分整个序列：

采用插入排序算法分别对 {14, 27, 35, 42} 和 {19, 10, 33, 44} 进行排序：

3. 采用插入排序算法对整个序列进行一次排序，过程如下：

间隔设置为多少合适呢：

待排序序列如何进行划分，划分多少次，都会影响到希尔排序算法的执行效率。

希尔排序算法没有固定的划分标准。

一般可以按要对比序列长度的的1/3作为开始gap；每轮再取1/3作为gap；直到最终gap=1(若gap=0是gap=1)；

或者可以按要对比序列长度的的1/2作为开始gap；每轮再取1/2作为gap；直到最终gap=1；

一张图解释：

3.直接选择排序

选择排序的基本思想：每一次在n-i+1(i=1,2,3,...,n-1)个记录中选取键值最小的记录作为有序序列的第i个记录。

对数据量较少的序列实现升序或降序排序，可以考虑使用选择排序算法，它对应的时间复杂度为O(n^2)。

排序算法对含有 n 个元素的序列实现排序的思路是：每次从待排序序列中找出最大值或最小值，查找过程重复 n-1 次。对于每次找到的最大值或最小值，通过交换元素位置的方式将它们放置到适当的位置，最终使整个序列变成有序序列。

举个例子，我们使用选择排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 完成升序排序，需要经历以下几个步骤：

1. 遍历整个待排序序列，从中找到最小值 10 并与第一个元素 14 交换位置：

2. 待排序序列变成 {33, 27, 14, 35, 19, 42, 44}，从中找到最小值 14 并与 33 交换位置：

3. 待排序序列变成 {27, 33, 35, 19, 42, 44}，从中找到最小值 19 并与 27 交换位置：

4. 待排序序列变成 {33, 35, 27, 42, 44}，从中找到最小值 27 并与 33 交换位置：

5. 待排序序列变成 {35, 33, 42, 44}，从中找到最小值 33 并与 35 交换位置：

6. 待排序序列变成 {35, 42, 44}，从中找到最小值 35，它的位置无需变动：

7. 待排序序列变成 {42, 44}，从中找到最小值 42，它的位置无需变动：

对于包含 n 个元素的待排序序列，选择排序算法中只需要找出 n-1 个“最小值”，最后剩下的元素的值必然最大。由此，我们就得到了一个升序序列 {10, 14, 19, 27, 33, 35, 42, 44}。

选择排序算法可以看作是冒泡排序算法的“改良版”。和后者相比，选择排序算法大大减少了交换数据存储位置的操作。

例题：

4.堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

基本思想：利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

算法过程(以大顶堆为例)：

① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点 ② 依次将根节点与待排序序列的最后一个元素交换 ③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

•升序：建大堆

•降序：建小堆

2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

算法图解（以下面的一道题目为例）：

判断序列（28，75，33，68，25，56，47，99，86，36）是否为堆？如果不是，则把它调整为堆（最小堆）。

到这里；题目的问题就可以完成解答了；答案就是图1.e_2。

接下来，我们继续；以题目的示例完成堆序列的最终堆排序。

以上内容就是整个堆排序的过程说明（小顶堆）。

• 平均时间复杂度：O(nlog_2{n})
• 稳定性：不稳定
• 空间：O(1)(仅需一个记录大小的供交换用的辅助存储空间。)

堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1…n]中选择最大记录，需比较n-1次，然后从R[1…n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。

例题：

5.冒泡排序

冒泡排序是所有排序算法中最简单、最易实现的算法，有时也称为起泡排序算法。

冒泡排序是一种交换排序的方法，其过程是首先将第一个记录的键值和第二个记录的键值进行比较，出现逆序，则将这两个记录交换，然后继续比较低二个和第三个记录的键值。依次类推，直到完成第n-1个记录和第n个记录的键值比较交换为止。这个过程称为 起泡。

算法示例：

例如，从 {14, 33, 27, 35, 10} 中找到最大值 35 的过程如下：

1. 比较 14 和 33 的大小，显然后者更大，不需要交换它们的位置，序列不发生改变。

2. 比较 33 和 27 的大小，前者大于后者，交换它们的位置，新的序列如下图所示。

3. 比较 33 和 35 的大小，后者更大，不需要交换它们的位置，序列不发生改变。

4. 比较 35 和 10 的大小，前者大于后者，交换它们的位置，新的序列如下图所示。

可以看到，序列中值最大的元素 35 被移动到了序列的末尾。整个查找最大值的过程中，最大的元素就像水里的气泡一样，一点一点地“冒”了出来，这也是将该算法命名为冒泡排序算法的原因。

采用同样的方法，我们可以很轻松地从 {14, 27, 33, 10} 中找到最大值 33。找到 33 后的新序列为：

从 {14, 27, 10} 中找到最大值 27 后，新的序列如下图所示：

从 {14, 10} 中找到最大值 14 后，新的序列如下图所示：

所有比 10 大的数都被一一找到，所以 10 必然是最小的数，这也是为什么“对 n 个数据进行排序，找最大值的过程只重复 n-1 次”的原因。

例题：

6.快速排序

提到排序算法，多数人最先想到的就是快速排序算法。快速排序算法是在分治算法基础上设计出来的一种排序算法，和其它排序算法相比，快速排序算法具有效率高、耗费资源少、容易实现等优点。

快速排序是交换排序的一种，实质上是对冒泡排序的一种改进。

要点：用第一个数字，依次和后面的每个比较，然后拆分成2部分，一部分小于等于，一部分大于，依次类推即可。

快速排序算法的实现思路是：

• 从待排序序列中任选一个元素（假设为 pivot）作为中间元素，将所有比 pivot 小的元素移动到它的左边，所有比 pivot 大的元素移动到它的右边；（相同的数可以到任一边）
• pivot 左右两边的子序列看作是两个待排序序列，各自重复执行第一步。直至所有的子序列都不可再分（仅包含 1 个元素或者不包含任何元素），整个序列就变成了一个有序序列。

真正实现快速排序算法时，我们通常会挑选待排序序列中第一个元素或者最后一个元素作为中间元素。

这里给大家讲解一种方法：

以 {35, 33, 42, 10, 14, 19, 27, 44, 26, 31} 为例，选择 31 作为中间元素，具体的实现过程为：

1. 建立 2 个指针（命名为 lo 和 hi），分别指向序列中第一个元素和倒数第 2 个元素，如下图所示：

2. lo 指针向右移动，当指向的元素不小于 31 时暂停。显然，当前指向的 35 > 31，所以 lo 暂时不移动；

3. hi 指针向左移动，当指向的元素不大于 31 时暂停。显然，当前指向的 26< 31，所以 hi 暂时不移动；

4. 交换 lo 和 hi 所指元素的位置，如下图所示：

5. 重复执行 2~4 步，直至 lo ≥ hi。此时，将 pivot 元素与 lo 所指元素交换位置。下面的动画演示了整个分割的过程：

可以看到，最终元素 31 左侧的元素都比它小，右侧的元素都比它大。

算法实现的图解过程：

实现1：

这种实现细节比较多；也就是代码写起来较为麻烦。

实现2：

例题：

7.归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

基本思想：

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

归并算法算是很好理解的了；

这两篇文章内容已经很详尽了：

https://blog.csdn.net/justidle/article/details/104203958

https://zhuanlan.zhihu.com/p/124356219

例题：

8.计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。通过计数将时间复杂度降到了O(N)

基本思想：

计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理：

① 分配。扫描一遍原始数组，以当前值-minValue作为下标，将该下标的计数器增1。 ② 收集。扫描一遍计数器数组，按顺序把值收集起来。

限制：它只能对整数进行排序。

图解：

9.桶排序（Bucket sort）或箱排序

桶排序是计数排序的升级版，也是一种非比较排序的方法。

工作的原理：是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。

什么时候最快？

当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢?

当输入的数据被分配到了同一个桶中。

算法图解：

10.基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

• MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
• LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

实现逻辑：

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

图解(以LSD为例):

算法复杂度对比

类别	排序方法	时间复杂度			空间复杂度	稳定性	复杂性	特点
		最好	平均	最坏	辅助存储		简单
插入 排序	直接插入	O(N)	O(N2)	O(N2)	O(1)	稳定	简单
	希尔排序	O(N)	O(N1.3)	O(N2)	O(1)	不稳定	复杂
选择 排序	直接选择	O(N)	O(N2)	O(N2)	O(1)	不稳定
	堆排序	O(N*log2N)	O(N*log2N)	O(N*log2N)	O(1)	不稳定	复杂
交换 排序	冒泡排序	O(N)	O(N2)	O(N2)	O(1)	稳定	简单	1、冒泡排序是一种用时间换空间的排序方法，n小时好 2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级 3、最好的情况是数据本来就有序，复杂度为O(n)
	快速排序	O(N*log2N)	O(N*log2N)	O(N2)	O(log2n)~O(n)	不稳定	复杂	1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。 2、划分之后一边是一个，一边是n-1个， 这种极端情况的时间复杂度就是O(N^2) 3、最好的情况是每次都能均匀的划分序列，O(N*log2N)
归并排序		O(N*log2N)	O(N*log2N)	O(N*log2N)	O(n)	稳定	复杂	1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。
基数排序		O(d(r+n))	O(d(r+n))	O(d(r+n))	O(rd+n)	稳定	复杂
注：r代表关键字基数，d代表长度，n代表关键字个数

本人能力有限，文中内容难免有纰漏，真诚欢迎大家斧正~

喜欢本文的朋友请三连哦！！！

另外本文也参考了网络上其他优秀博主的观点和实例，这里虽不能一一列举但内心属实感谢无私分享知识的每一位原创作者。