#include <stdio.h>

void insertionSort(int arr[], int length) {
    // 从第二个元素开始，假设第一个元素是已排序的
    for (int i = 1; i < length; i++) {
        // 取出当前元素
        int currentElement = arr[i];
        int j = i - 1;
        // 向左移动已排序部分的元素，直到找到当前元素应插入的位置
        while (j >= 0 && arr[j] > currentElement) {
            arr[j + 1] = arr[j]; // 右移元素
            j--;
        }
        // 将当前元素插入到找到的位置
        arr[j + 1] = currentElement;
    }
}

// 测试插入排序
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int length = sizeof(arr) / sizeof(arr[0]);  // 获取数组长度
    
    printf("排序前：");
    for (int i = 0; i < length; i++) {  // 使用传统的for循环
        printf("%d ", arr[i]);
    }

    insertionSort(arr, length);  // 传递数组和长度

    printf("\n排序后：");
    for (int i = 0; i < length; i++) {  // 使用传统的for循环
        printf("%d ", arr[i]);
    }

    return 0;
}
