插入排序

插入排序也是一种排序算法，时间复杂度同样为 O(n²)，但比冒泡排序稍微优化了一些。

在这个算法中，数组分成两部分。一部分是已排序的，另一部分是未排序的。我们从未排序的数组中取出一个元素，并将它放入已排序的数组中的正确位置。

重复这个过程，直到所有元素都排好序。

1. 假设我们有一个数组 {8,4,1,5}。把第一个元素视为已排序，其余元素视为未排序。开始时，第 0 个元素被视为已排序。

2. 创建一个临时变量，并将第 (i) 个元素（这里是 4）放入其中。将 temp 与当前已排序的数组（此时只有 8）进行比较。由于 4<8, 将已排序的数组向右移动，直到 4 到达正确的位置。在这种情况下，8 需要移动一次。现在，已排序数组的长度变为 2。

3. 重复这个过程，直到整个数组都排好序。

for(int i=1;i<n;i++){           //从第一个元素开始，因为我们认为第 0 个元素已经排好序。
    int temp=arr[i];
    
    int j=i-1;                  //检查它左侧的所有元素。 
    
    while(arr[j]>temp && j>=0){ //只要左侧元素大于 temp，就将其右移，直到第一个元素。
      arr[j+1]=arr[j];          //将元素向右移动一位。
      j--;                      
    }
    
    arr[j+1]=temp;              //将 temp 放到正确的位置。
  
}

插入排序可视化

插入排序可视化工具