排序算法引言

排序算法是最常见的算法之一，常见的排序算法有冒泡排序、插入排序、选择排序、希尔排序、归并排序、堆排序、快速排序。其目的是为了实现>对数组中元素的排序。通常排序分为正序和倒序。

时间复杂度

• 最好、最坏、平均时间复杂度
• 时间复杂度计算公式
• 比较次数和交换次数

空间复杂度

• 空间复杂度，衡量空间上的内存消耗
• 原地排序，代指空间复杂度为O(1)的排序

排序算法的稳定性

• 稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序,反之不稳定的排序算法经常会改变这个次序。以某两个相等元素c[i]和c[j]为例，假如在原始待排序数组中c[i] == c[j]，并且c[i]位置在c[j]之前。那么如果整个排序过程中，c[i]均在c[j]之前，则说明排序算法是稳定的，反之则是不稳定的。

[3][4][9] .... [i] ... [j] ...

公共函数

/*比较两个元素大小*/
private static boolean less(Comparable v, Comparable w){
    return v.compareTo(w) < 0;
}

/*交换两个元素*/
private static void exch(Comparable[] a, int i, int j){
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
}