Please enable Javascript to view the contents

排序算法之插入排序

 ·  ☕ 2 分钟

对欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。

n个待排序的元素看成为一个有序表和一个无序表。

开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

一、排序步骤

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

二、动画演示

insert_sort

三、代码实现

 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
30
31
32
33
34
35
36
37
38
package com.whoismy8023.learning.sort;

import java.util.Arrays;

/**
 * Created by SPPan on 2019/9/6.
 * <p>
 * 直接插入排序
 */
public class InsertSortLearning {

    public static void main(String[] args) {
        int[] arr = {1, -1, 2, -2, 3, 6, 5, 4};
        System.out.printf("排序前:%s \n", Arrays.toString(arr));
        insertSort(arr);
        System.out.printf("排序后:%s \n", Arrays.toString(arr));
    }

    private static void insertSort(int[] arr) {
        int insertIndex;
        int currVal;
        for (int i = 1; i < arr.length; i++) {
            currVal = arr[i];
            insertIndex = i - 1;

            while (insertIndex >= 0 && currVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = currVal;
            }
            System.out.printf("第%d轮后的结果:%s \n", i, Arrays.toString(arr));
        }
    }
}

四、代码演示结果

1
2
3
4
5
6
7
8
9
排序前:[1, -1, 2, -2, 3, 6, 5, 4] 
第1轮后的结果:[-1, 1, 2, -2, 3, 6, 5, 4] 
第2轮后的结果:[-1, 1, 2, -2, 3, 6, 5, 4] 
第3轮后的结果:[-2, -1, 1, 2, 3, 6, 5, 4] 
第4轮后的结果:[-2, -1, 1, 2, 3, 6, 5, 4] 
第5轮后的结果:[-2, -1, 1, 2, 3, 6, 5, 4] 
第6轮后的结果:[-2, -1, 1, 2, 3, 5, 6, 4] 
第7轮后的结果:[-2, -1, 1, 2, 3, 4, 5, 6] 
排序后:[-2, -1, 1, 2, 3, 4, 5, 6] 
目录