排序算法（二）---插入排序
一、算法思想
每次从无序部分取出一个数据，然后将它插入到有序部分的正确位置。初始时，有序部分只有第一个元素，然后每次将无序部分的第一个元素插入到有序部分，直到所有元素都有序。
具体步骤
- 从第一个元素开始，该元素可以认为已经被排序（有序部分）。
- 取出下一个元素（无序部分的开头），在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5，直到所有元素都排序完毕。
二、时间复杂度
- 最坏情况：当数组是逆序时，每次插入都需要比较和移动有序部分的所有元素。对于第i个元素，需要比较i-1次，所以总比较次数为1+2+...+(n-1) = n(n-1)/2，即O(
)。 - 最好情况：当数组已经有序时，每次插入只需要比较一次，所以总比较次数为n-1，即O(n)。
- 平均情况：也是O()。
三、代码
#include
using namespace std;
int n;
int a[100];
void insert_sort(){
for(int i = 1; i < n; i++){
int key = a[i]; // 当前要插入的元素
int j = i - 1; // 已排序中的最后一个元素索引
// 将已排序部分中比当前要插入元素大的元素向右移动
while(j >= 0 && a[j] > key){
a[j + 1] = a[j];
j--;
}
// 插入key到正确位置
a[j + 1] = key;
}
}
int main(){
cin>>n;
for(int i = 0; i < n; i++){
cin>>a[i];
}
insert_sort();
for(int i = 0; i < n; i++){
cout<
