名词解释

排序算法的稳定性

['AI','Java','ML','NLP','CPP']

对上面的数组中字符串按照长度进行排序，如果排序后相同长度的字符串的相对位置不变（即排序后 "AI" 依然排在 "ML" 的前面），则称排序算法是稳定的。

选择排序

找到最小的元素和第一位交换，从第二位开始在最小的元素和第二位交换，如此往复。

特点：

• 运行时间和输入无关
• 数据移动最少

public static void sort(Comparable[] a) {
    int len = a.length;
    for (int i = 0; i < len; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++) {
            if (a[j].compareTo(a[min]) < 0) {
                min = j;
            }
        }
        Utils.swap(a, i, min);
    }
}

插入排序

不断和前一个元素比较，如果前一个元素大于当前元素，则交换。就像整理扑克牌一样，第一张牌不动，第二张则插在第一张的左或右边，而第三张则插入在前两张的合适位置。

特点：

• 插入排序对下列数组排序效果很好 ：
  • 数组中只有几个元素的位置不正确
  • 每个元素都离自己正确的位置不远
• 当倒置数很少的时候，性能很好

希尔排序

对于大数组，插入排序工作的并不好，因为它只会交换相邻元素，元素只能一点一点地搬动到另一端。而希尔排序，通过调整跨度，可以将大数组快速地调整为局部有序的数组，而后再采用插入排序完成最终排序。

归并排序

归并排序的思路是将问题两个有序数组的合并，合并两个有序数组是线性复杂度的。

自顶向下的归并排序

自顶向下的归并排序采用递归的写法，可以想象不断将数组划分为原来的一半，递归到最深层有两个元素进行比较，这时候就相当于是两个有序数组了，可将他们归并为一个有序数组。而后递归退回一层将两个有序数组在归并。这样整个数组就进行排序。

merge 算法，需要一个额外的空间来保存两个 a 数组中的内容。

自顶向下的归并排序需要递归，其本质是将两个有序子数组合并为一个有序数组。为了得到有序子数组，纯粹的递归归并，是通过递归深入到最底层，进行两个元素的比较。这才得到了一个有两个元素的有序子数组，而后有四个元素的有序子数组……。

这样递归深度是 log2(N) 层，为了减少递归深度，可以在子数组长度较少时可以使用插入排序得到有序的子数组。这样可以减少递归的深度。

自底向上的归并排序

模仿递归的归并排序的效果，可采用迭代完成相同的效果。第一次迭代以 2 为跨度，将两个元素调整为有序，而后以 4 为跨度，将其中的两个有 2 个元素的有序数组合并，而后以 8 为跨度。

堆排序

堆排序是利用二叉堆的特性，首先用待排序数组构成二叉堆，而后不断将堆中最大元素放到数组的后面，同时减小堆的大小，当堆为空时，排序完成。

堆排序的主要缺点是它不能有效地利用缓存，堆排序中的比较很少在相邻元素间进行，在对大数组排序的时候，缓存往往不会命中。这是为什么看起来堆排序具有和快速排序相同时间复杂度为 O(NlogN)，但却没有得到广泛使用的原因。