数据结构直接插入排序代码

直接插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是使用Python实现的直接插入排序代码：

def insertion_sort(arr):
    # 假设数组长度大于1
    for i in range(1, len(arr)):
        key = arr[i]  # 当前元素
        j = i - 1  # 指向已排序部分的最后一个元素

        # 从后向前比较，如果当前元素小于前一个，就移动前一个元素到后一位
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]  # 移动已排序部分的元素
            j -= 1

        # 将当前元素插入其最终位置
        arr[j + 1] = key

# 示例
unsorted_array = [9, 7, 5, 11, 12, 2]
insertion_sort(unsorted_array)
print("排序后的数组：", unsorted_array)

相关问题

数据结构直接插入排序代码c++

以下是C++实现的直接插入排序代码：

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] =;
    }
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

pta数据结构直接插入排序

### PTA 数据结构 直接插入排序练习题及解析

#### 题目描述
给定一个整数数组 `arr`，长度为 `n`。编写函数实现直接插入排序算法，按照升序排列该数组。

#### 输入格式
输入的第一行为测试用例的数量 `T` (`1 ≤ T ≤ 10`)。
对于每一个测试用例，第一行是一个正整数 `N` 表示数组的大小(`1 ≤ N ≤ 100`)；第二行有 `N` 个整数代表待排序的数组元素，这些整数值范围在 `-1000` 到 `1000` 之间[^1]。

#### 输出格式
针对每一组测试数据输出两行：第一行为排序后的数组元素列表，各元素间以单个空格隔开；第二行为用于记录每次插入操作前后的状态变化说明【可选】。

#### 示例代码

#include <iostream>
using namespace std;

void insertSort(int *array, int length){
    for (int i = 1; i < length; ++i) {
        int current = array[i];
        int j;
        // 寻找合适的位置并移动较大的元素到右边
        for(j=i;j>0 && current<array[j-1];--j){  
            array[j]=array[j-1];
        }
        array[j]=current;// 将当前值放入正确位置
        
        // 打印每一步的状态(可选)
        cout << "After inserting element at index "<<i<<": ";
        for(int k=0;k<length;++k){
            cout<<array[k]<<" ";
        }
        cout<<"\n";
    }
}

int main(){
    int t,n,*nums;
    
    cin>>t;
    while(t--){
        cin >> n;
        nums=new int[n];
        
        for(int i=0;i<n;++i){
            cin>>nums[i];
        }

        insertSort(nums,n);

        // 输出最终结果
        for(int i=0;i<n;++i){
            if(i!=0)cout<<" ";
            cout<<nums[i];
        }
        delete[] nums;
        cout<<"\n";
    }
}

此程序实现了简单的直接插入排序逻辑，并且展示了如何处理多个测试案例以及打印中间过程中的数组状态以便于理解整个排序流程的工作机制。