名字：区间插入排序 对插入的优化

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 100; 
  
void printSortedArrays(int sortedArrays[][MAX_SIZE], int size) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < MAX_SIZE; ++j) {
            if (sortedArrays[i][j] == 0) {
                break;
            }
            cout << sortedArrays[i][j] << " ";
        }
    }
    cout << endl;
}

void insertIntoSortedArrays(int sortedArrays[][MAX_SIZE], int& size, int num) {
    if (size == 0) {
        sortedArrays[0][0] = num;
        size++;
        return;
    }

    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (num < sortedArrays[mid][0]) {
            right = mid - 1;
        } else if (num > sortedArrays[mid][MAX_SIZE - 1]) {
            left = mid + 1;
        } else {
            for (int i = 0; i < MAX_SIZE; ++i) {
                if (sortedArrays[mid][i] == 0 || sortedArrays[mid][i] > num) {
                    for (int j = MAX_SIZE - 1; j > i; --j) {
                        sortedArrays[mid][j] = sortedArrays[mid][j - 1];
                    }
                    sortedArrays[mid][i] = num;
                    return;
                }
            }
        }
    }

    for (int i = size; i > left; --i) {
        for (int j = 0; j < MAX_SIZE; ++j) {
            sortedArrays[i][j] = sortedArrays[i - 1][j];
        }
    }
    sortedArrays[left][0] = num;
    size++;
}

void mergeSortedArrays(int sortedArrays[][MAX_SIZE], int size, int result[], int& resultSize) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < MAX_SIZE; ++j) {
            if (sortedArrays[i][j] == 0) {
                break;
            }
            result[resultSize++] = sortedArrays[i][j];
        }
    }
    sort(result, result + resultSize);
}

void intervalInsertionSort() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    int nums[MAX_SIZE];
    cout << "Enter the elements: ";
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int sortedArrays[MAX_SIZE][MAX_SIZE] = {0};
    int size = 0;
    for (int i = 0; i < n; ++i) {
        insertIntoSortedArrays(sortedArrays, size, nums[i]);
    }

    int result[MAX_SIZE * MAX_SIZE];
    int resultSize = 0;
    mergeSortedArrays(sortedArrays, size, result, resultSize);

    cout << "Sorted array: ";
    for (int i = 0; i < resultSize; ++i) {
        cout << result[i] << " ";
    }
    cout << endl;
}

int main() {
    intervalInsertionSort();
    return 0;
}