Posts 插入排序
Post
Cancel

插入排序

原理

  1. 首先将第一个元素视为已排序的序列。
  2. 取未排序序列中的一个元素,在已排序的序列中从后向前查找,直到找到比当前元素小(大)的位置,然后插入进去。
  3. 重复第 2 步,直到整个序列有序。

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class InsertionSort {
    public static void sort(int[] arr, BiPredicate<Integer, Integer> cmp) {
        for (int i = 1; i < arr.length; i++) {
            if (cmp.test(arr[i], arr[i - 1])) {
                int t = arr[i];
                for (int j = i; j >= 0; j--) {
                    if (j > 0 && cmp.test(t, arr[j - 1])) {
                        // 将所有比当前元素大(小)的元素向后移动
                        arr[j] = arr[j - 1];
                    } else {
                        // 插入
                        arr[j] = t;
                        break;
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 3, 6, 4, 9, 8, 7, 10};
        sort(arr, (a, b) -> a < b);
    }
}

算法复杂度

时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性
O(N2)O(N2)O(N)O(1)稳定
OLDER POST NEWER POST

Comments powered by Disqus.

内容

Search Results