排序算法图解之Java插入排序

首先要了解什么是插入排序，插入排序是排序算法中简单直观的一种，其原理是将未排序的元素一个一个插入到已经排好序的元素中，最终得到一个有序的序列。那么下面我将用Java代码来演示插入排序的实现过程，并且提供详细的注释帮助读者理解。

算法步骤

1. 从第一个元素开始，认为第一个元素是已经排好序的，取第二个元素和已排序的元素进行比较，如果第二个元素比已排序的元素小，则交换两个元素，否则将第二个元素插入到已排序的元素中，此时第二个元素成为已排序的元素。
2. 然后取第三个元素，重复上述操作，将第三个元素插入到已排序的元素中。
3. 以此类推，直到所有元素都被排序。

Java实现

public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 3, 8, 6, 4};
        insertionSort(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            // 将元素插入到已排序的元素中
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

在代码中，我们定义了一个函数insertionSort来实现插入排序。在该函数中，我们首先获取数组的长度，然后从第二个元素开始遍历数组。对于每一个未排序的元素，我们都将其插入到已排序的元素中。具体实现是，将未排序的元素保存在一个变量key中，然后从该元素的前一个元素开始向前遍历已排序的元素，如果已排序的元素大于key，则将元素向后移动一位，直到找到key的正确位置为止。然后将key插入到该位置中。最终实现了数组的排序。

示例说明

示例一：假设我们需要将[5,3,8,6,4]进行升序排序

1. 首先，将第二个元素3和第一个元素5进行比较，3比5小，因此将3插入已排序的元素5中，此时数组为[3,5,8,6,4]。

2. 接着，将第三个元素8和已排序的元素[3,5]进行比较，8比5大，因此8不需要移动，此时数组为[3,5,8,6,4]。

3. 然后，将第四个元素6和已排序的元素[3,5,8]进行比较，6比8小，在8和5中间插入6，此时数组为[3,5,6,8,4]。

4. 最后，将第五个元素4和已排序的元素[3,5,6,8]进行比较，4比8小，在8和6之间插入4，此时数组为[3,5,4,6,8]。

5. 经过4轮比较插入排序后，最终数组为[3,4,5,6,8]，完成了排序。

示例二：假设我们需要将[1,2,3,4,5]进行升序排序

1. 首先，将第二个元素2和第一个元素1进行比较，2比1大，因此2不需要移动，此时数组为[1,2,3,4,5]。

2. 接着，将第三个元素3和已排序的元素[1,2]进行比较，3比2大，因此3不需要移动，此时数组为[1,2,3,4,5]。

3. 然后，将第四个元素4和已排序的元素[1,2,3]进行比较，4比3大，因此4不需要移动，此时数组为[1,2,3,4,5]。

4. 最后，将第五个元素5和已排序的元素[1,2,3,4]进行比较，5比4大，因此5不需要移动，此时数组为[1,2,3,4,5]。

5. 最终排序结果为[1,2,3,4,5]，数组不需要移动，已经是有序的了。