# 03 经典排序算法

重温排序算法，动画详见：[Magicsort](https://chanshiyu.com/treasure/magicsort/)

## 插入排序

插入排序是一种简单的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序算法的运作如下：

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

插入排序平均时间复杂度 O(n^2)，在最好情况下复杂度为 O(n)，在最坏情况下复杂度为 O(n^2)。

### 经典插入算法

经典插入算法：将数列分为有序区和无序区两部分，在每轮循环中从无序区选择一个最小值并入有序区，新增一位有序区同时减少一位无序区，n - 1 轮排序后全部变为有序区，从而完成排序。

```java
public class InsertSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
        insertSort(array);
        for (int value : array) {
            System.out.print(value + " ");
        }
    }

    /**
     * 插入排序
     *
     * @param array 待排序数组
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 待插入的元素
            int needInsert = array[i];
            // 开始比较的索引
            int index = i - 1;
            while (index >= 0 && array[index] > needInsert) {
                // 将该位置的元素进行后移
                array[index + 1] = array[index];
                // 再比较该位置前一个元素
                index--;
            }
            // 当前位置满足条件
            array[index + 1] = needInsert;
        }
    }

}
```

### 二分插入算法

二分插入算法：查找插入位置时使用二分查找的方式，在插入值之前，先在有序区中找到待插入值需要比较的左边界，在数据长度较大时，可以有效减少每轮排序中的查找插入位置的次数。

```java
public class InsertSort {

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 待插入的元素
            int needInsert = array[i];
            // 左右边界
            int left = 0;
            int right = i - 1;

            // 找到待插入数据的合适位置
            while (left <= right) {
                int middle = (left + right) / 2;
                if (needInsert < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }

            // 将右边比待插入数据大的数都右移一位
            for (int j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            // 当前位置满足条件
            array[left] = needInsert;
        }
    }

}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chanshiyu.gitbook.io/blog/hou-duan/li-lun-gai-nian/03-jing-dian-pai-xu-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.