排序算法之插入排序

插入排序是一种思想很简单的排序方法，它通过比较当前元素和其之前已经排好元素的大小，找到合适的位置插入，并把插入位置后的元素向后移动。

步骤

1. 从第一个元素开始，该元素可以认为已经排好序。
2. 取出下一个元素，在已经排好序的元素序列中从后往前扫描进行比较。
3. 如果该元素(已排序)大于新元素，则将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后面。
6. 重复步骤2~5。

代码实现：

package sortdemo;
public class InsertSort {
    public static void main(String[] args){
        int arr[]={6,5,3,1,8,7,2,4};
        System.out.println("排序之前：");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        insertSort(arr);
        System.out.println();
        System.out.println("排序之后:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    
    public static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            if (arr[i-1]>arr[i]){
                int temp = arr[i];
                int j = i;
                while (j>0 && arr[j-1]>temp){
                    arr[j]=arr[j-1]; //将比temp大的元素往后移
                    j--;
                }
                arr[j]=temp; //将temp值插入
            }
        }
    }
}

复杂度

时间复杂度

1. 最好的情况就是已经排好序的数组，这样一次都不用交换。
2. 最坏的情况就是完全是逆序的数组，这样每个元素都要挪动，每次都要交换，次数为1+2+3+...+n-1=n(n-1)/2，时间复杂度为O(n^2)。
3. 平均复杂度为O(n^2)，是一种稳定的排序方法。

空间复杂度

插入排序和冒泡排序一样是时间换空间的排序方法，没有使用多余的数据结构，不用分配额外的空间，所以空间复杂度为O(1)。