初级排序算法

选择排序

描述： 伪代码： 算法分析：

插入排序

描述：就像我们整理扑克牌一样，从左往右从小往大，一张一张的依次将牌插入正确的位置上。 伪代码：

**算法分析：**插入排序的时间复杂度与输入元素的初始顺序有很大的关系。平均情况下是平方级别，最好情况下是线性级别。

对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要～N2/4次比较以及～N2/4次交换。最坏情况下需要～N2/2次比较和～N2/2次交换，最好情况下需要N-1次比较和0次交换。

希尔排序

希尔排序是基于插入排序的快速排序算法。为了解决插入排序只会交换相邻的元素，当最小的元素在数组的最后边时需要交换N-1次。希尔排序交换不相邻的元素，从而加快插入排序处理的速度。 核心思想是使数组中间隔为h的元素都是有序的。

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。

算法性能：

INFO

希尔排序的性能并不好准确分析。 备注：也给自己带来新的理解，并不是所有的算法我们都能准确分析它的时间复杂度

归并排序

归并的意思是将两个有序的子数组归并成一个更大的有序数组。 自顶向下的归并排序：将一个数组递归的一分为二再进行排序，然后再将有序的子数组归并成一个更大的数组。

快速排序

快速排序是一种分治的排序算法。基本思想是将一个数组切分为两个子数组，当这两个子数组有序时，整个数组就有序了。其中切分是选择一个切分元素J，使得切分后的两个数组满足左边数组的元素全部小于J，右边数组的元素全部大于J。性能特点：

• 快速排序需要的内存较少，
• 命题K：将长度为N的无重复数组排序，快速排序平均需要**~2InN次**比较（以及1/6的交换）
• 命题L：快速排序最多需要约N2/2次比较，但随即打乱数组能够预防这种情况。

优先队列

优先队列是为了解决这类场景：需要元素部分有序，或者不要求元素一次性排好序。比如我们需要从10亿个元素中选出最大的10个，此时如果我们对所有的元素排序的代价就会太大。

优先队列是一种抽象数据类型，最重要的操作是：

• 删除最大元素，
• 插入元素

优先队列的初级实现（基于链表或数组）

使用无序序列是解决这个问题的惰性方法，我们仅在必要的时候才会采取行动（找出最大元素）；使用有序序列则是解决问题的积极方法。

二叉堆实现优先队列

二叉堆的定义

数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个（子元素）特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推。

INFO

定义：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。

根据二叉树的定义，二叉树有一些很好的性质，而这些性质对于我们实现优先队列很有帮助。

1. 根节点是最大的，而最小的元素肯定出现在最下边的一层。
2. 用数组来表示二叉树时，我们可以根据节点的位置（索引），可以方便的获得其父节点和子节点的位置。位置k的结点的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1

INFO

**命题P。**一棵大小为N的完全二叉树的高度为[lgN]。 **证明。**通过归纳很容易可以证明这一点，且当N达到2的幂时树的高度会加1。

堆的算法

优先队列最重要的两个操作是：插入元素、删除最大元素 使用二叉堆来实现优先队列主要要解决的就是两个问题：

• 插入元素后保证堆有序（由下至上的堆有序）
• 删除元素和保证堆有序（由上至下的堆有序）

由下至上的堆有序（上浮）

基本思想是不断地比较子节点与其父节点的大小，如果子节点的大于父节点，则交换位置，再重复的进行这个过程，直到堆有序。 上浮的算法实现： 上浮算法对于插入元素这个操作很有用：

由上至下的堆有序（下沉）

由上至下的堆有序算法对于优先队列中删除最大元素的操作很有用，因为：我们可以将根元素（最大元素）删除，并将数组中最后一个元素放置在根元素，然后进行下沉的算法，最后使得堆有序。 下沉算法实现：

private void sink(int k){
    while(2*k <= N){ // k不超过数组大小
        int j = 2*k //k的左子节点
        // 比较k的左子节点与右子节点大小
        if(j < N && less(j,j+1)) {
            // 将j设为较大的子节点的值
            j++
        } ;
        // 当K已经比两个子节点都大时,返回
        if(!less(k,j)) break;
        k = j;
    }
}

删除最大元素的操作如下：

INFO

命题Q。对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过（lgN+1）次比较，删除最大元素的操作需要不超过2lgN次比较。 **证明。**由命题P可知，两种操作都需要在根结点和堆底之间移动元素，而路径的长度不超过lgN。对于路径上的每个结点，删除最大元素需要两次比较（除了堆底元素），一次用来找出较大的子结点，一次用来确定该子结点是否需要上浮。

索引优先队列

注：这里的内容看算法4书上有些不理解，部分内容取自网上

索引优先队列是一个比较抽象的概念，它是一个优先队列，又带有索引，这个索引是用来干什么的呢？ 考虑上面图中的情况，将小明、小龙、小花三人的分数进行排序，进入优先队列后，我们只能知道分数的排布，但却没法知道小明是排在那个位置（对应关系）； 这也是队列的一个缺点，我们无法知道队列中的第m个元素到底对应我们把所有元素加入优先队列之前的哪一个？

索引优先队列是通过一个数组保存某个元素在优先队列中的位置，从而允许引用队列中的元素。 例如：

prirotyQueue[i] = j; //索引优先队列的第i个元素的值是j
Index[j] = i; //那么，我们需要的这个元素j在优先队列中的位置就是i

实现原理： 索引优先队列的实现很巧妙，通过维护三个数组来实现。 以下边这张图为例，"CHINA"字符数组，使用优先队列进行排序。 其中：keys 保存的是原始字符数组； pq数组存储的是排序后keys中元素索引。（） qp数组是pq数组的“逆数组”，pq[i] =j qp[j]=i

可以看出pq数组是实际上的优先队列，存储排序后的元素索引。

为什么要引入qp数组呢？思考这样的情景，如果没有qp数组，我们需要查找“C”在优先队列中的位置，只有遍历pq数组，而有了qp数组，我们可以一步得到：“C"在keys中的索引为1，那么"C"在优先队列中的位置就是 **pq[ qp[1]] **

堆排序

我们可以用基于堆的优先队列变成一种排序方法：将所有的元素插入一个查找最小元素优先队列，然后再重复调用删除最小元素的操作来将它们按顺序删去。 堆排序算法分为两个阶段：

1. 堆构造阶段，原始数组重新组织安排进一个堆中
2. 下沉排序阶段，从堆中按顺序取出最小/最大元素，最终得到排序结果。

堆构造

我们第一时间能想到的堆构造的办法是从左往右遍历原数组，调用swim方法来实现堆构造。 一种更高效的办法是用sink函数，过程如下图所示：

下沉排序

第二阶段下沉排序就很简单了，过程和选择排序有些类似（按照降序而非升序取出所有元素），但所需的比较要少得多，因为堆提供了一种从未排序部分找到最大元素的有效方法。