java插入排序算法（java排序实现）

# Java插入排序算法

## 简介

插入排序是一种简单且有效的排序算法，它的基本思想是每次将一个待排序元素插入到已经排好序的部分中的适当位置，直到所有元素都排好序为止。该算法的时间复杂度为O(n^2)，适用于小规模数据或基本有序数据的排序。

## 算法步骤

1. 从第一个元素开始，该元素可以认为已经被排序。

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。

4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。

5. 将新元素插入到该位置。

6. 重复步骤2~5，直到所有元素都排好序。

## Java代码实现

```java

public class InsertionSort {

public 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;

}

}

public static void main(String[] args) {

int[] arr = {12, 11, 13, 5, 6};

InsertionSort ob = new InsertionSort();

ob.insertionSort(arr);

System.out.println("Sorted array:");

for (int i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

}

```

## 示例运行结果

输入：{12, 11, 13, 5, 6}

输出：{5, 6, 11, 12, 13}

通过以上代码和步骤的解释，我们可以实现Java插入排序算法，并对输入的数组进行排序，得到按升序排列的结果。这种简单但有效的排序算法在实际应用中仍然有一定的价值，特别是对于小规模数据或基本有序数据的排序。