插入排序（Insertion Sort）是一種簡單直觀的排序算法，其基本思想是將一個記錄插入到已經排好序的有序表中，從而形成一個新的、記錄數增1的有序表。插入排序的工作方式類似於人們排序一手撲克牌，開始時，左手為空且桌子上的牌面向下，然後每次從桌子上拿走一張牌並將其插入左手中正確的位置，為了找到一張牌的正確位置，需要從右到左將它與已在手中的每張牌進行比較。
插入排序的具體過程如下：
將待排序的元素分為已排序和未排序兩個部分。
每次從未排序部分取出一個元素。
將該元素與已排序部分的元素逐個比較，找到合適的位置插入。
重複上述過程，直到所有元素都排序完成。
插入排序的時間複雜度在最壞情況下為O(n^2)，其中n是待排序序列的長度。這是因為在一個逆序序列的情況下，每個元素的插入都需要與所有已排序的元素進行比較。儘管如此，插入排序對於小規模的數據或部分有序的數據序列仍然是一個有效的算法。