浅谈常用数据结构

冒泡排序
冒泡排序（Bubble Sort）算法是所有排序算法中最为简单的一种。其基本思想就是通过不停比较交换将当前最大或最小值交换至前方位置完成对所有数据的排序。其排序流程如下：

对数组中的每个位置依次进行两两比较。
如果前面数据大于后面数据就交换2个位置的值信息。经过一轮比较最大的值就被交换至最前面的位置。
在用同样的方法对剩下的数组位置进行两两比较交换，最后便可按照从小到大的顺序排好数据各数据。

冒泡排序

选择排序
选择排序（Selection Sort）也是比较简单的排序算法之一，其基本思想就是通过每次在数据集中选择最小的值与前方的数据进行交换来完成所有数据的排序。其排序流程如下：

从数组内选择最小的一个数据，并且与数组中第一个数据进行位置交换。
从剩下的数据内选择最小的一个数据，并且与数组内第二个数据进行位置交换。
依次重复上述步骤，直到最后两个数据完成交换。

选择排序

插入排序
插入排序（Insertion Sort）其基本思想就是将未排序的数据依次插入到前方以已排好序的合适的位置中。其排序流程如下：

对数组中前2个数据进行比较判断是否交换位置
将第三个数据依次向前2个数据进行比较，如果出现该数据大于比较的数据时，则将数据插入到该比较的数据后方。
然后第四个数据依次向前3个数据进行比较，判断选择合适的插入位置。
不断重复上述过程，知道最后一个数据插入到合适的位置，完成对原始数据的排序。

(1).当数据规模小的时候非常高效。
(2).当给定数据已经有序时的时间代价为O(N)

插入排序

希尔排序
对于大量的数据需要排序时，往往需要寻求更为高效的排序算法，希尔排序（Shell Sort）算法便是其中一种。希尔排序算法严格来说是基于插入排序的思想，其又称为缩小增量排序。希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。它是基于插入排序的改造而来的（第一个突破O(n^2)的排序）其流程如下：

将有n个元素的数组分成n/2个数字序列，第i个元素与每间隔n/2的元素为一组。
一次循环将每个序列对利用插入排序排好序。
然后，再变成n/4个序列，第i个元素与每间隔n/4的元素为一组，再次排序。
不断重复上述过程，随着序列减少最后变成一个，也就完成了整个排序。

Shell排序可以理解为插入排序的变种，它充分利用了插入排序的两个特点：
(1).当数据规模小的时候非常高效。
(2).当给定数据已经有序时的时间代价为O(N)
所以，Shell排序每次把数据分成若干块，来使用插入排序，而且之后在这若干个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停的合并小块，直到最后一个块，并使用插入排序。

在这里插入图片描述

快速排序
快速排序（Quick Sort）与冒泡排序类似都是基于交换排序的思想。快速排序对冒泡排序进行改进，从而具有更高的执行效率。其主要流程如下：

首先选取一个值作为分界值，通过该分界值将数组分为左右两个部分。
将大于分界值的数据集中移动到数组右边，小于等于分界值的数据集中移动到数组的左边。此时，左边部分中各元素都小等于分界值，而右边部分中各元素都大于分界值。
然后对于左侧的数组数据，又可以选取一个值作为分界值，将该数组划分成为左右两部分，同样将左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程直到每个小数组只剩2个元素进行排序，即完成整个快速排序。
整个排序过程是基于分界值进行数据交换，因此对于杂乱无章的数据具有高效性，而具有一定排序性的数据效率并不高。

在这里插入图片描述

堆排序
堆排序（ Heap Sort）算法是基于选择排序思想的算法，其利用堆结构和二叉树的一些性质来完成数据的排序。
堆排序的关键是构建堆结构，堆结构是一种树结构，准确地说是一个完全二叉树。并且每个结点应满足以下条件：

如果按照从小到大的顺序排序，要求非叶结点的数据要大于或等于其左、右子结点的数据。
如果按照从大到小的顺序排序，要求非叶节点的数据要小于或等于其左、右子结点的数据。

一个完整的堆排序需要经过反复的两个步骤：构造堆结构和堆排序输出。具体步骤如下：

构建堆时，通过将元素放在堆末端，然后依次向上比较是否大于或小于父结点，若是则进行交换。
完成堆结构的构建
进行堆元素取出时，则直接取出堆前端元素，然后将将堆末端防止堆前端中，然后依次判断结点与子节点的关系是否大于（或小于）如是则如果左子节点比右子节点大（或者小）则与左节点交换，反之则与右结点交换以便将节点进行下沉，将最大（最小）值进行上浮。

由上述步骤可知该树节点具有一定的顺序性，因此对于有一定顺序性的数据集具有良好的效率，而对于杂乱无章的数据集效率较低。

堆排序

合并排序
合并排序（Merge Sort）算法就是将多个有序数据表合成一个有序数据表。对于一个原始的待排序序列，往往可以通过分割的方法来归结为多路合并排序。合并排序的具体步骤如下：

首先将含有n个节点的待排序数据序列看做由n个长度为1的有序子表组成，将其依次两两合并，得到长度为2的若干有序子表。
再对这些子表进行两两合并，得到长度为4的若干有序子表，重复上述过程。

对有序子表的两两归并涉及到二路归并算法，二路归并具体步骤如下：

首先比较2个子表的第一个元素，判断移动指针指向那个子表。
取出第一个元素后，判断移动指针下个元素是否大于或小于另一个表的指针指向，若不是则移动指针并取出接下来的元素，若是则改变为另一个子表为移动指针并且取出元素。
通过反复上述步骤，将所有元素取出则完成对2个有序子表的排序。

二路归并

归并算法

排序算法的效率问题

在排序算法中还有一个特殊的概念，即稳定排序算法。稳定排序算法主要依照相等的关键字维持记录的相对次序来进行排序。通俗来讲，对于两个有相等关键字的数据D1和D2，在待排序的数据中D1出现在D2之前，在排序过后的数据中D1也在D2之前，那么这就是一个稳定排序算法。比如说对数据 [{name:小明,age:10},{name:小张,age:10},{name:小红,age:8}] 进行对字段age升序排序后使得数据集呈现 [{name:小红,age:8},{name:小明,age:10},{name:小张,age:10}] 则为稳定算法而使得数据集呈现[{name:小红,age:8},{name:小张,age:10},{name:小明,age:10}] 则为不稳定算法。
没有一种排序算法是绝对好的，不同的排序算法各有优劣。在实际应用中，需要根据实际的问题来选择合适的排序算法。如果数据流n较小，可采用插入排序或者选择排序法；当数据量n较大时，则应采用时间复杂度为O（nlogn）的排序方法，如快速排序、堆排序或合并排序。如果待排序的原始数据呈随机分布，那么快速排序算法的平均时间最短。

排序算法比较