插入排序

插入排序的时间复杂度是N^2。

插入排序有N-1趟排序组成，对于i=1到N-1趟，插入排序保证从位置0到位置i的元素处于排好的状态。

从位置j开始与前一个比较，符合条件的就交换，一直到不符合条件。

加个例子：

原始数组是34,8,64,51,32,21

一趟：8,34,64,51,32,21

二趟：8,34,64,51,32,21

三趟：8,34,51,64,32,21

四趟：8,32,34,51,64,21

五趟：8,21,32,34,51,64

import java.util.Scanner;

//插入排序：n^2
public class InsertionSort {
  private static Scanner scanner = new Scanner(System.in);

  public static void main(String[] args) {
    // 输入数组个数，然后输入数组
    int n = scanner.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = scanner.nextInt();
    }
    // 下面进行插入排序
    for (int i = 1; i < arr.length; i++) {
      int temp = arr[i];
      int j = 0;
      // 从大到小：temp > arr[j-1]
      // 从小到大：temp < arr[j-1]
      for (j = i; j > 0 && temp > arr[j - 1]; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = temp;
    }
    // 打印结果
    for (int i : arr) {
      System.out.print(i + " ");
    }
    System.out.println();
  }
}

也可以这样，道理是一样的

//插入排序
  public static void insertionSort(int arr[]){
    for (int i = 1; i < arr.length; i++) {
      for(int j = i;j>0&&arr[j]<arr[j-1];j--){
        swap(arr,j,j-1);
      }
    }
  }