9 种常用排序算法总结

一、插入排序

基本思想：每一趟将一个待排序的记录，按其关键字的大小插入到已经排序好的一组记录的适当位置上，直到全部待排序记录全部插入为止。

1.1 直接插入排序

排序过程：

• 将待排序数组 arr[1...n] 看作两个集合，arr[1] 为有序集合中元素，arr[2...n] 为无序集合中元素，a[0] 用来临时存放当前待排序记录
• 外层循环每次从无序集合中选择一个待插入元素（n-1 次），每次使用顺序查找法，内层循环查找 arr[i] 在有序集合中的位置（将有序集合中大于待插入元素的记录后移一位）

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 从第二个元素开始（第一个元素默认已排序）
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将比 key 大的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 插入 key 到正确位置
            arr[j + 1] = key;
        }
    }
}

时间复杂度：

• 最好情况下（待排序记录递增有序），总的比较次数为 n-1 次，记录不需要移动。
• 最坏情况下（待排序记录递减有序），总的比较次数和移动次数均为 n^2/2。
• 平均情况下，比较次数和移动次数都是 n^2/4。

空间复杂度：

只需要一个辅助空间 arr[0],因此空间复杂度为 O(1)

1.2 折半插入排序

基本思想同直接查找插入排序，不同点在于，在有序集合中搜索插入位置时折半插入采用二分搜索，可以有效的减少比较次数。