C++实现插入排序算法

插入排序算法的基本思想是：将数列中的元素与已排序好的数据进行比较，从而找到合适的位置插入。根据其思想，我们可以很快的实现此算法。代码如下。

#include 
using namespace std;


int *create_rand_arr() {
    

    int length = 10;  // 定义长度为10
    srand(time(0));  // 设置时间种子

    int *rand_arr = new int [length];
    for (int i = 0; i < length; i++) {
        rand_arr[i] = rand() % (100 - -100 + 1) + -100;  // 将随机数填充进数组指针中
    }

    return rand_arr;
}


int get_length(int *arr) {
    
    return  _msize(arr) / sizeof(*arr);
}


void insert_sort(int *arr) {
    
    int temp, j, length = get_length(arr);

    for (int i = 0; i < length; i++) {
        temp = arr[i];  // 用于暂存数据
        j = i - 1;

        // 循环排序，保证数据到达合适的位置
        while (j >= 0 && temp > arr[j]) {
            arr[j + 1] = arr[j];  // 把所有的数据往后移一位
            j--;  // 下标减1
        }

        arr[j + 1] = temp;

        
    }
}


int main() {
    int *arr = create_rand_arr();  // 制作随机整数数组
    int length = get_length(arr);  // 获取长度

    // 输出原数组
    cout << "原数组： ";
    for (int i = 0; i < 10; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // 使用插入排序函数进行排序
    insert_sort(arr);

    // 输出新数组
    cout << "新数组： ";
    for (int i = 0; i < 10; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

运行结果如下。

此排序算法的复杂度和之前的选择排序算法和冒泡排序算法相同。平均时间复杂度为 O ( n 2 ) O(n^2) O(n2)，最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)，空间复杂度为 O ( 1 ) O(1) O(1)。