什麼時候shell排序進行冗餘比較？

Question

我的回答是：

Shell排序，使因爲如果元素相距甚遠（當h大約是8），它比那將是鄰居兩個元素，則是要比較相同元素的比較過程中多餘的比較再次比較彼此靠近的元素時（當h大約在1時）。例如，如果列表是113 400 818 612 112 311 412 429，那麼當h = 4時，它將比較113和112，並且當h = 1時，它將再次比較113和112，因爲它將比較彼此最接近的元素。

我的回答正確嗎？

Answer 1

你的例子絕對是一個冗餘發生的地方。事實上，在Shell Sort中無法避免冗餘。正如你注意到的那樣，當h = 1時，它總是比較之前預處理過程中比較的東西。你可以做的一件事是提高Shell Sort的性能（即減少冗餘比較），可以巧妙地選擇h。例如，如果選擇h爲4,2,1，那麼必須將113和112進行三次比較，而如果選擇h爲5,3,1，則冗餘比較會顯着減少。選擇h的一般規則是不選擇2的冪，並且不選擇彼此的倍數。希望這可以幫助。