直接插入排序（初级版）之C++实现
一、源代码：InsertSortLow.cpp
/*直接插入排序思想：
假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。
从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。
*/ #include<iostream>
using namespace std;
/*定义输出一维数组的函数*/
void print(int array[], int n)
{
for (int i = ; i < n; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
/*
首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1)；
然后将R[k．．i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。
注意：
若R[i]的关键字大于等于R[1．．i-1]中所有记录的关键字，则R[i]就是插入原位置。
*/
int insertSort(int array[], int n)
{
//定义变量，记录交换次数
int count = ;
//定义中间变量，做为临时交换变量
int temp;
int j;
//遍历数组（进行排序）
cout << "开始对数组进行排序了..." << endl;
for (int i = ; i < n; i++)
{
//当左边元素大于右边元素时
if (array[i] < array[i - ])
{
//将当前的数组元素存储到临时变量中
temp = array[i];
//将从i位置（比temp大的元素）开始的数组元素整体后移
for (j = i - ; j >= && array[j]>temp; j--)
{
cout << "第" << (i + ) << "趟第" << (j + ) << "次排序" << endl;
//将数组中的元素整体后移一个单位
array[j + ] = array[j];
cout << array[j] << "和" << array[j + ] << "互换了" << endl;
//输出此时数组的顺序
cout << "数组此时的顺序是：";
print(array, );
//每交换一次，记录数加1
count++;
}
array[j + ] = temp;
}
}
cout << "数组排序结束了..." << endl;
return count;
} int main()
{
//定义待排序的一维数组
int array[] = { , , , , , , , , , };
//输出原始数组
cout << "原始数组是：" << endl;
print(array, );
//对数组进行排序
int count = insertSort(array, );
//输出排序后的数组
cout << "排序后的数组是：" << endl;
print(array, );
cout << "共交换" << count << "次" << endl;
return ;
}
二、运行效果