插入排序概述
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。
原理与步骤
原理
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序。
步骤
从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤2~5。
Java代码实现
以下是一个使用Java实现的插入排序算法的示例：
public class InsertionSort {
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;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j – 1;
}
arr[j + 1] = key;
}
}
// Utility function to print array of size n
public static void printArray(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String[] args) {
int[] arr = { 12, 11, 13, 5, 6 };
System.out.println("Original array");
printArray(arr);
insertionSort(arr);
System.out.println("\nSorted array");
printArray(arr);
}
}
实战案例分析
案例一：对整数数组进行排序
假设我们有一个整数数组
arr = { 12, 11, 13, 5, 6 }
，我们可以使用插入排序算法对其进行排序。
运行上述代码后，输出结果为：
Original array
12 11 13 5 6
Sorted array
5 6 11 12 13
案例二：对包含重复元素的数组进行排序
假设我们有一个整数数组
arr = { 3, 6, 2, 6, 5, 2, 3 }
，其中包含重复元素。
运行上述代码后，输出结果为：
Original array
3 6 2 6 5 2 3
Sorted array
2 2 3 3 5 6 6
总结
插入排序是一种简单直观的排序算法，适合对少量数据进行排序。在处理大量数据时，插入排序的性能较差，因为其时间复杂度为O(n^2)。但在某些特定情况下，插入排序仍然是一个不错的选择，例如当待排序数据基本有序时，插入排序的效率会显著提高。