常见的排序算法

插入排序

直接插入排序希尔排序 选择排序

选择排序堆排序 交换排序

冒泡排序快速排序 归并排序快速排序为什么是不稳定的？

将数组中的所有元素依次和前面的已经排好序的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。
场景：

现有一个无序数组，共7个数：89 45 54 29 90 34 68。

使用直接插入排序法，对这个数组进行升序排序。

89 45 54 29 90 34 68
45 89 54 29 90 34 68
45 54 89 29 90 34 68
29 45 54 89 90 34 68
29 45 54 89 90 34 68
29 34 45 54 89 90 68
29 34 45 54 68 89 90

希尔排序也称缩小增量排序；希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时（用gap = gap/3+1 控制），保证了最后一次进行直接插入排序，算法终止。

直接插入排序是希尔排序gap=1的特例，另外，gap越大，值越大的容易到最后面，但是不太接近有序，一般gap不要超过数组大小的一半。

思想：在一个无序数组中选择出每一轮中最值元素，然后把这一轮中最前面的元素和min交换，最后面的元素和max交换；然后缩小范围（开始位置（begin++）++，最后位置（end–）–）,重复上面步骤，最终得到有序序列（升序）。

堆排序实际上是利用堆的性质来进行排序的，要知道堆排序的原理我们首先一定要知道什么是堆。

堆实际上是一棵完全二叉树，其满足两个性质：

堆的每一个父节点都大于（或小于）其子节点。堆的每个左子树和右子树也是一个堆。

堆的分类：

最大堆（大顶堆）：堆的每个父节点都大于其孩子节点。最小堆（小顶堆）：堆的每个父节点都小于其孩子节点。

由上面的介绍我们可以看出堆的第一个元素要么是最大值（大顶堆），要么是最小值（小顶堆），这样在排序的时候（假设共n个节点），直接将第一个元素和最后一个元素进行交换，然后从第一个元素开始进行向下调整至第n-1个元素。所以，如果需要升序，就建一个大堆，需要降序，就建一个小堆。

堆排序的步骤分为三步:

建堆（升序建大堆，降序建小堆）。交换数据。向下调整。

假设我们现在要对数组arr[]={8,5,0,3,7,1,2}进行排序（降序），首先要先建小堆：

堆建好了下来就要开始排序了：

从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。

算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。

快速排序采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。它的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2).

首先上图：

其实快速排序的思想就是通过第一遍的遍历（让left和right指针重合）来找到数组的切割点，快速排序的步骤如下：

首先我们从数组的left位置取出该数（20）作为基准（base）参照物。(如果是选取随机的，则找到随机的哨兵之后，将它与第一个元素交换，开始普通的快排)从数组的right位置向前找，一直找到比（base）小的数，如果找到，将此数赋给left位置（也就是将10赋给20），此时数组为：10，40，50，10，60，left和right指针分别为前后的10。从数组的left位置向后找，一直找到比（base）大的数，如果找到，将此数赋给right的位置（也就是40赋给10），此时数组为：10，40，50，40，60，left和right指针分别为前后的40。重复“第二,第三“步骤，直到left和right指针重合，最后将（base）放到40的位置， 此时数组值为：10，20，50，40，60，至此完成一次排序。此时20已经潜入到数组的内部，20的左侧一组数都比20小，20的右侧作为一组数都比20大，因此现在20所在的位置就是排序之后20的位置。以20为切入点，对20左右两边的序列按照"第一，第二，第三，第四"步骤进行，最终快排大功告成。

每个递归过程涉及三个步骤：

分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素。治理: 对每个子序列分别调用归并排序__MergeSort, 进行递归操作。合并: 合并两个排好序的子序列,生成排序结果。

假设待排序数组: a = [ 1, 2, 2, 3, 4, 5, 6 ];

在快速排序的随机选择比较子(即pivot)阶段：

若选择a[2]（即数组中的第二个2）为比较子，而把大于等于比较子的数均放置在大数数组中，则a[1]（即数组中的第一个2）会到pivot的右边， 那么数组中的两个2非原序（这就是“不稳定”）。

若选择 a[1] 为比较子，而把小于等于比较子的数均放置在小数数组中，则数组中的两个 2 顺序也非原序 。

这就说明，quick sort是不稳定的。