排序4-希尔排序

插入排序在以下情况时效率较高

1. 当元素序列基本有序

2. 元素个数较少

希尔排序是对插入排序的优化

希尔排序先将元素分组(通常为总长度的一半, 例如有8个数据量, 则将数据分为4组, 每组2个数据),

然后再对每一组元素单独进行插入排序, 创造出满足上述2个条件的情况

示意(间隔为2, 分组为2)

数据分别排序后归位, 相对有序的序列, 对整体进行一次插入排序

希尔排序

void shellSort(int arr[], int length){
    int i,j,k;
    //增量(等于1时,全部元素归为一组, 进行直接的插入排序)
    int increasement = length;
    do{
        //确定分组的增量
        increasement = increasement/3 + 1; //减少增量
        for (i = 0; i < increasement; i++){
            //对每一组都进行插入排序
            for (j = i+increasement; j < length; j+=increasement){
                if(arr[j] < arr[j-increasement]){
                    int tmp = arr[j];
                    for (k = j-increasement; k>=0 && tmp<arr[k]; k-=increasement){
                        arr[k+increasement] = arr[k];
                    }
                    arr[k+increasement] = tmp;
                }            
            }

        }
    }while(increasement>1); //直到增量为1
}

与插入排序效率比较

int main(){
    int arr[MAX];
    int arr2[MAX];
    int randNum;
    srand((unsigned int)time(NULL));
    for (int i = 0; i < MAX; i++){
        randNum = rand() % MAX;
        arr[i] = randNum;
        arr2[i] = randNum;
    }

    long t1 = getSystemTime();
    shellSort(arr,MAX);
    long t2 = getSystemTime();
    cout << "希尔排序" << MAX << "个元素耗时:" << t2-t1 << "ms" << endl;

    long t3 = getSystemTime();
    insertSort(arr2,MAX);
    long t4 = getSystemTime();
    cout << "插入排序" << MAX << "个元素耗时:" << t4-t3 << "ms" << endl;

    system("pause");
    return 0;
}