数据结构排序算法之插入排序详解（java实现）

悠悠 2022-06-01 23:43 152阅读 0赞

### 前言 ###

相信学过数据结构的人都知道这个插入排序算法，不多说，今天就总结一下这个算法。
    
    注意：测试环境为java8

### 知识点一：插入排序思想 ###

插入排序：将一个记录插入到一个已经排好序的列表中，使得新列表仍然有序。
    
     可能你看到这个会有点晕，没关系听我慢慢解释一下：
            1,首先假设我们的列表项的第一个项是有序的
            2，我们从列表的第二项开始遍历，在循环中遍历当前项以前有序列表，找到当前项插入的位置
            3,移动有序列表的位置，空出插入位置
            4，在插入位置插入当前项

### 知识点二：插入排序分类 ###

1，直接插入排序：逐个遍历查找
    2，折半插入排序：查找插入位置阶段使用二分查找实现

### 知识点三：时间复杂度、稳定性、辅助空间 ###

时间复杂度：O(n^2)
    稳定性：稳定排序
    辅助空间：O(1)

### 知识点四：java实现 ###

#### 1.java实现直接排序（默认升序） ####

/** * 直接选择排序实现 （默认升序） */
        private void selectionSort(int[] ints) {
            Objects.requireNonNull(ints);
            for (int i = 1; i < ints.length; i++) {
                int temp = ints[i];
                //后面一项小于前面一下需要排序
                if (temp < ints[i - 1]) {
                    int j;
                    for (j = i - 1; j >= 0; j--) {
                        if (ints[j] > temp) {
                            //移动位置
                            ints[j + 1] = ints[j];
                        } else {
                            break;
                        }
                    }
                    ints[j + 1] = temp;
                }
            }
        }

测试类：

@Test
        public void test() {
            int[] ints = { 1,52, 16,78, 1, 1};
            selectionSort(ints);
            Arrays.stream(ints).forEach(System.out::println);
        }

结果：

1
    1
    1
    16
    52
    78

#### 2.java实现折半插入排序 ####

/** * 折半选择排序,升序 */
        private void halfSelectionSort(int[] ints) {
            Objects.requireNonNull(ints);
            for (int i = 1; i < ints.length; i++) {
                int temp = ints[i];
                if (temp < ints[i - 1]) {
                    //遍历查找i元素插入的位置
                    int low = 0, high = i - 1, mid = (low + high) / 2;
                    while (low <= high) {
                        if (ints[mid] > temp) {
                            high = mid - 1;
                        } else {
                            low = mid + 1;
                        }
                        mid = (low + high) / 2;
                    }
    
                    //移动插入位置之前的元素
                    for (int j = i; j > low; j--) {
                        ints[j] = ints[j - 1];
                    }
                    //插入当前元素
                    System.out.println("当前元素ints[i] = " + temp + "插入到了" + low + "位置");
                    ints[low] = temp;
                }
            }
        }

测试代码：

@Test
        public void test() {
            int[] ints = { 1,52, 16,78, 1, 1};
            //selectionSort(ints);
            halfSelectionSort(ints);
            //halfSelectionSortDesc(ints);
            Arrays.stream(ints).forEach(System.out::println);
        }

测试结果：

当前元素ints[i] = 16插入到了1位置 当前元素ints[i] = 1插入到了1位置 当前元素ints[i] = 1插入到了2位置 1 1 1 16 52 78

#### 3.java实现折半查找倒序 ####

/** *折半选择排序,降序 * */
        private void halfSelectionSortDesc(int[] ints) {
            Objects.requireNonNull(ints);
            for (int i = 1; i < ints.length; i++) {
                int temp = ints[i];
                if (temp > ints[i - 1]) {
                    //遍历查找i元素插入的位置
                    int low = 0, high = i - 1, mid = (low + high) / 2;
                    while (low <= high) {
                        if (ints[mid] >= temp) {
                            low = mid + 1;
                        } else {
                            high = mid - 1;
                        }
                        mid = (low + high) / 2;
                    }
    
                    //移动插入位置之前的元素
                    for (int j = i; j > low; j--) {
                        ints[j] = ints[j - 1];
                    }
                    //插入当前元素
                    System.out.println("当前元素ints[i] = " + temp + "插入到了" + low + "位置");
                    ints[low] = temp;
                }
            }
        }

测试代码：

@Test
        public void test() {
            int[] ints = { 1,52, 16,78, 1, 1};
    
            halfSelectionSortDesc(ints);
            Arrays.stream(ints).forEach(System.out::println);
        }

测试结果：

当前元素ints[i] = 52插入到了0位置 当前元素ints[i] = 16插入到了1位置 当前元素ints[i] = 78插入到了0位置 78 52 16 1 1 1

### 总结： ###

插入排序算是常用排序中简单的一个了，好好理解一下还是可以弄明白的。其核心的特点就是假设数据集合中的第一个元素已经是有序的了，
    从第二个元素开始遍历插入到前面的有序列表中，使得插入后的有序列表仍然有序。