#include <iostream>
using namespace std;
/*
* 插入排序基本思想
* 将n个元素的数列分为已有序和无序两个部分，如插入排序过程示例下所示：
* {{a1}，{a2，a3，a4，…，an}}
* {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
* {{a1(n-1），a2(n-1) ，…},{an(n-1)}}
* 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，
* 找出插入位置，将该元素插入到有序数列的合适位置中。
*/
int main(){//主函数算法
void InsertSort(int a[]);//直接插入排序算法函数的函数声明
int a[10]={1,2,5,4,3,6,8,7,9,0};//数组包含10个元素
cout<<"排序前:"<<endl;
for (int i=0;i<10;i++) {//输出排序之前数组的10个元素
cout<<a[i]<<" ";
}cout<<endl;
cout<<"------------------------------------------------"<<endl;
InsertSort(a);//调用直接插入排序算法
cout<<"排序后:"<<endl;
for (int j=0;j<10;j++) {//输出排序之后数组的10个元素
cout<<a[j]<<" ";
}
cout<<endl;
getchar();
return 0;
}
void InsertSort(int a[]) {//直接插入排序算法
void swap(int b[], int i, int j);//互换函数的函数声明
for (int i=1;i<10;i++) {
for (int j=i;(j>0)&&(a[j]<a[j-1]);j--) {//第一个元素不比较,放在一边为一组,后面这组的都一个元素依次往第一组插入
swap(a,j,j-1);
}
}
}
void swap(int b[], int i, int j) {//互换函数算法
int temp = b[i];
b[i] = b[j];
b[j] = temp;
}