排序（二）希尔排序、归并排序、快速排序

网上有关“排序（二）希尔排序、归并排序、快速排序”话题很是火热，小编也是针对排序（二）希尔排序、归并排序、快速排序寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。

希尔排序是对插入排序的优化。希尔排序的思想：先使用数组中任间隔为h的元素有序，然后对全局进行排序。

h该怎么取值呢？如果数组长度比较小，则可设置 h=3，h=1。若数组长度比较大，可以取 h=4，但最终还是得对全局进行排序：h=1。但如果数组很长呢？则可以设置 h=10，h=4，h=1。那如果再来一个数组更加大的呢？则可以对h=22，h=10，h=4，h=1（全局排序）进行排序。所以说h的取值是一个递增序列。

我们要对一个大规模的数组进行间隔排序，再全局排序（h=1），最终得到有序的数组。

我们用其中最常用的这个。对应的时间复杂度是： 。（不推倒了，记一下）

data数组有16个元素，下面是对data中的元素进行排序：

h=4时，

开始：i从i=4，即i从数组第5个元素开始；j=i 比较j和j-4，如果是升序的，就不做任何交换了。

下一个元素：i=5，j从i开始，比较j和j-4，看是否需要交换。

...

i=8，j从i开始，将j，j-4，j-8，(间隔为4的元素)的进行排序。排序过程：先将j和j-4比较，看是否需交换；再将j-4和j-8进行比较，看是否需要交换。

....

h=1时，

开始：i从i=1，j从i开始，比较j和j-1，看是否需要交换。

i=2，j从i开始，将j，j-1，j-2，(间隔为1的元素)的进行排序。排序过程：先将j和j-1比较，看是否需交换；再将j-1和j-2进行比较，看是否需要交换。

....

i=13，j从i开始，将j，j-1，j-2，... (间隔为1的元素)的进行排序。排序过程：先将j和j-1比较，看是否需交换；再将j-1和j-2进行比较，看是否需要交换...

为了降低空间复杂度，也可以这样写：

另一种写法，开始时，将data中元素拷贝到tmp中，再对data中的元素进行操作。

归并排序总时间=子序列排好序时间+合并时间

自底向上的归并排序不是重点，把之前的那个自顶向下的归并排序弄精通了就行啦。

找到一个pivot分区点，将小于分区点的排到pivot前面，将大于分区点的排到pivot后面。

那么，如何将左边的子数组排序？还是在子数组里选择一个分区点，将小于分区点的放到前面，大于分区点的放到后面。

递推公式：sort(data, lo, hi)

当分区点选择不合理，快排的时间复杂度退化为 。比如，在升序序列中，将最后一个元素设为pivot。

当数组中有大量重复元素，上述方法会增加不必要的排序。

数据结构-八大排序算法的时间复杂度 稳定性

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

点击以下查看大图：

关于时间复杂度

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

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

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

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

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模 k："桶"的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

包含以下内容：

1、冒泡排序 2、选择排序 3、插入排序 4、希尔排序 5、归并排序 6、快速排序 7、堆排序 8、计数排序 9、桶排序 10、基数排序

排序算法包含的相关内容具体如下：

冒泡排序算法

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

选择排序算法

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

插入排序算法

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

希尔排序算法

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

归并排序算法

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

快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

堆排序算法

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

计数排序算法

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

桶排序算法

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

基数排序算法

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

希尔排序的时间复杂度

1：直接插入排序：

最好：待排序已经有序， 从前往后走都不用往里面 插入。 时间复杂度为o(n)

最坏：待排序列是逆序，每一次都要移位插入。 时间复杂度o(n^2)

是稳定排序

2：希尔排序：

最好：缩小增量的插入排序，待排序已经有序。时间复杂度o(n）

一般：平均时间复杂度o(n 1.3)，最差也是时间复杂度o(n 1.3)

不稳定排序

3：冒泡排序：

最好：待排序已经有序。时间复杂度o(n）

最坏：待排序是逆序。时间复杂度o(n^2）

稳定排序

4：快速排序：

最好：待排序无序。时间复杂度o(nlogn)

最坏: 待排序已经有序，基准定义在开始。 时间复杂度为o(n^2)

不稳定排序

5：直接选择排序：

无论好坏:o(n^2)

稳定排序

6：堆排序：

无论好坏：时间复杂度o(nlogn)

不稳定排序

7：归并排序：

稳定排序

8：基数排序：

无论好坏:o(d(n+r)) ，r为基数，d为位数.

稳定排序

希尔排序的希尔分析

希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。 扩展资料

　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的'倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量。

　该方法实质上是一种分组插入方法。比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

　一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

　给定实例的shell排序的排序过程：

　假设待排序文件有10个记录，其关键字分别是：

　49，38，65，97，76，13，27，49，55，04。

　增量序列的取值依次为：

　5，2，1

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

关于“排序（二）希尔排序、归并排序、快速排序”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！