算法-各种排序

概览：选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序。稳定性分析。

排序算法

排序成本模型：
需要计算比较和交换的数量。对于不交换的算法计算访问数组的次数。

额外的内存使用：
排序算法可分为两类：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存来存储另一份数组副本的其他排序算法。

选择排序

找到数组中最小的元素，将它和数组中第一个元素交换位置。然后在剩下的元素中找到最小元素，与第二个元素交换，如此往复。

public void chooseSort(int[] a) {
  for (int i = 0; i < a.length; i++) {
    int minIndex = i;
    for (int j = i; j < a.length; j++) {
      if (a[j] < a[minIndex]) {
        minIndex = j;
      }
    }
    int temp = a[minIndex];
    a[minIndex] = a[i];
    a[i] = temp;
  }
}

特点：

1. 运行时间和输入无关。
2. 数据移动是最少的。

插入排序

当前索引前所有元素有序，从索引后取数，插入到前面有序队列中。

对于部分有序的数组，插入排序很有效，选择排序则不然。当倒置的数量很少时，插入排序很可能比任何算法都要快。
对于随机排序的数组，插入排序和选择排序的运行时间是平方级别。

希尔排序

希尔排序是基于插入排序的快速的排序算法。
对于大规模数组插入排序很慢，因为只会交换相邻的元素。希尔排序改进了这点，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

归并排序

要将一个数组排序，可以先将它分为两半分别排序，然后将结果归并起来，递归操作。

没有任何基于比较的算法能够保证使用少于 lg(N!) ~ NlgN 次比较将长度为N的数组排序。
归并排序是一种渐进最优的基于比较排序的算法。

局限性：

1. 归并排序的空间复杂度不是最优的。
2. 实践中不一定会遇到最坏的情况。
3. 除了比较，算法的其他操作也可能重要
4. 不进行比较也能将某些数据排序。

快速排序

快速排序是一种分治的排序算法。将一个数组分成两个子数组，将两部分独立地排序。
特点：原地排序，线性对数增长级别 NlogN. 内循环短小，理论上实际上快。
缺点：非常脆弱，要非常小心避免低劣性能。在切分不平衡时这个程序可能极为低效。

优势：内循环短小，比较次数很少。

优先队列 堆排序

需求：为元素分配优先级，获取最大最小的的元素。
堆的定义：当一颗二叉树每个节点都大于等于它的两个子节点时，被称为有序堆。二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储。

位置k的节点的父节点位置为： k/2 , 而她的两个子节点的位置分别为2k 和 2k+1。
一颗大小为N的完全二叉树的高度为 lgN 。

稳定性

如果一个排序算法能够保留数组中重复元素的相对位置则可称为稳定。
稳定的算法：插入排序和归并排序
不稳定的：选择排序，希尔排序，快速排序和堆排序

快速排序是最快的通用排序算法。

1. 内循环指令少，还能利用缓存。
2. 使用三向切分后，快速排序对于实际应用中俄能出现的分布式输入编程线性。