0%

插入排序

发表于 更新于 分类于

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

基本思想

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，动态图如下(来源：https://www.cnblogs.com/onepixel/articles/7674659.html)：

stopthread2.jpg

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author gelong
 * @date 2020/6/4 22:55
 */
public class InsertionSort {

    private InsertionSort() {}

    private static <T> void sort(T[] data, Comparator<T> comparator) {
        for (int i = 1; i < data.length; i++) {
            int j;
            T temp = data[i];
            for (j = i; j > 0 && comparator.compare(data[j - 1], temp) > 0; j--) {
                data[j] = data[j - 1];
            }
            data[j] = temp;
        }
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }
}