插入排序-算法

动画

插入排序
最好情况： 比较n-1次，移动2(n-1)次
最差情况： 比较(n+2)(n-1)/2 ，移动(n+4)(n-1)/2
直接插入排序的时间复杂度为： $O(n^2)$
空间复杂度为：$T(n)$

直接插入排序

#include <iostream>
#include <cstdio>
using namespace std;
void insertion_sort(int arr[], int len)
{
    for (int i = 1; i < len; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while ((j >= 0) && (key < arr[j]))
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
int main(void)
{
    int arr[] = {5, 2, 4, 1, 0, 7};
    int len = sizeof(arr) / sizeof(int);
    insertion_sort(arr, len);
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
}

#include <iostream>
using namespace std;
void inser_sort(int arr[], int len)
{
    if(arr == NULL || len <=0)
    {
        return;
    }
    for(int i = 1;i<len;i++){
        int temp = arr[i];//存储下一位数字
        int j; //j代表前一位数字
        for(j = i - 1;j>=0;j--){
            if(arr[j] > temp){
                //如果前一位数字大于后一位数字，把前一位的数字往后移动一位
                arr[j+1] = arr[j];
            }
            else{
                break;
            }
        }
        arr[j+1] = temp;
    }
}
int main(void)
{
    int arr[] = {9,8,7,6,5,4,3,2,1};
    int len = sizeof(arr) / sizeof(int);
    inser_sort(arr,len);
    for(int i = 0;i < len;i++) {
        cout << arr[i] << " ";
    }
}

折半插入排序

将折半查找用于在有序集中确定插入位置，把这种排序方法叫做折半插入排序