#include<iostream>
using namespace std;
#include"ShellSort.h"
#include"swap.h"
int comparisons2 = 0;
int moves2 = 0;
bool stable2 = true;
void ShellSort(int arr[], int n, int& comparisons, int& moves)
{
// 创建辅助数组，保存原始索引位置
int* aux = new int[n];
for (int i = 0; i < n; i++)
{
aux[i] = i;
}
int gap = n / 2;
while (gap > 0)
{
for (int i = gap; i < n; i++)
{
int temp = arr[i];
int tempAux= aux[i];
int j = i;
// 将arr[j-gap]与arr[j]进行比较并交换位置
while (j >= gap && arr[j - gap] > temp)
{
arr[j] = arr[j - gap];
aux[j] = aux[j - gap];
j -= gap;
comparisons2++;//关键字比较一次
moves2++;//关键字移动一次
}
arr[j] = temp;
aux[j] = tempAux;
moves2++;//关键字移动一次
}
// 更新增量值
gap /= 2;
}
// 验证稳定性
for (int i = 1; i < n; i++)
{
// 如果值相等，但是索引位置发生变化，则说明不稳定
if (arr[i] == arr[i - 1] && aux[i] < aux[i - 1])
{
stable2 = false;
break;
}
}
}
void test2(bool &stable)
{
if (stable2)
{
cout << "希尔排序是稳定的" << endl;
}
else
{
cout << "希尔排序是不稳定的" << endl;
}
}
这个用辅助数组验证稳定性的方法是在网上找的，我感觉逻辑没什么问题，但是输出希尔排序是稳定的，不过希尔排序不是不稳定的吗，我不知道哪里出了问题，帮我找一下谢谢
测试稳定性需要通过多组数据来验证，至少包括：
（1）随机数组
（2）递增数组
（3）递减数组
（4）完全重复数组
且数据量必须足够大！
所以，你需要定义4个以上数组（随机数组可以定义多个），然后再判断就可以了
稳定指的是任何时候排序过后索引的相对位置都不变
而你传入了一个数组，这只是验证了其中一种情况而已，不能说就是稳定的
说的极端一点
我随便定义一个数组{1,2,3}
这东西拿任何一种算法来排，都不可能不稳定，因为里面根本连重复的元素都没有，索引怎么可能会变
/* 初始化散列表 */
Status InitHashTable (HashTable *H)
{
int i;
m=HASHSIZE;
H->count=m;
H->elem=(int *)malloc(m*sizeof(int));
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
return OK;
}