希尔排序之C++实现（高级版）
一、源代码：ShellSortHigh.cpp
/*希尔排序基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；
然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1(<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
*/
#include<iostream>
using namespace std;
/*定义输出一维数组的函数*/
void print(int array[], int n)
{
for (int i = ; i < n; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
/*
一种查找比较操作和记录移动操作交替地进行的方法。
具体做法：
将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：
① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；
②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。
关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。 */
int shellSort(int array[], int n)
{
//定义变量，记录交换次数
int count = ;
//定义中间变量，做为临时交换变量
int temp;
//遍历数组（进行排序）
cout << "开始对数组进行排序了..." << endl;
//定义初始增量值
int gap = n;
do{
//初始增量变化规律
gap = gap / + ;
for (int i = gap; i < n; i++)
{
for (int j = i; j >= gap; j-=gap)
{
if (array[j] < array[j - gap])
{
temp = array[j];
array[j] = array[j - gap];
array[j - gap] = temp;
cout << array[j] << "和" << array[j - gap] << "互换了" << endl;
//输出此时数组的顺序
cout << "数组此时的顺序是：";
print(array, );
//每交换一次，记录数加1
count++;
}
else
{
break;
}
}
}
} while (gap>);
cout << "数组排序结束了..." << endl;
return count;
} int main()
{
//定义待排序的一维数组
int array[] = { , , , , , , , , , };
//输出原始数组
cout << "原始数组是：" << endl;
print(array, );
//对数组进行排序
int count = shellSort(array, );
//输出排序后的数组
cout << "排序后的数组是：" << endl;
print(array, );
cout << "共交换" << count << "次" << endl;
return ;
}
二、运行效果