蓝桥杯 插入排序

蓝桥杯 插入排序

插入排序的思想

插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素逐个插入到已排序序列
的合适位置中，使得已排序序列逐渐扩大，从而逐步构建有序序列，最终得到完全有序的序
列。
它类似于我们打扑克牌时的排序方式，将一张张牌插入到已经有序的手牌中。
时间复杂度为O(n^2)。

插入排序的实现

//i表示当前要确定的位置
for(int i=2;i<=n;i++){//此时[1,i-1]已经为有序的数组int val=a[i],j;//将val和a[j-1]比较//如果val<a[j-1]就将a[j-1]往后移动一格//给val留出位置for(j=i;j>1&&val<a[j-1];j--){a[j]=a[j-1];} //当循环跳出时,j==1或val>a[j] ,且此时a[j]已经往后移动//此时的j为val腾出的位置a[j]=val; 
} 

例题讲解

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int a[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=2;i<=n;i++){int val=a[i],j;for(j=i;j>1&&val<a[j-1];j--){a[j]=a[j-1];} a[j]=val; 
} for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];return 0; 
}