Java-数据结构和算法-插入排序(insertion sort)

相关文章

接下来我们看看插头排序

插入排序

我打牌一般不输，我有一个跟输赢无关的习惯。就是牌会按大小顺序排列。从摸牌，再到排序这么一个过程，其实就是插入排序。

算法描述

插入排序分为两组数据，已经排序的数据，等待排序的数据 从等待排序的数据，向已经排序的数据中对比插入

代码实现

我这里偷懒，用了一下集合

public class Main {
    public static void main(String[] args) {
        int[] data = new int[]{344, 4, 345, 23, 566, 456, 34, 5, 78, 45, 23, 56673};
        //我们使用集合比较方便插入，当然啦，集合直接就有工具类去排序了。
        List<Integer> sortedData = new ArrayList<>();
        for (int i = 0; i < data.length; i++) {
            int current = data[i];
            insert(sortedData, current);
            output(sortedData);
        }
        output(sortedData);
    }

    private static void insert(List<Integer> sortedData, int current) {
        //如果size为0，直接插入，不需要进行比较
        if (sortedData.size() == 0) {
            sortedData.add(current);
        } else if (sortedData.size() == 1) {
            if (current > sortedData.get(0)) {
                sortedData.add(current);
            } else {
                sortedData.add(0, current);
            }
        } else {
            for (int i = 0; i < sortedData.size(); i++) {
                if (current < sortedData.get(i)) {
                    sortedData.add(i, current);
                    break;
                }
                if (i == sortedData.size() - 1) {
                    //
                    sortedData.add(current);
                    break;
                }
            }
        }
    }

    private static void output(List<Integer> data) {
        System.out.print("[");
        for (Integer datum : data) {
            System.out.print(" " + datum + " ");
        }
        System.out.println("]");
    }
}

那用数组怎么写呢？

public class MainTwo {
    public static void main(String[] args) {
        int[] data = new int[]{344, 4, 345, 23, 566, 456, 34, 5, 78, 45, 23, 56673};
        //默认值全为0
        int[] sortData = new int[data.length];
        for (int i = 0; i < data.length; i++) {
            //取数据
            int current = data[i];
            output(sortData);
            //插入到数组里
            insert(sortData, current, i);
            output(sortData);
        }
    }

    private static void insert(int[] sortData, int current, int index) {
        //index表示已经插入了多少个嘛
        if (index == 0) {
            sortData[0] = current;
        } else {
            //比大小
            for (int i = 0; i < index; i++) {
                if (current < sortData[i]) {
                    int tmp = sortData[i];
                    sortData[i] = current;
                    //就在i这个地方了
                    for (int j = i + 1; j <= index; j++) {
                        int next = sortData[j];
                        sortData[j] = tmp;
                        tmp = next;
                    }
                    break;
                }
                if (i == index - 1) {
                    //放到最后面去了
                    sortData[index] = current;
                }
            }
        }
    }

    private static void output(int[] data) {
        System.out.print("[");
        for (int datum : data) {
            System.out.print(datum + " ");
        }
        System.out.println("]");

    }
}

单数组实现

public class InsertionSort {

    public static void main(String[] args) {
        int[] data = new int[]{344, 4, 345, 23, 566, 456, 34, 5, 78, 45, 23, 56673};
        //从第二个开始遍历每一个元素
        for (int i = 1; i < data.length; i++) {
            //拿到要排序的元素
            int target = data[i];
            //所有的元素往后移动，直到target找到合适的位置
            int j = i - 1;//j表示已经排序的数量
            while (j >= 0 && target < data[j]) {
                //数据往右移动
                //data[j+1]第一个就是data[i]
                data[j + 1] = data[j];
                j--;
            }
            data[j + 1] = target;
        }
    }
}

排序结果

集合写的排序结果

用数据写的结果：