直接插入排序：

算法思想：基本思想就是，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

注意点：插入排序所需的时间取决于输入元素的初始顺序

时间复杂度：O(n²)

代码实现：

//通过交换进行插入排序
public static void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
}

// 通过将较大的元素都向右移动而不总是交换两个元素
public static void sort2(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int num = a[i];
        int j;
        for (j = i; j > 0 && num < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = num;
    }
}

希尔排序:

算法思想：希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

注意点：步长的选择是希尔排序的重要部分，即：只要最终步长为1任何步长序列都可以工作，一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。

时间复杂度：O(nlog2 n)

代码实现：

//该算法中步长的选择：h/3
public static void sort(int[] a) {
    int length = a.length;
    int h = 1;
    while (h < length / 3) h = 3 * h + 1;
    for (; h >= 1; h /= 3) {
        for (int i = 0; i < a.length - h; i += h) {
            for (int j = i + h; j > 0; j -= h) {
                if (a[j] < a[j - h]) {
                    int temp = a[j];
                    a[j] = a[j - h];
                    a[j - h] = temp;
                }
            }
        }
    }
}

简单选择排序:

算法思想：选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n个元素的表进行排序总共进行至多 n-1 次交换。

注意点：如果某个元素位于正确的最终位置上，则它不会被移动。

时间复杂度：O(n²)

代码实现：

public static void sort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int min = i;
        //找到最小的位置
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        //进行交换
        if (min != i) {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

堆排序：

基本思想：堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

注意点：一是建立堆，二是堆顶与堆的最后一个元素交换位置，这两点值得注意。

时间复杂度：O(nlog2n)

代码实现：

public static void sort(int[] a) {

    for (int i = a.length - 1; i > 0; i--) {
        max_heapify(a, i);
        //堆顶元素(第一个元素)与Kn进行交换
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
    }
}


/***
 *  将数组堆化
 *  i = 第一个非叶子节点
 *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始
 *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大
 */
public static void max_heapify(int[] a, int n) {
    int child;
    for (int i = (n - 1) / 2; i >= 0; i--) {
        //在左子节点位置
        child = 2 * i + 1;
        //在右子节点存在且大于左子节点，child变成右子节点
        if (child != n && a[child] < a[child + 1]) {
            child++;
        }
        //进行交换父节点与左右子节点中的最大值
        if (a[i] < a[child]) {
            int temp = a[i];
            a[i] = a[child];
            a[child] = temp;
        }
    }
}

本文介绍了四种排序算法，值得注意的是是，每一个算法中进行分析的时间复杂度都是基于平均时间复杂度的，另外对于空间复杂度没有进行分析的原因是，分析空间复杂度时会依赖于计算机的硬件性能，不能一概而论，所以，在此文中不进行空间复杂度的分析。最后，下个博客将会发表其余常见的排序算法。