常用排序算法总结
图片来自极客时间专栏《数据结构与算法之美》
# 如何分析一个“排序算法”？
# 执行效率
最好情况、最坏情况、平均情况下的时间复杂度
时间复杂度的系数、常数、低阶
比较次数和交换（移动）次数
# 内存消耗
有些算法是“原地排序的”，空间复杂度是O(1)，即不需要开辟新的内存空间（或只需要开辟常数级的内存空间）。而有些算法需要辅助内存空间。
# 稳定性
如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变——稳定性
在对象数组中排序时更加需要注意，避免待排序对象字段相同时，排序结果发生意料外的改变。
# 排序算法
# 冒泡排序
# 思路
对一个N个元素的数组，遍历N次（优化后，如果已经提前排好序，可以<N），每次比较相邻元素，不满足大小关系则互换。每次冒泡，都会把最大/最小的元素确定下来
# 特点
是原地排序算法
每次比较时，大小相同的元素不交换，因此是稳定的
最好情况O(n)，已经有序；最坏情况O(n^2)，倒序；平均复杂度O(n^2)
# 插入排序
# 思路
把数组分为已排序区间和未排序区间，初始已排序区间只有一个元素（数组的第一个元素），取未排序区间的元素，在已排序区间中找到合适的位置插入，并保证已排序区间数据一直有序。
# 特点
是原地排序算法
对值相同的元素，可以把后出现的元素插入到同值的前面出现的元素后，保证原有顺序不变，因此是稳定的
最好情况O(n)，已排序；最坏情况O(n^2)，倒序；平均O(n^2)
# 选择排序
# 思路
把数组分为已排序区间，未排序区间，每次把未排序区间中最小的通过交换位置放在已排序区间的末尾。
# 特点
是原地排序算法
因为每次找最小值时交换位置，不能保证稳定性
由于不管是否有序，每次都需要找到未排序区间的最小值并交换，因此最坏、最好、平均复杂度都是O(n^2)
# 归并排序
# 思路
基于分治思想，把数组从中间不断分成两部分直到每部分只有一个元素，再对两部分分别排序，再把排好序的两部分合并在一起。
在合并两个已排好序的数组时，需要开辟一个长度为两数组长度之和的辅助数组，分别从两个数组头部开始比较，把较小的数字放入辅助数组。完成后再把辅助数组的值拷贝回原数组。
# 特点
需要开辟O(n)的内存空间，非原地排序工具
合并数组时，如果有相同的元素，可以把前半部分数据先放入辅助数组，这样就实现合并前后顺序不变。因此，是一个稳定的排序方法
最好、最坏、平均时间复杂度恒为O(nlogn)
# 快速排序
# 思路
选择任意一个数据作为分区点（pivot），遍历数组，把小于分区点的数据放在左边，把大于分区点的数据放在右边，对两个区域重复递归执行相同操作，区间长度为1时所有数组有序。
快速排序可以用巧妙的算法实现原地排序：
指针i代表pivot最后所在的位置，指针j代表当前处理的位置，算法最终要找到pivot应该待的位置，即i的位置。遍历数组，当j指向的元素小于pivot的值时，i、j元素互换，然后i右移一位，相当于记录小于pivot的元素个数。遍历完成后，把pivot和i的元素互换。
# 特点
是原地排序算法
由于涉及元素交换操作，相同元素位置会被改变，因此不是稳定的排序算法
大多数情况下时间复杂度是O(nlogn)，极差情况下，当数组已经有序，每次选择的分区点是最大的数，是O(n^2)
# 堆排序
# 背景知识
堆是一种特殊的树，它满足以下条件：
完全二叉树
每一个节点的值都大于（小于）等于其子树中每一个节点的值
每一个节点的值都大于等于其子树中每一个节点的值的堆，叫“大顶堆”；反之，叫”小顶堆“。
堆往往用数组存储，如图：
下标为i的节点的左子节点是2*i，右子节点是2*i+1，父节点是i/2。
# 往堆中插入元素
插入元素后，为了使堆满足堆的特性，需要进行堆化，堆化有从下往上和从上往下两种方式。
从下往上堆化时，让新插入的节点和父节点对比大小，如果不满足堆的特性，就互换两个节点，并重复该过程直到堆满足堆的特性。
从上往下堆化时，从第一个非叶子节点开始，依次进行以它为根节点的堆化。这里的从上往下堆化，不是指从堆顶开始堆化，而是指每个非叶子节点作为一个个堆顶的从上而下堆化。这种方法不光可以处理插入一个元素的情况，也适用于把无序数组构建成堆的情况。
# 删除堆顶元素
删除堆顶元素后，为了让堆满足堆的特性，如果直接把第二大的元素放到堆顶，最后堆化出来的堆可能并不是完全二叉树。
那就换种方法，直接把最后一个节点放在堆顶，然后从上到下比较父子元素的大小关系，不满足堆的特性则互换，直到满足堆的特性为止。
# 思路
堆排序可以分成两个大步骤：建堆和排序
# 建堆
建堆的过程可以看作往堆里一次次插入元素，可以使用往堆中插入元素的方法。
# 排序
建完堆后，堆顶元素就是最大的元素。把堆顶元素和最后一个元素交换，再通过堆化的方法把剩下的其他元素构建成堆，重复该步骤，数组就排序完毕了。
# 特点
是原地排序算法
在排序过程中，存在堆顶和最后一个元素互换的操作，相同值顺序可能被改变，因此不是稳定的
堆排序包含两个操作，建堆的时间复杂度是O(n)，排序的时间复杂度是O(nlogn)，因此整体时间复杂度是O(nlogn)
# 快速排序 vs 归并排序
快速排序的处理是由上到下的，每次找出分区点，然后就进行移动操作，再对新出现的两个分区重复步骤；归并排序的处理是由下到上的，先把数组拆分完全后，再一步步合并拼接成最终数组。
归并排序虽然是稳定的O(nlogn)时间复杂度，但是它是非原地排序算法，相比快速排序需要占用内存。
# 快速排序 vs 堆排序
在实际开发中，快速排序比堆排序性能好，有两方面原因：
堆排序数据访问方式没有快速排序好
快速排序中数据是顺序访问的，而堆排序时数据是跳着访问的，这不利于CPU的缓存
对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
# 排序算法的优化
# 优化快速排序
快速排序出现时间复杂度糟糕的情况，主要原因是分区点选的不合理。因此，选择更好的分区点，就可以优化平均排序时间。
有两个比较简单的分区算法：
三数取中
从区间首、尾、中间分别取出一个数，比较大小，把三个数的中间值作为分区点，这样肯定比直接取一个值更好，不会取到最差的值。数组比较大时，也可使用“五数取中”、“十数取中”
随机法
直接随机选择一个元素作为分区点，从概率来讲，虽然不太可能选中最好的，但是也很难选中最差的，保证平均情况下的时间复杂度。